Maths Olympiad Prep

Library / /490 of 520

Number theory Difficulty 7.3 National olympiad, round 2 Prove it

7. Prove: The system of congruences
{xa(modm1)xa(modm2)\left\{\begin{array}{ll} x \equiv a & \left(\bmod m_{1}\right) \\ x \equiv a & \left(\bmod m_{2}\right) \end{array}\right.

has all solutions
xa(mod{m1,m2})x \equiv a\left(\bmod \left\{m_{1}, m_{2}\right\}\right)

Solution

7. Proof: From xa(mod{m1,m2})x \equiv a\left(\bmod \left\{m_{1}, m_{2}\right\}\right), we know
{m1,m2}(xa)\left\{m_{1}, m_{2}\right\} \mid(x-a)

Since m1{m1,m2},m2{m1,m2}m_{1}\left|\left\{m_{1}, m_{2}\right\}, m_{2}\right|\left\{m_{1}, m_{2}\right\}, by Lemma 2 of Chapter 1, we have
m1(xa),m2(xa),xa(modm1),xa(modm2)\begin{array}{c} m_{1}\left|(x-a), \quad m_{2}\right|(x-a), \\ x \equiv a \quad\left(\bmod m_{1}\right), \quad x \equiv a \quad\left(\bmod m_{2}\right) \end{array}

This proves that xa(mod{m1,m2})x \equiv a\left(\bmod \left\{m_{1}, m_{2}\right\}\right) is a solution to the system of congruences xa(modm1)x \equiv a\left(\bmod m_{1}\right), xa(modm2)x \equiv a\left(\bmod m_{2}\right).

Conversely, suppose x0x_{0} is a solution to xa(modm1),xa(modm2)x \equiv a\left(\bmod m_{1}\right), x \equiv a\left(\bmod m_{2}\right). By the definition of congruence, we have
m1(x0a),m2(x0a)m_{1}\left|\left(x_{0}-a\right), \quad m_{2}\right|\left(x_{0}-a\right)

Therefore, by Lemma 9 of Chapter 1, {m1,m2}(x0a)\left\{m_{1}, m_{2}\right\} \mid\left(x_{0}-a\right), i.e.,
x0a(mod{m1,m2})x_{0} \equiv a\left(\bmod \left\{m_{1}, m_{2}\right\}\right)

Thus, xa(mod{m1,m2})x \equiv a\left(\bmod \left\{m_{1}, m_{2}\right\}\right) is the complete solution to the system of congruences xa(modm1)x \equiv a\left(\bmod m_{1}\right), xa(modm2)x \equiv a\left(\bmod m_{2}\right).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.