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

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