Firstly, the question starts with Fermat's Theorem:
- $5^{2017}$ (mod 7) (mod 11) (mod 13) = ?
I have computed all of them and the answer is (in order): (5, 3, 5).
Secondly, the question asks to compute the below problem using The Chinese Remainder Theorem:
- $5^{2017}$ (mod 1001) = ? (while actually $7*11*13 = 1001$)
What I did is:
- mod 7 mod 11 mod 13
$x$ = $11*13$ $7*13$ $7*11$
$x \equiv 143 \;(\bmod\;7)$
$x \equiv 91 \;(\bmod\; 11)$
$x \equiv 77 \;(\bmod\; 13)$
Therefore:
$x \equiv 3 \;(\bmod\; 7)$
$x \equiv 3 \;(\bmod\; 11)$
$x \equiv 12 \;(\bmod\; 13)$
$x = (B1*X1*C1) + (B2*X2*C2) + (B3*X3*C3)$
Therefore:
$x = (143*3*5) + (91*3*3) + (77*12*5) = 7584$
So, where did I do a mistake?
Best Answer
The mistake is that you forgot to take inverses. We want
$\quad \bmod 7\!:\ \ \ 1/(11\cdot 13)\equiv 1/3\equiv -6/3\equiv \color{#c00}{-2}$
$\quad \bmod 11\!:\,\ 1/(7\cdot 13)\equiv 1/3\equiv 12/3\equiv \color{#0a0}4$
$\quad \bmod 13\!:\!\,\ 1/(7\cdot 11)\equiv 1/(-1)\equiv \color{#90f}{-1}$
so $\,\ x\equiv 5\,\underbrace{(11\cdot 13)(\color{#c00}{-2})}_{\textstyle \equiv 1\pmod{\!7}}\ +\ 3\!\!\!\!\! \underbrace{(7\cdot 13)\,\color{#0a0} 4}_{\textstyle \equiv 1\pmod{\!11}}\!\!\!\! +\ 5\!\!\underbrace{(7\cdot 11)(\color{#90f}{-1})}_{\textstyle \equiv 1\pmod{\!13}}\! = -723 \equiv 278\pmod{\!1001}$
But it is much easier to solve the congruences two-at-a-time as below:
Note $\, x\equiv 5\pmod{\!7\ \&\ 13}\!\iff\! x\equiv 5\pmod{\!91}\,$ so $\,x = \color{#0a0}{5\! +\! 91k}\ $ by CCRT = constant case CRT.
so $\bmod \color{#c00}{11}\!:\,\ 3\equiv x\equiv \color{#0a0}{5 + 91}\,\color{#c00}k\equiv 5+3k\iff 3k\equiv -2\equiv 9\iff \color{#c00}{k\equiv 3}$
Thus we conclude $\,\ x = 5 + 91(\color{#c00}{3\!+\!11n}) = \bbox[5px,border:1px solid #c00]{278 + 1001n}\ \,$ Took $1$ minute of mental arithmetic.