# 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 unique1, 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

1. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927

#### Footnotes

1. Any maximum (the $\gcd$ is a maximum, by definition) is unique, see notes on special elements of posets