0
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ The chinese remainder theorem is the key for your problem. $\endgroup$ – Peter Jan 12 at 13:03
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! ice and clean answer! Now that i see it, it seems so simple! :) $\endgroup$ – Chai Jan 12 at 14:30
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jan 12 at 15:22
0
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.