2

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?

Peter Phipps
  • 3,065
Algebruh
  • 600
  • 3
    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. – Doctor Who Aug 20 '20 at 20:21
  • 1
    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)$. – Jyrki Lahtonen Aug 20 '20 at 20:24

2 Answers2

4

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$.

markvs
  • 19,653
1

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$.

John Omielan
  • 47,976