Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I wrote it as $n^{120}=1\pmod{310}$ and thought I'd divide it in simpler congruences with primes (is this right?)
$$n^{120}=n^{4\cdot30}=1\pmod{31}$$
$$n^{120}=n^{30\cdot4}=1\pmod{5}$$
But then I'm stuck on this one: it seems to be a false congruence and I guess I can't apply Fermat's theorem on this one, or can I? How do I solve it?
$$n^{120}=1\pmod{2}$$
If this approach is valid I'd prefer answers continuing from here if possible.
Hint: $\varphi(310)=120$, where $\varphi$ is the Euler totient function.
(I generally prefer to post hints as comments, but in this case it's a little too long for a comment).
Hint: Remember that Fermat's theorem is actually a special case of Euler's theorem: given $\gcd(n, a) = 1$, then $n^{\phi(a)} \equiv 1 \pmod a$. Since $\phi(p) = p - 1$ for $p$ prime, you get Fermat's theorem.
Since $\phi(310) = 120$, that means that if $\gcd(n, 310) = 1$, then $n^{120} \equiv 1 \pmod{310}$. That also means that $n^{121} \equiv n \pmod{310}$ and therefore $n^{121} - n \equiv 0 \pmod{310}$ .
Of course if $n$ is a multiple of 310, then $n^\alpha \equiv 0 \pmod{310}$ for any exponent $\alpha \in \mathbb{Z}^+$. Then $n^{120}$ and $n^{121}$ are also multiples of 310, but guess what, so is $n^{121} - n$.
The problem with this approach is that it doesn't help you with a lot of numbers, such as even numbers that are not also multiples of 155.
