# Find number x such that $x\equiv 4^{1002}\pmod{55}$

Find a natural number x, for $0 \le x \le 54$ such that is a solution for the following equation:

$$x\equiv 4^{1002}\pmod{55}$$

This question was asked in an exam, so I expect that the answer is without the use of computers. Any help is appreciated.

-
Actually, we didn´t saw the Euler Theorem in class ... Although that method gives the right answer, I am looking for one that uses congreunces properties – user132226 May 19 '14 at 4:23

Using Carmichael function $\displaystyle\lambda(55)=$lcm$(10,4)=20$

and
$$1002\equiv2\pmod{20}$$

Alternatively, using Euler's totient theorem, $\displaystyle\phi(55)=4\cdot10=40$ and $$1002\equiv2\pmod{40}$$

Either case $$\implies4^{1002}\equiv4^2\pmod{55}$$

-
Why mod 20 ?? what property/theorem did you use to pass from the first equation to the second one ?? – user132226 May 19 '14 at 4:14
@user132226, Have you followed the links? We shall have $$4^{20}\equiv1\pmod{55}$$ – lab bhattacharjee May 19 '14 at 4:16

We have $$\phi(55)=\phi(5\times11)=4\times10=40\ .$$ Since $4$ is coprime to $55$, Euler's Theorem gives $$4^{40}\equiv1\pmod{55}$$ and therefore $$4^{1002}=(4^{40})^{25}4^2\equiv1^{25}4^2\equiv16\pmod{55}\ .$$

Addendum. If you can't use Euler's Theorem, you can calculate $$4^1\equiv4\,,\ 4^2\equiv16\,,\ 4^3\equiv64\equiv9\,,\ 4^4\equiv36\pmod{55}$$ and so on; eventually you will find $4^{10}\equiv1$, and then use a method similar to the above.

Possibly a bit simpler: we have $$4^{1002}\equiv(-1)^{1002}\equiv1\pmod5$$ and $$4^{1002}\equiv(4^5)^{200}4^2\equiv1^{200}4^2\equiv5\pmod{11}\ .$$ Now solve $$x\equiv1\pmod5\ ,\quad x\equiv5\pmod{11}$$ by using the Chinese Remainder Theorem.

-
Thanks for your answer .. however I am looking for a method of finding this without using Euler´s theorem since we didn´t saw it in class ... Thanks anyway :) – user132226 May 19 '14 at 4:24
Can you use the Chinese Remainder Theorem? – David May 19 '14 at 4:28
Yep !! we saw that actually :) – user132226 May 19 '14 at 4:29
See extra solutions. – David May 19 '14 at 4:33

Since the OP asked for a direct proof, note that $4^{3} \equiv 9$ (mod $55$), and that $9^{3} \equiv 14$ (mod $55$). Hence $4^{10} \equiv 4 \times 14 \equiv 1$ (mod $55$), so $4^{1002} \equiv 16$ (mod $55$). Or you can just go through the powers of $4$ one by one (mod $55$), until you notice that $4^{10} \equiv 1$. However, the answers already given illustrate that knowing a little theory can reduce laborious calculation to something much more manageable.

-

Hint $\ \ \begin{eqnarray} {\rm mod}\ 5\!:\ \ \ 2^4\equiv1\,\Rightarrow\, \color{#0a0}{2^{20}}\equiv 1\\ {\rm mod}\ 11\!:\ 2^{10}\equiv1\,\Rightarrow\, \color{#0a0}{2^{20}}\equiv 1\end{eqnarray}\,\color{#c00}\Rightarrow\, {\rm mod}\ 55\!:\ \color{#0a0}{2^{\large 20}}\equiv 1\,\Rightarrow\, 2^{\large 20q+r}\equiv (\color{#0a0}{2^{\large 20}})^{\large q} 2^{\large r}\equiv 2^{\large r}$

where $(\color{#c00}\Rightarrow)$ follows by CRT,  or by $\,5,11\mid 2^{20}\!-1\,\Rightarrow\, 5\cdot 11\mid 2^{20}\!-1,\,$ by $\,{\rm lcm}(5,11) = 5\cdot 11.$

Hence $\ {\rm mod}\ 55\!:\ 4^{\large 1002} = 2^{\large 2004} = 2^{\large 20\cdot 100+4}\equiv 2^{\large 4}$

-
@Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. – Bill Dubuque May 19 '14 at 20:51
It appears that several high-reputation users are currently being serially downvoted, and seems to have nothing to do with answer quality; +1. – user61527 May 19 '14 at 22:00
@T.Bongers Yes, alas, all of my recent answers have been doubly downvoted, apparently by a network of sockpuppets, see this meta thread. Hopefully the community can help to reverse this destructive behavior. – Bill Dubuque May 19 '14 at 22:05
I've been triple downvoted on several answers; hopefully it'll be corrected soon. – user61527 May 19 '14 at 22:12
Indeed; I've also sent a complaint message recently (we'll see what happens). – user61527 May 19 '14 at 22:56