# Find the remainder of $1234^{5678}\bmod 13$

Find the reminder of $1234^{5678}\bmod 13$

I have tried to use Euler's Theorem as well as the special case of it - Fermat's little theorem. But neither of them got me anywhere.

Is there something important here that I am missing.

-
1234 = -1mod13. – The Chaz 2.0 Dec 7 '11 at 21:43
Hmm... I thought this smartphone was supposed to be fast! Oh well. See the answer. – The Chaz 2.0 Dec 7 '11 at 21:45

Well, the first thing is that $1234 \equiv 12 \equiv -1 \pmod{13}.$ And 5678 is even. So the answer is 1.

-
I failed to follow the logic here. I understand that $1234\equiv 12\equiv -1(\mod 13)$ but why 5678 is even makes the answer 1 – geraldgreen Dec 7 '11 at 21:58
$1234 \equiv 12 \equiv -1 \pmod{13} \implies 1234^{5678}\equiv (-1)^{5678} \pmod{13} \implies 1234^{5678} \equiv 1 \pmod{13}$ – Rashmirathi Dec 7 '11 at 22:32

$\rm mod\ 13\!:\ \ 12\: \equiv\: -1,\ 10\:\equiv\:-3\$ so $\rm\ 1234\ =\ 12\cdot 10^{\:2} +\: 34\ \equiv\:\: -1\cdot (-3)^2 + 34\ \equiv\: 25\ \equiv\: -1\:.\$

Therefore $\rm\quad 1234^{2\:N}\ \equiv\ (-1)^{2\:N}\ \equiv\ ((-1)^2)^N\ \equiv\ 1^N\ \equiv 1\pmod{ 13}$

-

$1234^{5678} \quad \equiv_{13} \quad (-1)^{5678} \quad \equiv_{13} \quad((-1)^2)^{2839} \quad \equiv_{13} \quad 1^{2839} \quad \equiv_{13}\quad 1$.

-