Таблицы Брадиса

Целые числа 3. Сравнения

Целые числа 3. Сравнения

Элементы математики в задачах - Г. А. Мерзон

б*) Придумайте простой способ проверки, эквивалентны ли под­становки а и Ь, и выясните, какие из указанных преподавателем подстановок эквивалентны.

Целые числа 3. Сравнения

листок 10 / февраль 2005

Определение 1. Числа а и b сравнимы по модулю т = 0, если а — b. т. Обозначение: а = b (mod m).

Задача 1. Докажите, что а сравнимо с b по модулю т тогда и только тогда, когда остаток от деления а на т равен остатку от деления b на т.

Задача 2. Докажите, что сравнимость по модулю т является отноше­нием эквивалентности.

Задача 3. Докажите, что для любых а1, а2, b1, b2, с, т:

а)  а1 = b1 (mod т), а2 = b2 (mod т) ^ а1 + а2 = b + b2 (mod т);

б)  ах = b (mod т) ^ сах = сЬх (mod т);

в)  ах = b1 (mod т), а2 = b2 (mod т) ^ аха2 = bxb2 (mod т).

Задача 4. Докажите, что если а = b (mod т), то:

а) ап = Ьп (mod т) для любого неотрицательного п; б*) для любого многочлена f (х) с целыми коэффициентами f (а) = f (b) (mod т).

Задача 5. Верно ли, что если а = b (mod т) и а, b ^ 0, то 2а = 2b (mod т)?

Задача 6. Пусть апап_1...а1а0 — десятичная запись числа х. Докажи­те, что:

а)  х = а0 + . + ап (mod 3), х = а0 + . + ап (mod 9);

б)  х = а0 (mod 2), х = а0 (mod 5);

в)  х = а0 — аг + ... + (—1)пап (mod 11).

Задача 7. Докажите, что если х нечетно, то х2 = 1 (mod 8).

Задача 8*. Докажите, что следующие уравнения не имеют ненуле­вых решений в целых числах: а) х2 + y2 = 3z2; б) х2 + у2 + z2 = 4t2.

Задача 9*. Докажите, что существует бесконечно много натураль­ных чисел, не представимых в виде суммы трех а) квадратов; б) кубов натуральных чисел.

Задача 10. Решите сравнения: а) 3х = 1 (mod 7); б) 6х = 5 (mod 9);

в)  4х = 2 (mod 10).

Задача 11. Сравнение ах = b (mod т) имеет решение тогда и только тогда, когда b. НОД(а, т).

Задача 12. Пусть p — простое число, а = 0 (mod p), тогда сравнение ах = b (mod p) имеет решение, причем любые два решения этого сравнения сравнимы по модулю p.