Задача
Пользуясь результатом задачи 160579, найдите остатки, которые при простом p дают числа Fp и Fp+1 при делении на p.
Решение
Применяя формулу из задачи 60579, находим, что Fp ≡ 5(p–1)/2 (mod p), 2Fp+1 ≡ 1 + 5(p–1)/2 (mod p). Кроме того, 5(p–1)/2 ≡ 1 (mod p) при p = 10k ± 1 и
5(p–1)/2 = –1 (mod p) при p = 10k ± 3.
Ответ
1 и 0 при p = 2; 0 и 3 при p = 5; 1 и 1 при p = 10k ± 1; p – 1 и 0 при p = 10k ± 3.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет