Покажи то $7^{(2n^2 + 2n)}$ конгруэнтно $1 \bmod 60$
Только что сдал экзамен, но мне не удалось решить следующую задачу:
Покажите, что следующее верно для всех $n \in \mathbb{N}$:
$7^{2(n^2 +n)} \equiv 1 \mod 60$
Я пытался показать, что показатель степени кратен $\varphi(60) = 16$ а затем используйте $a^{\varphi(n)} \equiv 1 \mod n$но я думаю, что это неправильно, или, по крайней мере, это меня не продвинуло. Есть ли у кого-нибудь совет или уловка, как решить эту проблему?
Ответы
Да, $n^2+n=n(n+1)$ всегда даже так $2n^2+2n$ делится на $4$, так $2n^2+2n=4k$ и $7^{2n^2+2n}=(7^4)^k=2401^k \equiv 1 \mod 60$.
На самом деле, вам просто нужно показать показатель всегда кратна мультипликативного порядка в$7$ по модулю $60$. Поскольку это значение должно делиться$\varphi(60) = 16$, это должен быть фактор $16$. Как видно из комментария к вопросу Доктора Кто , вы можете легко определить и проверить порядок умножения.$4$ поскольку $7$ и $7^2 = 49$ не работают, но $7^4 = 2401 \equiv 1 \pmod{60}$работает. Затем вам просто нужно подтвердить$n^2 + n = n(n + 1)$ всегда четный, что довольно легко сделать, так как либо $n$ или же $n + 1$ даже для всех $n$.