Prove if $n\mid ab$, then $n\mid [\gcd(a,n) \times \gcd(b,n)]$

Question

Prove if $n\mid ab$, then $n\mid [\gcd(a,n)\times \gcd(b,n)]$

So I started by letting $d=\gcd(a,n)$ and $e=\gcd(b,n)$. Then we have $x,y,w,z$ so that $dx=a$, $ey=b$,$dw=ez=n$ and we also have $s$ so that $ns=ab$

or $ns=dexy$.

what I want is $n\mid de$, but I'm only getting to $n\mid de(xy)$ since I cannot prove that $s/(xy)$ is an integer.

Answer 1

By Bézout's theorem there are integers $\alpha,\beta,\gamma,\delta$ such that $\gcd(a,n)=\alpha a+\beta n$ and that $\gcd(b,n)=\gamma b+\delta n$. Therefore,$$\gcd(a,n)\times\gcd(b,n)=\alpha\gamma ab+\beta\gamma nb+\alpha\delta an+\beta\delta n^2.$$So, since $n\mid ab$, $n\mid\gcd(a,n)\times\gcd(b,n)$.

Answer 2

$(a,n)(b,n) = ((a,n)b,(a,n)n) = (ab,nb,an,nn) = \color{#c00}n(ab/n,\color{}{b,a,n})\,$ by GCD Distributive Law

Remark $ $ More generally $\,(\color{#0a0}{ab},\color{#c00}n)\mid (\color{#0a0}{ab},\color{#c00}n(a,b,n))=(a,n)(b,n)\ $ by above.

Using the distributive law (always true) yields a more general proof than using Bezout's gcd identity because not every gcd is writable as a Bezout linear combination, e.g. for polynomials in $\,x,y\,$ over a field we have $\, \gcd(x,y)=1\,$ but $1$ is not a linear combination of $\,x,y,\,$ else $\,x\,f(x,y)+y\,g(x,y)=1\Rightarrow 0=1\,$ by evaluating at $\,x=0=y.$