Задание олимпиады по теории чисел и принципу Дирихле
Пусть p – простое число, и a не делится на p. Докажите, что найдется натуральное число b, для которого ab ≡ 1 (mod p).
Разобрать решение
Решение 1:a·ap–2 = ap–1 ≡ 1 (mod p).
Решение 2:Числа 0, a, 2a, ..., (p – 1)a при делении на p дают разные остатки: ia – ja = (i – j)a не делится на p, поскольку |i – j| < p. Следовательно, эти остатки принимают все возможные значения, в том числе и 1.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.