3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ $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... $\endgroup$ – Gregory Grant May 6 '15 at 20:49
  • $\begingroup$ 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. $\endgroup$ – André Nicolas May 6 '15 at 20:50
  • $\begingroup$ @AndréNicolas how do I apply the CRT after calculating the values mod 8,3 and 5 here? $\endgroup$ – YoTengoUnLCD May 6 '15 at 20:54
  • $\begingroup$ 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)$. $\endgroup$ – André Nicolas May 6 '15 at 21:06
  • $\begingroup$ @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. $\endgroup$ – YoTengoUnLCD May 6 '15 at 21:09
1
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.