Олимпиадные задачи из источника «параграф 2. Алгоритм Евклида»

Отметим на прямой красным цветом все точки вида  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).

Докажите равенства

  а)  [1, 2,..., 2<i>n</i>] = [<i>n</i> + 1, <i>n</i> + 2, ..., 2<i>n</i>];

  б)  (<i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>) = (<i>a</i>₁, (<i>a</i>₂, ..., <i>a_n</i>));

  в)  [<i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>] = [<i>a</i>₁, [<i>a</i>₂, ..., <i>a_n</i>]].

Докажите, что если  (<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  разрешимо в целых числах.

Найдите все взаимно простые <i>a</i> и <i>b</i>, для которых   <img width="92" height="51" align="MIDDLE" border="0" src="/storage/problem-media/60519/problem_60519_img_2.gif"> = ³/₁₃.

Существует ли в сутках момент, когда расположенные на общей оси часовая, минутная и секундная стрелки правильно идущих часов образуют попарно углы в 120°?

Докажите, что число шагов в алгоритме Евклида может быть сколь угодно большим.

Решите в целых числах уравнения:

  а)  45<i>x</i> – 37<i>y</i> = 25;

  б)  19<i>x</i> + 95<i>y</i> = 1995;

  в)  10<i>x</i> + 2<i>y</i> + 18<i>z</i> = 7;

  г)  109<i>x</i> + 89<i>y</i> = 1;

  д)  43<i>x</i> + 13<i>y</i> = 21;

  е)  34<i>x</i> – 21<i>y</i> = 1.

Как описать все решения в целых числах уравнения  <i>ax + by = c</i>  при произвольных целых <i>a, b, c</i>?

<i>a, b, c</i> – целые числа, причем  (<i>a, b</i>) = 1.  Пусть  (<i>x</i>₀, <i>y</i>₀)  – некоторое целочисленное решение уравнения  <i>ax + by</i> = <i>c</i>.

Докажите, что все решения этого уравнения в целых числах получаются по формулам  <i>x = x</i>₀ + <i>kb,  y = y</i>₀ – <i>ka</i>,  где <i>k</i> – произвольное целое число.

Пусть <i>a</i> и <i>b</i> – натуральные числа. Докажите, что среди чисел <i>a</i>, 2<i>a</i>, 3<i>a, ..., ba</i> ровно  (<i>a, b</i>)  чисел делится на <i>b</i>.

Докажите, что если  (<i>a, b</i>) = 1,  то наибольший общий делитель чисел  <i>a + b</i>  и  <i>a</i>² + <i>b</i>²  равен 1 или 2.

Докажите, что если  (<i>a, b</i>) = 1,  то  (2<i>a + b, a</i>(<i>a + b</i>)) = 1.

Докажите, что равенство  (<i>a, mn</i>) = 1  равносильно выполнению двух условий  (<i>a, m</i>) = 1  и  (<i>a, n</i>) = 1.

Докажите, что  <i>p</i>_<i>n</i>+1 ≤ 2^{2^<i>n</i>} + 1,  где <i>p_n</i> – <i>n</i>-е простое число.

Докажите, что число  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  – числа Ферма.

На какие натуральные числа можно сократить дробь  <img width="67" height="49" align="MIDDLE" border="0" src="/storage/problem-media/60506/problem_60506_img_2.gif">,  если известно, что она сократима и что числа <i>m</i> и <i>n</i> взаимно просты.

Найдите все натуральные  <i>n</i> > 1,  для которых  <i>n</i>³ – 3  делится на  <i>n</i> – 1.

При каких целых $n$ число

  а) $\frac{n^4+3}{n^2+n+1}$;   б) $\frac{n^3+n+1}{n^2-n+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">?