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!

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