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

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

  а)  [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>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>-е простое число.

Докажите, что при  <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">?

Докажите, что следующие дроби несократимы при всех натуральных значениях <i>n</i>:

  а)  <img width="61" height="49" align="MIDDLE" border="0" src="/storage/problem-media/60502/problem_60502_img_2.gif">;   б)  <img width="60" height="55" align="MIDDLE" border="0" src="/storage/problem-media/60502/problem_60502_img_3.gif">;   в)  <img width="81" height="55" align="MIDDLE" border="0" src="/storage/problem-media/60502/problem_60502_img_4.gif">.

Для некоторых целых <i>x</i> и <i>y</i> число  3<i>x</i> + 2<i>y</i>  делится на 23. Докажите, что число  17<i>x</i> + 19<i>y</i>  также делится на 23.

По окружности радиуса 40 катится колесо радиуса 18. В колесо вбит гвоздь, который ударяясь об окружность, оставляет на ней отметки. Сколько всего таких отметок оставит гвоздь на окружности? Сколько раз прокатится колесо по всей окружности, прежде чем гвоздь попадёт в уже отмеченную ранее точку?

Докажите, что для нечётных чисел <i>a, b</i> и <i>c</i> имеет место равенство   (½ (<i>b + c</i>), ½ (<i>a + c</i>), ½ (<i>a + b</i>)) = (<i>a, b, c</i>).

Докажите, что  (<i>bc, ac, ab</i>)  делится на  (<i>a, b, c</i>)².

Может ли наибольший общий делитель двух натуральных чисел быть больше их разности?

Докажите, что  (5<i>a</i> + 3<i>b</i>, 13<i>a</i> + 8<i>b</i>) = (<i>a, b</i>).

Числа от 1 до 1000 выписаны подряд по кругу. Начиная с первого, вычёркивается каждое 15-е число: 1, 16, 31, ..., причём при повторных оборотах зачёркнутые числа считаются снова. Число оборотов не ограничено. Сколько чисел останутся незачёркнутыми?