1
$\begingroup$

This question already has an answer here:

How do I calculate $12345^{12345} \operatorname{mod} 17$? I cant do it on a calculator? How would I show this systematically?

$\endgroup$

marked as duplicate by Steven Stadnicki, vonbrand, froggie, TooTone, Stefan Hansen Feb 24 '14 at 17:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ Hint: $a^b\bmod n = (a\bmod n)^b\bmod n$. Fermat's Little Theorem can be very useful too! $\endgroup$ – Peter Košinár Feb 24 '14 at 16:38
  • $\begingroup$ Thanks I worked it out but say if x ≡ 12345^12345 mod 17 how would I work out x? $\endgroup$ – user131190 Feb 24 '14 at 16:47
  • $\begingroup$ You've been given all you need, time to show some effort. $\endgroup$ – Christoph Feb 24 '14 at 16:48
4
$\begingroup$

Hint: By Fermat's little theorem, if $c$ is a prime number, and $c$ don't divide $a$, $a^{c-1}\equiv 1 \mod c$

$\endgroup$
  • $\begingroup$ Thanks I worked it out but say if x ≡ 12345^12345 mod 17 how would I work out x? $\endgroup$ – user131190 Feb 24 '14 at 16:47
  • $\begingroup$ @Isaac the question is answered see the other answers $\endgroup$ – happymath Feb 24 '14 at 16:48
3
$\begingroup$

Hint: $$12345=17\cdot726+3=3\pmod{17}$$ Now, show/observe that $3^{16}=1\pmod{17},$ so since $12345=771\cdot16+9,$ then what can we conclude about $3^{12345},$ modulo $17$?

$\endgroup$
0
$\begingroup$

This solution is without using Fermat Little theorem(in case anyone does not know)

$12345\hspace{1 mm} mod \hspace{1 mm}17$=3

So question simplifies to $3^ {12345}\hspace{1 mm} mod \hspace{1 mm}17$

$3^6\hspace{1 mm} mod \hspace{1 mm}17$=-2

So question simplifies to $-2^ {2057}*-2^3\hspace{1 mm} mod \hspace{1 mm}17$

$-2^4\hspace{1 mm} mod \hspace{1 mm}17$=-1

So question simplifies to $-1^ {514}*-2^3*-2\hspace{1 mm} mod \hspace{1 mm}17$=-1

$\endgroup$