Олимпиадные задачи из источника «параграф 3. Сравнения»

Дано <i>n</i> чисел, <i>x</i>₁, <i>x</i>₂, ..., <i>x_n</i>, при этом  <i>x_k</i> = ±1.  Доказать, что если  <i>x</i>₁<i>x</i>₂ + <i>x</i>₂<i>x</i>₃ + ... + <i>x_nx</i>₁ = 0,  то <i>n</i> делится на 4.

Известно, что  <i>ax</i>⁴ + <i>bx</i>³ + <i>cx</i>² + <i>dx + e</i>,  где <i>a, b, c, d, e</i> – данные целые числа, при любом целом <i>x</i> делится на 7.

Доказать, что все числа <i>a, b, c, d, e</i> делятся на 7.

Доказать, что многочлен с целыми коэффициентами  <i>a</i>₀<i>xⁿ</i> + <i>a</i>₁<i>x</i>^<i>n</i>–1 + ... + <i>a</i>_<i>n</i>–1<i>x</i> + <i>a_n</i>,  принимающий при  <i>x</i> = 0  и  <i>x</i> = 1  нечётные значения, не имеет целых корней.

Пусть числа <i>x</i>₁, <i>x</i>₂, ..., <i>x_m</i> образуют полную систему вычетов по модулю <i>m</i>. Для каких <i>a</i> и <i>b</i> числа  <i>y_j = ax_j + b</i>  (<i>j</i> = 1, ..., <i>m</i>)  также образуют полную систему вычетов по модулю <i>m</i>?

Докажите, что любые <i>m</i> чисел <i>x</i>₁,..., <i>x_m</i>, попарно не сравнимые по модулю <i>m</i>, представляют собой полную систему вычетов по модулю <i>m</i>.

Докажите, что два класса <span style="text-decoration: overline;"><i>a</i></span> и <span style="text-decoration: overline;"><i>b</i></span> совпадают тогда и только тогда, когда  <i>a ≡ b</i> (mod <i>m</i>).

Докажите, что класс <span style="text-decoration: overline;"><i>a</i></span> состоит из всех чисел вида  <i>mt + a</i>,  где <i>t</i> – произвольное целое число.

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

Решите в целых числах уравнение   2^<i>x</i> – 1 = 5^<i>y</i>.

Решите в натуральных числах уравнение   1! + 2! + ... + <i>n</i>! = <i>m</i>².

Докажите, что числа  <i>H_n</i> = 1 + ¹/₂ + ¹/₃ + ... + ¹/_<i>n</i>  при  <i>n</i> > 1  не будут целыми.

Докажите, что следующие уравнения не имеют решений в целых числах:

  а)  <i>x</i>² + <i>y</i>² = 2003;

  б)  12<i>x</i> + 5 = <i>y</i>²;

  в)   – <i>x</i>² + 7<i>y</i>³ + 6 = 0;

  г)  <i>x</i>² + <i>y</i>² + <i>z</i>² = 1999;

  д)  15<i>x</i>² – 7<i>y</i>² = 9;

  е)  <i>x</i>² – 5<i>y</i> + 3 = 0;

  ж)  <img align="absmiddle" src="/storage/problem-media/60724/problem_60724_img_2.gif"> 

  з)  8<i>x</i>³ – 13<i>y</i>³ = 17.

Докажите, что числа <i>p</i> и  <i>p</i> + 2  являются простыми числами-близнецами тогда и только тогда, когда  4((<i>p</i> – 1)! + 1) + <i>p</i> ≡ 0 (mod <i>p</i>² + 2<i>p</i>).

Докажите, что <i>p</i> – простое тогда и только тогда, когда   (<i>p</i> – 2)! ≡ 1 (mod <i>p</i>).

Докажите, что для простого <i>p</i>   (<i>p</i> – 1)! ≡ – 1 (mod <i>p</i>).

<i>p</i> – простое число. Для каких чисел <i>a</i> решением сравнения  <i>ax</i> ≡ 1 (mod <i>p</i>)  будет само число <i>a</i>?

В каких случаях разрешимо сравнение  <i>ax ≡ b</i> (mod <i>m</i>)? Опишите все решения этого сравнения в целых числах.

Найдите все такие пары чисел вида <span style="text-decoration: overline;">1<i>xy</i>2</span> и <span style="text-decoration: overline;"><i>x</i>12<i>y</i></span>, что оба числа делятся на 7.

Решите сравнения:

  а)  8<i>x</i> ≡ 3 (mod 13);

  б)  17<i>x</i> ≡ 2 (mod 37);

  в)  7<i>x</i> ≡ 2 (mod 11);

  г)  80<i>x</i> ≡ 17 (mod 169).

Докажите, что  <i>p</i>^<i>p</i>+2 + (<i>p</i> + 2)^<i>p</i> ≡ 0 (mod 2<i>p</i> + 2),  где  <i>p</i> > 2  – простое число.

Докажите, что если  6<i>n</i> + 11<i>m</i>  делится на 31, то  <i>n</i> + 7<i>m</i>  также делится на 31.

Может ли число  ¹/₃ (<i>n</i>² + 1)  быть целым при натуральном <i>n</i>?

Докажите, что число  1^<i>k</i> + 2^<i>k</i> + ... + 12^<i>k</i>  делится на 13 для  <i>k</i> = 1, 2, ..., 11.

Докажите справедливость следующих сравнений:

  а)  1 + 2 + 3 + ... + 12 ≡ 1 + 2 + 2² + ... + 2¹¹ (mod 13);

  б)  1² + 2² + 3² + ... + 12² ≡ 1 + 4 + 4² + ... + 4¹¹ (mod 13).

Найдите все такие целые числа <i>x</i>, что  <i>x</i> ≡ 3 (mod 7),  <i>x</i>² ≡ 44 (mod 7²),  <i>x</i>³ ≡ 111 (mod 7³).