# Show that $7^{(2n^2 + 2n)}$ is congruent to $1 \bmod 60$

Just finished an exam but I couldn't solve the following task:

Show that following holds true for all $$n \in \mathbb{N}$$:

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

I've tried to show that the exponent is a multiple of $$\varphi(60) = 16$$ and then use $$a^{\varphi(n)} \equiv 1 \mod n$$ but I guess that's wrong, or at least it didn't take me any further. Has anybody a tip or trick on how to solve this?

• First, check that it holds for $n = 1$. That is, verify manually that $7^4 \equiv 1$. Then, show that $n^2 + n$ is always even. Aug 20, 2020 at 20:21
• You don't need $\phi(60)$. As $60=2^2\cdot3\cdot5$ it suffices, by the Chinese remainder theorem, to look at $\phi(5)$, $\phi(4)$ and $\phi(3)$. Aug 20, 2020 at 20:24

## 2 Answers

Yes, $$n^2+n=n(n+1)$$ is always even so $$2n^2+2n$$ is divisible by $$4$$, so $$2n^2+2n=4k$$ and $$7^{2n^2+2n}=(7^4)^k=2401^k \equiv 1 \mod 60$$.

• Damm...thanks a lot Aug 20, 2020 at 21:25

Actually, you just need to show the exponent is always a multiple of the multiplicative order of $$7$$ modulo $$60$$. Since this value has to divide $$\varphi(60) = 16$$, it must be a factor of $$16$$. As Doctor Who's question comment indicates, you can easily determine and verify the multiplicative order is $$4$$ since $$7$$ and $$7^2 = 49$$ don't work, but $$7^4 = 2401 \equiv 1 \pmod{60}$$ does work. You then just need to confirm $$n^2 + n = n(n + 1)$$ is always even, which is quite easy to do since either $$n$$ or $$n + 1$$ is even for all $$n$$.