0

I'm trying to find the residue of $\frac{64^{82}}{12}$. This means that I need to find $m$ such that $64^{82} ≡_{12} m$. Using Fermat's little theorem, I have $6^11 ≡_{12} 1$. However, 12 is a nonprime number, so my question is: how can I find that residue using Fermat's little theorem?

flt0102
  • 1
  • It is clear that $64^{82}\equiv 0\pmod{4}$. Now work modulo $3$. Here you can use Fermat's Theorem. (But Fermat's Theorem may be overkill for this problem.) – André Nicolas Mar 23 '14 at 19:58
  • I have $64^2 ≡ _{3} 1$. What does this tell me about the residue I'm trying to find? – flt0102 Mar 23 '14 at 20:53
  • Already $64\equiv 1\pmod{3}$. So our number is congruent to $1$ modulo $3$ and $0$ modulo $4$, so it is congruent to $4$ modulo $12$. In principle we have used the Chinese Remainder Theorem, but in practice one can solve the system $x\equiv 1\pmod{3}$, $x\equiv 0\pmod{4}$ "by inspection." – André Nicolas Mar 23 '14 at 20:59
  • Why can you say that it is congruent to 4 modulo 12? – flt0102 Mar 23 '14 at 22:09
  • Because $12$ is small, we can do it like this. Since $x\equiv 0\pmod{4}$, we have $x\equiv 0$, $4$, or $8$\pmod{12}$, Of these $3$ choices, only one is congruent to $1$ modulo $12$. – André Nicolas Mar 23 '14 at 22:30
  • Please tell me if my reasoning is right: I have $m ≡ 0$ (mod 4) and $m≡64$ (mod 3). Using the Chinese remainder theorem: $m≡0$ (mod 4) $→ 4n = m → 4n ≡ 63$ (mod 3). We have that $4·1 ≡ 64$ (mod 3), so $n=1$ and $m=4$. Thus, the residue is $4$. – flt0102 Mar 23 '14 at 23:24
  • We cannot say that $n=1$. The best one can assert is what $n$ is congruent to modulo $3$. – André Nicolas Mar 23 '14 at 23:35
  • So how can I solve for m? I'm a bit confused. – flt0102 Mar 24 '14 at 00:08
  • I will repeat the earlier comment, that was spoiled by a TeX error. Since $x\equiv 0\pmod{4}$, we have $x$ is congruent ot one of $0$, $4$, or $8$ modulo $12$. Of these three possibilities, only $x\equiv 4\pmod{12}$ satisfies the condition $x\equiv 1\pmod{3}$. – André Nicolas Mar 24 '14 at 00:12
  • So that implies that $m$ (the residue) $=4$? – flt0102 Mar 24 '14 at 00:32

1 Answers1

1

$64 \cong 4 \mod 12$. $4^2 = 16 \cong 4 \mod 12$. Thus all (positive) powers of $4$ and hence $64$ are congruent to $4$ modulo $12$.

Eric Towers
  • 67,037