0
$\begingroup$

I need to solve the above simultaneous congruences, I have been told not to use Euclid's algorithm and that there's a 'trick' but I just can't see it.

Any pointers would be appreciated

$\endgroup$
  • $\begingroup$ Since $7^{1000}$ and $5^{200}$ are coprime you can use Chinese Reminder Theorem. $\endgroup$ – Konrad Szałwiński Jan 22 '14 at 15:02
1
$\begingroup$

$x = a \mod b$ is the same as saying that $(x - a) | b$. What can you say about $x - 5$ in this case? What numbers are possible for $x - 5$?

$\endgroup$
  • $\begingroup$ so $ x-5 = (5^{200}7^{1000})k $? I'm not really sure where to go from here (or is this sufficient as a solution?) $\endgroup$ – user123049 Jan 22 '14 at 15:26
  • $\begingroup$ This is correct. You should be able to express this equation in "mod" form once again (which I think is enough). $\endgroup$ – jwg Jan 22 '14 at 16:01
3
$\begingroup$

Observe that both $7^{1000}$ and $5^{200}$ divide $x-5$. Also, $gcd(7^{1000},5^{200})=1$.

$\endgroup$
0
$\begingroup$

$5^{200}$ and $7^{1000}$ divide $x-5$ and are coprime, hence their product also divide $x-5$ so we have that $x=5+k5^{200}7^{1000}$ for $k\in\mathbb{Z}$

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