0
$\begingroup$

I'm struggling when solving the simultaneous linear congruences $$x\equiv 3 \pmod{101^{1000}}$$ and $$x\equiv 3 \pmod{7^{200}}$$ where the moduli are very large. I haven't got an issue when solving more reasonably sized moduli.

Could I solve this by reducing them to $x\equiv 3 \pmod{101}$ and $x\equiv 3 \pmod7$? I did this and I got $x\equiv 3 \pmod{707}$ using the Chinese Remainder Theorem. Could I somehow use this result to be $mod7^{200}101^{1000}$ or have I approached this problem completely wrong?

Thanks in advance.

$\endgroup$
1
  • 1
    $\begingroup$ The Chinese Remainder Theorem also works for coprime numbers. They need not to be primes. $\endgroup$
    – Peter
    Jan 15, 2015 at 13:41

1 Answer 1

2
$\begingroup$

Actually, in this case the equation can be solved easily. Just use the fact that $$101^{1000} \mid x-3$$ $$7^{200} \mid x-3 $$ Because $\text{gcd}(101^{1000},7^{200}) = 1$, these two equations are equivalent with $$101^{1000}.7^{200} \mid x-3$$ So your solutions are all the numbers that bear this property.

$\endgroup$
3
  • $\begingroup$ I understand this. I knew this when asking the question. Isn't there a unique answer for the question? How would I go about finding it? $\endgroup$ Jan 15, 2015 at 14:50
  • $\begingroup$ I'm sorry, I don't think I understand your question. The answer I gave gives a necessary and sufficient condition. Or what do you want to know? $\endgroup$
    – Jef
    Jan 15, 2015 at 15:13
  • $\begingroup$ I want to know x that satisfies both congruences. So isn't a number modulo $101^{1000}.7^{200}$ $\endgroup$ Jan 15, 2015 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .