How many positive integer $(n < 180)$ that$ (n^3 + 3n+1)^{180} (mod 180) = 1 $?

Question

How can we manage a large exponent and set it to a perfect square or something?

I only started with $n^3 + 3n \equiv 0 \ mod \ 180 \ $ and $n^3 + 3n \equiv -2 \ mod \ 180 \ $

but it seems not sure that coverage all of answers or not.

If I have deal with $(n^3 + 3n+1)^{36} \equiv 1 \ mod \ 180 \ $I can't transform it to a perfect cube.

I'm appreciate for your help.

Answer 1

If this equation is satisfied modulo $180$ then it will be satisfied modulo $2$, $2^2$, $3$, $3^2$, and $5$. This condition is necessary and sufficient.

First, note (and prove) that if $x\not\equiv 0$ modulo any of these then $x^{180}\equiv 1$. This comes from Euler's Theorem (an extension of Fermat's Little Theorem).

Then investigate whether $x\equiv 0$. For instance, $(n^3+3n+1)\equiv 0\pmod 3$ if and only if $n\equiv 2\pmod 3$.

$(n^3+3n+1)\not \equiv 0\pmod 2$ always. You can try the other moduli yourself.

Answer 2

Any number that is coprime to 180, will satisfy the relation $n^{180}=1 \pmod{180}$.

This is because the period of 180 divides the lcm of the euler totitive of the primes, vis 4*9*5 -> 2*6*4 = 12.

It then matters modulo 4, 5, 9 what solutions are coprime to these. They all are for 4, for 5, we see that 1, 2 fails, so 3/5 work. With 9, we see that for 0,1 mod 3 is not a multiple of 3, while 2 is, so 2/3 work. All together, 6/15 or 72/180 of the numbers under 180 will give a remainder of 1.