2
$\begingroup$

How to solve and see resolution of $13^{53} \pmod 7$ using Fermat little Theorem? Using Fermat's Little Theorem, I know it gives me 6 as an answer to this problem..., but why? How is the resolution? Thanks,

  • 3
    Are you sure it is related somehow to `Mathematica` programming ? Hint : for odd numbers it is always 6.2012-09-25
  • 0
    I mean $13^k \mod 7 = 6$ for all odd $k$.2012-09-25
  • 0
    Ok, thank you.. But why?.. I mean, which theorem says so..?2012-09-25
  • 0
    If this _were_ a Mathematica question the answer should be `Mod[13^53, 7]`2012-09-25
  • 0
    $13 \times 6 \mod 7 = 1$ and $13 \times 1 \mod 7 = 6$. You should complete the rest to prove this theorem.2012-09-25
  • 1
    @LeandroArielAltamirano Write $13^k$ as $(7+6)^k$ and then look at the terms... there's only one term that's not a power of $7$. Now look at that term for odd and even $k$. That should give you a clue... You can further expand that term as $(7-a)^k$ where you'll have to figure out what $a$ is, apply the same logic and you'll see that it boils down to either $-1\, \text{mod}\, 7$ or $1\, \text{mod}\, 7$, depending on whether $k$ is odd or even, giving you $6$ and $1$ respectively.2012-09-25
  • 0
    I meant a _multiple_ of 7 in the first line above...2012-09-25

1 Answers 1

7

Fermat's Little Theorem says $x^7\equiv x\pmod{7}$. When $x\not\equiv0\pmod{7}$, we can divide by $x$ to get $$ x^6\equiv1\pmod{7} $$ In the case of $13^{53}$, we get that $13^{53}=13^{6\cdot8+5}=\left(13^6\right)^8\cdot13^5\equiv1^8\cdot(-1)^5\equiv-1\pmod{7}$ since $13^6\equiv1\pmod{7}$ and $13\equiv-1\pmod{7}$.

Of course, since $13\equiv-1\pmod{7}$, we get that $13^{53}\equiv(-1)^{53}\equiv-1\pmod{7}$.

In any case, $13^{53}\equiv-1\equiv6\pmod{7}$.

  • 0
    Ohh..., I want to be like you when I grow Up... Thank You!2012-09-25
  • 1
    @Leandro: You mean you want to be a mean square with a big bushy beard? :-)2012-09-25
  • 2
    @AsafKaragila: only if I haven't trimmed in a long time :-p2012-09-25