Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 4:23

4 Answers 4

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

share|improve this answer
    
Why mod 20 ?? what property/theorem did you use to pass from the first equation to the second one ?? –  user132226 May 19 at 4:14
    
@user132226, Have you followed the links? We shall have $$4^{20}\equiv1\pmod{55}$$ –  lab bhattacharjee May 19 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.

share|improve this answer
    
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 at 4:24
    
Can you use the Chinese Remainder Theorem? –  David May 19 at 4:28
    
Yep !! we saw that actually :) –  user132226 May 19 at 4:29
    
See extra solutions. –  David May 19 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.

share|improve this answer

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

share|improve this answer
    
@Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. –  Bill Dubuque May 19 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 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 at 22:05
    
I've been triple downvoted on several answers; hopefully it'll be corrected soon. –  user61527 May 19 at 22:12
    
Indeed; I've also sent a complaint message recently (we'll see what happens). –  user61527 May 19 at 22:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.