I wrote it as $n^{120}=1\pmod{310}$ and thought I'd divide it in simpler congruences with primes (is this right?)



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?


If this approach is valid I'd prefer answers continuing from here if possible.

  • 1
    $\begingroup$ This is not true for $n = \pm 1$. $\endgroup$ – Alex Silva Jan 2 '15 at 11:55
  • 3
    $\begingroup$ In fact, it does not hold for any odd $n$. $\endgroup$ – Some Math Student Jan 2 '15 at 11:57
  • $\begingroup$ I think it holds only for numbers in the form $310k$, with $k \in \mathbb{Z}$. $\endgroup$ – Alex Silva Jan 2 '15 at 11:58
  • $\begingroup$ It does actually, I'm checking by plugging number on Wolframalpha, I'm kind of confused right now lol $\endgroup$ – Snowflake Jan 2 '15 at 12:03
  • $\begingroup$ What? This is bizarre. Do you really think $310|n^{121}$ for every integer $n$? The only prime factors of $n^{121}$ are just the prime factors of $n$ with repetition. You are saying that every integer contains the prime factors of $310$. Isn't that a bit unbelievable? $\endgroup$ – MPW Jan 2 '15 at 12:05

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.


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.