# $x \equiv 5\: mod\: 7^{1000} , \: x \equiv 5\: mod \: 5^{200}$

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

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

$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$?
• 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?) – user123049 Jan 22 '14 at 15:26
Observe that both $7^{1000}$ and $5^{200}$ divide $x-5$. Also, $gcd(7^{1000},5^{200})=1$.
$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}$