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

Пусть числа <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>.

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

  а)  <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>ax ≡ b</i> (mod <i>m</i>)? Опишите все решения этого сравнения в целых числах.

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

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

Докажите, что число  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³).

В задаче <a href="https://mirolimp.ru/tasks/160477">160477</a> были определены <i>числа Евклида</i>. Встретится ли каждое простое число в качестве сомножителя некоторого числа Евклида <i>e_n</i>?

Шестизначное число делится на 7. Его первую цифру стёрли, а затем записали её позади последней цифры.

Докажите, что новое число также делится на 7.

а) Докажите, что квадрат целого числа не может оканчиваться четырьмя одинаковыми цифрами, отличными от 0.

б) Какими тремя цифрами может оканчиваться целое число, квадрат которого оканчивается тремя одинаковыми цифрами, отличными от 0?

Равносильны ли сравнения  <i>a ≡ b</i> (mod <i>m</i>)  и   <i>ac ≡ bc</i> (mod <i>mc</i>)?

Когда сравнения  <i>a ≡ b</i> (mod <i>m</i>)  и   <i>ac ≡ bc</i> (mod <i>m</i>)  равносильны?

Из свойств сравнений следует, что с классами вычетов можно делать все операции, которые допустимы для целых чисел: складывать, вычитать, умножать, возводить в степень. Отличие будет лишь в том, что построенная арифметика действует на конечном множестве классов вычетов. Например, для  <i>m</i> = 6  получаются такие таблицы сложения и умножения: <div align="center"><img src="/storage/problem-media/60678/problem_60678_img_2.gif">          <img src="/storage/problem-media/60678/problem_60678_img_3.gif"></div>Постройте аналогичные таблицы сложения и умножения для модулей  <i>m</i>= 7, 8, ..., 13.