Закон предложения

Задачи  для самостоятельного решения

1. Найти  остаток от деления  а) 315²⁰  на 15;

                            б) 1021³⁰⁰  на 3;

                              в) 5¹⁰⁰ + 13¹⁰ на 4;

                              г) 11¹⁰⁰ ∙ 22²  на 5.

2. Найти  остаток от деления 5²⁰ ∙ 6¹⁹ - 9¹⁰ + 13⁴ на 4.

3. Доказать, что  на 3¹⁰⁵ + 4¹⁰⁵ делится нацело на 181.

4. Найти  остаток от деления  (9674⁶ + 28)¹⁵ на 39.

5. При  делении натурального числа n на 3 получается остаток 1, а при делении n на 37, остаток равен 33. Найдите остаток от деления n на 111.

6. Доказать, что  p² – q² делится нацело на 24, если p, q – простые числа, большие 3.

7.  Доказать, что если натуральное число  делится на 99, то сумма его цифр в десятичной записи не менее 18. 
 
 
 

Часть 2.

Решение сравнений первой степени.  

Определение

ax 

называют  сравнением первой степени.

Решить  сравнение, значит, найти x по модулю m. 

Пример

Решить  сравнение первой степени 5x 

Решение

Из 5x 9 (mod 11) следует, что 5x – 9 = 11t или 5x – 11t = 9.

Имеем линейное уравнение с двумя неизвестными, которое мы умеем решать в целых числах.

НОД(5,11) = 1. Поэтому  решение этого уравнения ищем в виде

 Найдем частное  решение уравнения, причем такое,  что  x₀- лежит между 0 и 10, так как мы решаем сравнение по модулю 11. А ведь остатки от деления на 11 лежат между 0 и 10.

Очевидно, что  такое решение всегда существует, если вообще есть решение уравнения.

      Поэтому, осуществим некоторый перебор от 0 до 10. Пусть x₀= 0. Тогда при подстановке этого значения имеем

0 –  11t₀ = 9,

что требует  нецелого t₀ (равного ). Значит, такое x₀ нас не удовлетворит.

      Пусть x₀= 1. Получим 5∙1 - 11t₀ = 9, откуда  t₀ = . Опять нецелое число.

      Проверки  для x₀= 2 и x₀= 3 также приводят нецелому значению  t₀. Однако, при x₀=3 получаем

5∙4 - 11t₀ = 9

или

11t₀ = 11.

Это уравнение  имеет целое решение t₀ = 1. Тогда можно выписать решение для x:

x = 11k + 4.

Последняя запись, означает, что остаток от деления  x на 11 равен 4, то есть

x

Ответ: x 4 (mod 11). 

Задачи  для самостоятельного решения. 

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

а) 5x  3 (mod 12);

б) 6x  7 (mod 3);

в) 9x  6 (mod 3);

г) 7x  9 (mod 17);

д) 256x  179 (mod 337).