4
$\begingroup$

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.

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

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

$\endgroup$
1
$\begingroup$

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$

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

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.