2
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Doctor Who
    Aug 20, 2020 at 20:21
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Jyrki Lahtonen
    Aug 20, 2020 at 20:24

2 Answers 2

Reset to default
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Damm...thanks a lot $\endgroup$
    – Algebruh
    Aug 20, 2020 at 21:25
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.