# multiply different residue classes

I am trying to solve a problem. Proof that $$300^{3000} \equiv 1 \bmod 1001$$ So after a bit of puzzeling I found that $$1001 = 7*11*13$$ and I have prooved that:

• $$300^{3000} \equiv 1 \;(\bmod 7\;)$$
• $$300^{3000} \equiv 1 \;(\bmod 11\;)$$
• $$300^{3000} \equiv 1 \;(\bmod 13\;)$$

Now I wish to conclude that therefore $$300^{3000} \equiv 1 \bmod 1001$$

But that hinges on the assumption that I can multiply residue classes somehow like:

$$[1]_7 * [1]_{11} * [1]_{13} = [1]_{1001}$$ or more general maybe: $$[a]_p * [b]_q * [c]_{13} = [abc]_{pqr}$$

Now we have some things that may help such as the factors $$p,r,r$$ being (co)prime in this case... but exaclty based on what can we draw such a conclusion ?

I was thiking of that somehow we can use Bezout, which guarantees that if $$gcd(p,q)=1 => (\exists x,y \in \mathbb{Z})\;(px+qy=1)$$

but after scribbling some papers full of almosts...I want to ask you guys for some direction. Thanks!

• The chinese remainder theorem is the key for your problem. – Peter Jan 12 at 13:03

You can't multiply the residue classes like that. If all three were congruent to $$2$$, the answer would be $$2$$, not $$8$$. As others have said, the Chinese Remainder Theorem is the thing. But you can proceed as follows. Let $$x=300^{3000}$$. Then $$x\equiv 1 \pmod{7}$$ tells us that $$x=7r+1$$ for some integer $$r$$. Put this in the second congruence to see that

$$x = 7r+1 \equiv 1 \pmod{11}.$$

Solve this for $$r$$ in the usual way to get $$r\equiv 0 \pmod{11}$$, which is to say $$r=11s$$ for some integer $$s.$$ Then we have $$x=7(11s)+1$$. Plug this into the last congruence to get

$$x=77s+1 \equiv 1\pmod{13}.$$

Solve this in the usual way to get $$s\equiv 0 \pmod{13}$$, or $$s=13t$$ for some integer $$t$$. Now you have

$$x = 77(13t)+1 =1001t+1 \equiv 1 \pmod{1001}.$$

• Thank you! ice and clean answer! Now that i see it, it seems so simple! :) – Chai Jan 12 at 14:30
• @Chai This is - at the heart - a property of $\,{\rm lcm}\,$ - one that is so fundamental in number theory that one must know it well to be proficient. See my answer and the linked answers for more on that. – Bill Dubuque Jan 12 at 15:22

If you have a calculator, here's a long way to do it. $$300^{3000}\equiv(-90)^{1500}\equiv92^{750}\equiv456^{375}\equiv(456^2)^{187}\cdot 456\equiv((-272)^2)^{93}\cdot(-272)\cdot456\equiv(-90)^{93}\cdot92$$$$(-90)^{93}\cdot92\equiv(90^2)^{46}\cdot90\cdot92\equiv92^{46}\cdot272\equiv(456^2)^{11}\cdot456\cdot272\equiv -272^{12}\cdot456\equiv-90^6\cdot456$$$$-90^6\cdot456\equiv-92^3\cdot456\equiv(-90)\cdot456\equiv1$$

• heheh yes, the short way is to type it in a computer... but the idea is to proof it without the aid of such :) – Chai Jan 12 at 13:29
• I meant for a standard calculator, you can easily evaluate the square of a number. – TheSimpliFire Jan 12 at 13:30
• Note that there is the cycle $90,92,456,272$ – TheSimpliFire Jan 12 at 13:31

Since $$1$$ is a solution to all three congruences, the Chinese remainder theorem tells us that it is the unique solution $$\pmod{1001}$$.

The inference follows immediately from the $$\rm\color{#c00}{universal}\,$$ property of $$\,{\rm lcm}$$ = least common multiple, viz.

$$\ x\equiv a\pmod{\!k,m,n}\!\iff\!$$ $$\smash[t]{\overbrace{k,m,n\mid x\!-\!a\!\color{#c00}\iff\! \ell := {\rm lcm}(k,m,n)\mid x\!-\!a}}$$ $$\!\iff\! x\equiv a\pmod{\!\ell}$$

So in the OP we have $$\ x\equiv 1\pmod{\!7,11,13}\iff x\equiv 1\pmod{7\cdot 11\cdot 13}$$

Remark  Alternatively we can use CCRT = Constant-case of CRT (Chinese Remainder Theorem), which is equivalent to the above $$\,{\rm lcm}\,$$ property.