# Modulo Problem, Fermat's little theorem

Find the value of the unique integer x satisfying $O \le x \le 17$ for which $$4^{1024000000002} \equiv x\pmod{17}$$ I think this is related to Fermat's little theorem. I'm knowledgeable with the Chinese remainder theorem and just need some advice on solving this.

• So what's the remainder of $1024000000002$ modulo $17-1$? – Daniel Fischer Aug 25 '13 at 14:52
• recent edit added an x – matthiasgh Aug 25 '13 at 14:53

You can indeed use Fermat's little theorem. Since 17 is prime and 4 is relatively prime to 17, we know that $a^{17-1}=a^{16}\equiv 1\pmod{17}$. Now since $$1024000000002 = 16\cdot64000000000+2$$ we'll have $$4^{1024000000002}=4^{16\cdot64000000000+2}=(4^{16})^{64000000000}(4^2)\equiv(1)(16)\pmod{17}$$

HINT:

As $4^2=16\equiv-1\pmod {17}$ and $a\equiv b\pmod m\implies a^n\equiv b^n\pmod m$ for integer $n\ge0,$

$4^{1024000000002}=(4^2)^{512000000001}\equiv(-1)^{512000000001}\pmod{17}\equiv-1\equiv16$

• recent edit added an x – matthiasgh Aug 25 '13 at 14:54
• @matthiasgh, edited the answer:) – lab bhattacharjee Aug 25 '13 at 14:55
• thanks m8 I think i understand what your saying so i keep getting the square and removing the mod until i reduce the LHS – matthiasgh Aug 25 '13 at 15:00
• @matthiasgh, if you have understood correctly, we need only one squaring and as $512000000001$ is odd, $(-1)^{512000000001}=-1$ – lab bhattacharjee Aug 25 '13 at 15:04
• Ok thanks I just did the example $3^{3002} \cong x(mod.13)$ and got the answer 1 is this correct – matthiasgh Aug 25 '13 at 15:17