4
$\begingroup$

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.

  • 0
    Hmm... I thought this smartphone was supposed to be *fast!* Oh well. See the answer.2011-12-07

3 Answers 3

12

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

  • 5
    $1234 \equiv 12 \equiv -1 \pmod{13} \implies 1234^{5678}\equiv (-1)^{5678} \pmod{13} \implies 1234^{5678} \equiv 1 \pmod{13}$2011-12-07
4

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

3

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