Question

Prove the following statements using either direct or contrapositive proof. If \(a \equiv b(\bmod n),\) then \(\operatorname{gcd}(a, n)=\operatorname{gcd}(b, n)\).

Short answer

The statement is proven. Given \(a \equiv b (\bmod n)\), the greatest common divisor (or gcd) of \(a\) and \(n\) is indeed equal to the gcd of \(b\) and \(n\). This was shown by applying definitions and properties of congruence and gcd.

Step-by-step solution

Definition of Congruence

The first step is to understand exactly what the congruence modulo \(n\) means. By definition, \(a \equiv b (\bmod n)\) means that \(a - b\) is divisible by \(n\). In other words, there exists some integer \(k\) such that \(a - b = kn\). Now, we should show that the GCD of \(a, n\) equals the GCD of \(b, n\).

Applying the Definition of Congruence

Let's denote by \(d\) and \(d'\) the gcd of the pairs \((a,n)\) and \((b,n)\) respectively. So according to the definition of gcd, we have \(d|a\), \(d|n\), \(d'|b\), and \(d'|n\). It results that \(d|a-b\) and \(d'|a-b\). But since \(a-b=kn\), we can then deduce that \(d|kn\) and \(d'|kn\). Since \(d|n\), it results that \(d|k\). Doing exactly the same reasoning, we can conclude that \(d|k\).

Conclude the Proof

According to the definition of gcd, we can conclude that \(d'\) divides \(d\). And from the previous step we have deduced that \(d\) divides \(d'\). So we have \(d'=d\), and hence \(\operatorname{gcd}(a, n)=\operatorname{gcd}(b, n)\) as was to be proven.