Monday, December 31, 2012
Ex 2.7 \(gcd(a,n) = gcd(b, n)\)
Let \(a,b,n \in \mathbb{Z}\) with \(n > 0\) and \(a \equiv b \pmod n\). Show that \(gcd(a, n) = gcd(b, n)\).
== Attempt ==
Given \(a \equiv b \pmod n\),
\(\mspace20pt\) \(a - b = y \cdot n \mspace10pt\) for some \(y \in \mathbb{Z}\)
Observe \(gcd(a, n)\) divides both the left hand side and right hand side. Therefore, \(gcd(a, n)\) must divide both \(b\) and \(n\), which means
\(\mspace20pt\) \(gcd(a, n) \le gcd(b, n)\)
Similar argument applies to \(gcd(b,n)\) which divides both sides, and therefore,
\(\mspace20pt\) \(gcd(b, n) \le gcd(a, n)\)
Thus, \(gcd(a, n) = gcd(b, n) \)
\(\Box\)
