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

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

• $0^4$ is $0$, $1^4$ is $1$, $2^4$ is 16, $3^4$ is 81. Now $4^4=256$ which is 16 again. $5^4=625$ which is 25. $6^4=1296$ which is 96. $7^4=2401$ which is 1 again. $8^4=4096$ which is 16 again. $9^4=6561$ which is 81 again. Starting to see a pattern... – Gregory Grant May 6 '15 at 20:49
• Combine the possible values mod $8$, $3$, $5$ using CRT. There will be $8$ but by using $\pm$ you can express them as $4$ pairs. – André Nicolas May 6 '15 at 20:50
• @AndréNicolas how do I apply the CRT after calculating the values mod 8,3 and 5 here? – YoTengoUnLCD May 6 '15 at 20:54
• This is not the most efficient way. You may know the general CRT procedure $\sum a_iM_i$. For $M_1$, multiply $3$ and $5$, and multiply by something to make the result congruent to $1$ modulo $8$, like $-1$.. For $M_2$, multiply $8$ and $5$, and multiply by something (like $1$) to make the result congruent to $1$ mod $3$. For $M_3$ similar. We get the formula $a_1(-15)+a_2(40)+a_3(-24)$. – André Nicolas May 6 '15 at 21:06
• @AndréNicolas Sorry, I don't know that procedure, for these types of problems what I do is write, for example $a^4=8k$ from the first congruence, then $8k \equiv 0 \pmod 3 \rightarrow k \equiv 0 \pmod 3 \rightarrow k=3q \longrightarrow 24q \equiv 0 \pmod 5$ and do that all the way, but seemed really tedious. – YoTengoUnLCD May 6 '15 at 21:09

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

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

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.