Dimostralo $7^{(2n^2 + 2n)}$ è congruente a $1 \bmod 60$

Question

Ho appena finito un esame ma non sono riuscito a risolvere il seguente compito:

Mostra che il seguito vale per tutti $n \in \mathbb{N}$:

$7^{2(n^2 +n)} \equiv 1 \mod 60$

Ho provato a dimostrare che l'esponente è un multiplo di $\varphi(60) = 16$ e poi usa $a^{\varphi(n)} \equiv 1 \mod n$ma credo che sia sbagliato, o almeno non mi ha portato oltre. Qualcuno ha un suggerimento o un trucco su come risolvere questo problema?

Answer 1

Sì, $n^2+n=n(n+1)$ è sempre così $2n^2+2n$ è divisibile per $4$, così $2n^2+2n=4k$ e $7^{2n^2+2n}=(7^4)^k=2401^k \equiv 1 \mod 60$.

Answer 2

In realtà, devi solo mostrare che l'esponente è sempre un multiplo dell'ordine moltiplicativo di$7$ modulo $60$. Poiché questo valore deve dividere$\varphi(60) = 16$, deve essere un fattore di $16$. Come indica il commento alla domanda di Doctor Who , puoi facilmente determinare e verificare l'ordine moltiplicativo$4$ da $7$ e $7^2 = 49$ non funziona, ma $7^4 = 2401 \equiv 1 \pmod{60}$funziona. Devi solo confermare$n^2 + n = n(n + 1)$ è sempre pari, il che è abbastanza facile da fare $n$ o $n + 1$ è anche per tutti $n$.