Calculate possible values of $a^4$ mod $120$.

Question

Calculate possible values of $a^4$ mod $120$.

I don't know how to solve this, what I did so far:

$120=2^3\cdot3\cdot5$

$a^4 \equiv 0,1 \pmod {\!8}$

$a^4 \equiv 0,1 \pmod {\!3}$

$a^4 \equiv 0,1 \pmod {\!5}$

I could use the CRT to get there's a unique solution mod $30$, but that gets me nowhere, right?

E: I just realized I can calculate $a^4 \bmod 8$ instead of $\!\bmod 2$ and the factors are still $\perp$.

Answer 1

After some heuristics with Excel I saw this:

$$(30b+a)^4 \equiv a^4 \text{ mod 120}$$

This can be verified by expanding the polynomial and noting that $30^4, 4\cdot 30^3, 6\cdot 30^2,$ and $4\cdot 30 \equiv 0 \text{ mod 120}$.

Any integer can be represented as $30b + a$ where $0 \le a \le 29$.

Hence, you can calculate $0^4 \text{ mod 120}$ up to $29^4 \text{ mod 120}$ and catch all of the values: $0,1,16,25,40,81,96,105$.

Answer 2

Property : If $(a,n)=1$ then $a^{\phi(n)}=1\ mod\ n$.

Take $b=3,\ 5$ or $8$.

If $(a,120)=1$, in this case we have for each different values of $b$ : $4$ divide $\phi(b)$ so using the property with $n=b$ we find that $a^{4}=1\ mod\ b$ : each $b$ divide $a^{4}-1$ so do $120$.

Thus if $(a,120)=1$ then $a^{4}=1\ mod\ 120$

Now if $a$ and $120$ have some factors in common then $a=2^b3^c5^dr$ for some $b,\ c$ and $d$. And $(a,r)=1$.

So $a^{4}=2^{4b}3^{4c}5^{4d}=2^{4b}3^{4c}5^{2d}\ mod\ 120$ using the previous property. And if $b,\ c$ and $d$ are $>0$ (30 divide a) then $a^{4}=0\ mod\ 120$.

I don't know if we can be more specific without computing.

Answer 3

Let $\{3,5,8\}=\{n_1,n_2,n_3\}$. When used, $k,m$ denote some integers.

$\color{#0ba}{1)}$ Cases $a^4\equiv 0\pmod{\! n_1,n_2,n_3}$ and $1$ are trivial, give $a^4\equiv \color{#0bc}{0},\color{#0bc}{1}\pmod{\! 120}$, respectively.

$\color{#0ba}{2)}$ If $a^4\equiv 1\pmod{\!n_1},\ a^4\equiv 0\pmod{\!n_2,n_3}$, let $a^4=n_2n_3k$.

$n_2n_3k\equiv 1\pmod{\!n_1}\!\iff\! k\equiv (n_2n_3)^{-1}\pmod{\!n_1}$

So $a^4=n_2n_3(n_1m+((n_2n_3)^{-1}\bmod n_1))=120m+\color{#0bc}{n_2n_3((n_2n_3)^{-1}\bmod {n_1})}$.

$\color{#0ba}{3)}$ If $a^4\equiv 1\pmod{\!n_1,n_2},\ a^4\equiv 0\pmod{\!n_3}$, let $a=n_3k$.

$n_3k\equiv 1\pmod{\!n_1n_2}\!\iff\!k\equiv n_3^{-1}\pmod{\!n_1n_2}$

So $a^4=n_3(n_1n_2m+(n_3^{-1}\bmod{n_1n_2}))=120m+\color{#0bc}{n_3(n_3^{-1}\bmod{n_1n_2})}$.

The blue are the possible residues. Now substitute $3,5,8$ in place of $n_1$ in $\color{#0ba}{2)}$ and in place of $n_3$ in $\color{#0ba}{3)}$ (with $\{3,5,8\}=\{n_1,n_2,n_3\}$).

$\color{#0ba}{2)\!:}$ $\ n_1=3\,\Rightarrow\, a^4\equiv 40\left(\frac{1}{40}\bmod{3}\right)\equiv 40\left(\frac{1}{1}\bmod{3}\right)\equiv 40(1)\equiv \color{#0bc}{40}\pmod{\!120}$.

$\ n_1=5\,\Rightarrow\, a^4\equiv 24\left(\frac{1}{24}\bmod{5}\right)\equiv 24\left(\frac{1}{-1}\bmod{5}\right)\equiv 24(-1)\equiv \color{#0bc}{96}\pmod{\!120}$.

$\ n_1=8\,\Rightarrow\, a^4\equiv 15\left(\frac{1}{15}\bmod{8}\right)\equiv 15\left(\frac{1}{-1}\bmod{8}\right)\equiv 15(-1)\equiv \color{#0bc}{105}\pmod{\!120}$.

$\color{#0ba}{3)\!:}$ $\ n_3=3\,\Rightarrow\, a^4\equiv 3\left(\frac{1}{3}\bmod{40}\right)\equiv 3\left(\frac{81}{3}\bmod{40}\right)\equiv 3(27)\equiv \color{#0bc}{81}\pmod{\!120}$.

$\ n_3=5\,\Rightarrow\, a^4\equiv 5\left(\frac{1}{5}\bmod{24}\right)\equiv 5\left(\frac{25}{5}\bmod{24}\right)\equiv 5(5)\equiv \color{#0bc}{25}\pmod{\!120}$.

$\ n_3=8\,\Rightarrow\, a^4\equiv 8\left(\frac{1}{8}\bmod{15}\right)\equiv 8\left(\frac{16}{8}\bmod{15}\right)\equiv 8(2)\equiv \color{#0bc}{16}\pmod{\!120}$.