Proof
(related to Lemma: Coprimality and Congruence Classes)
- By hypothesis, $m$ is a positive integer and $a(m)$ is a given congruence class.
- Assume, we have two representatives $a_1,a_2$, i.e. $a_1(m)\equiv a_2(m).$
- By definition, this means $m\mid (a_1-a_2).$
- For any divisor $d\mid m$ we have by the divisibility law no. 3 that $d\mid (a_1-a_2).$
- By the divisibility law no. 9, this is equivalent to $d\mid a_1$ and $d\mid a_2.$
- Therefore, $d$ is a common divisor of $m,$ $a_1$ and $a_2.$
- Since the greatest common divisor is unique, it follows $\gcd(a_1,m)=\gcd(a_2,m).$
- In particular, this is true if $a_1\perp m$ and $a_1\perp m$ are co-prime, i.e. $\gcd(a_1,m)=\gcd(a_2,m)=1.$
- Therefore, any representative $a\in\mathbb Z$ of a given congruence class $a(m)\in\mathbb Z_m$ is either co-prime or not co-prime to $m.$
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
References
Bibliography
- Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
Footnotes
