Олимпиадные задачи из источника «параграф 2. Алгоритм Евклида» - сложность 3-4 с решениями

Отметим на прямой красным цветом все точки вида  81<i>x</i> + 100<i>y</i>,  где <i>x, y</i> – натуральные, и синим цветом – остальные целые точки.

Найдите на прямой такую точку, что любые симметричные относительно неё целые точки окрашены в разные цвета.

Пусть натуральные числа $a$ и $b$ взаимно просты. Докажите, что для того, чтобы уравнение  $ax + by = c$  имело ровно $n$ целых положительных решений, значение $c$ должно находиться в пределах  $(n - 1) \cdot ab + a + b \leqslant c \leqslant (n + 1) \cdot ab.$

Пусть <i>a</i> и <i>b</i> – натуральные взаимно простые числа. Рассмотрим точки плоскости с целыми координатами  (<i>x, y</i>),  лежащие в полосе  0 ≤ <i>x ≤ b</i> – 1.  Каждой такой точке припишем целое число  <i>N</i>(<i>x, y</i>) = <i>ax + by</i>.

  а) Докажите, что для каждого натурального <i>c</i> существует ровно одна точка  (<i>x, y</i>)  (0 ≤ <i>x ≤ b</i> – 1),  для которой  <i>N</i>(<i>x, y</i>) = <i>c</i>.

  б) <b>Теорема Сильвестра</b>. Докажите, что наибольшее <i>c</i>, для которого уравнение  <i>ax + by = c</i>  не имеет решений в целых неотрицательных числах, имеет вид

<i>c...

В каких пределах должно заключаться <i>c</i>, чтобы уравнение  19<i>x</i> + 14<i>y = c</i>  имело шесть натуральных решений?

Найдите наименьшее <i>c</i>, при котором

  а) уравнение  7<i>x</i> + 9<i>y = c</i>  имело бы ровно шесть натуральных решений;

  б) уравнение  14<i>x</i> + 11<i>y = c</i>  имело бы ровно пять натуральных решений.

На доске написано <i>n</i> натуральных чисел. За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное.

  а) Докажите, что можно провести только конечное число операций.

  б) Финальный результат независимо от порядка действий будет одним и тем же. Например:

    (4, 6, 9) → (2, 12, 9) → (2, 3, 36) → (1, 6, 36),

    (4, 6, 9) → (4, 3, 18) → (1, 12, 18) → (1, 6, 36).

Докажите, что если  (<i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>) = 1,  то уравнение  <i>a</i>₁<i>x</i>₁ + <i>a</i>₂<i>x</i>₂ + ... + <i>a_nx_n</i> = 1  разрешимо в целых числах.

Докажите, что число  2^{2^<i>n</i>} – 1  имеет по крайней мере <i>n</i> различных простых делителей.

Докажите, что при  <i>m ≠ n</i>  выполняются равенства:

  а)  (<i>a^m</i> – 1, <i>aⁿ</i> – 1) = <i>a</i>^{(<i>m, n</i>)} – 1  (<i>a</i> > 1);

  б)  (<i>f_n, f_m</i>) = 1,  где  <i>f_k</i> = 2^{2^<i>k</i>} + 1  – числа Ферма.

При каких целых <i>n</i> сократимы дроби

  а)   <img width="89" height="55" align="MIDDLE" border="0" src="/storage/problem-media/60503/problem_60503_img_2.gif">;   б)  <img width="98" height="55" align="MIDDLE" border="0" src="/storage/problem-media/60503/problem_60503_img_3.gif">?

<i>a, b, c</i> – целые числа; <i>a</i> и <i>b</i> отличны от нуля.

Докажите, что уравнение  <i>ax + by = c</i>  имеет решения в целых числах тогда и только тогда, когда <i>c</i> делится на  <i>d</i> = НОД(<i>a, b</i>).

Натуральные числа <i>p</i> и <i>q</i> взаимно просты. Отрезок  [0, 1]  разбит на  <i>p + q</i>  одинаковых отрезков.

Докажите, что в каждом из этих отрезков, кроме двух крайних лежит ровно одно из  <i>p + q</i> – 2  чисел  ¹/_<i>p</i>, ²/_<i>p</i>, ..., ^<i>p</i>–1/_<i>p</i>,  ¹/_<i>q</i>, ²/_<i>q</i>, ..., ^<i>q</i>–1/_<i>q</i>.