Maths Olympiad Prep

Library / /233 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Theorem 5 Any two integers a1,a2a_{1}, a_{2} in a congruence class modulo mm have the same greatest common divisor with mm, i.e., (a1,m)=(a2,m)\left(a_{1}, m\right)=\left(a_{2}, m\right).

Solution

Proof: Let a1∈r mod m,a2∈r mod ma_{1} \in r \bmod m, a_{2} \in r \bmod m. By Theorem 1(i), we know aj=r+kjma_{j}=r+k_{j} m, j=1,2j=1,2. Then, by Theorem 8(iv) in Chapter 1 § 2, we get
(aj,m)=(r+kjm,m)=(r,m),j=1,2.\left(a_{j}, m\right)=\left(r+k_{j} m, m\right)=(r, m), \quad j=1,2 .

This completes the proof of the desired conclusion.

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.