# How do you calculate a large power modulo a small number? [duplicate]

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

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

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

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$

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

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

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