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

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.

• Hello @Y.Z. Can you please edit the question a bit? This will make it easier for the rest of us to read and follow your thoughts. This link explains how to use MathJax. – Ernie060 Nov 3 '18 at 19:58

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)$$.
$$(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.$$