0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ernie060 Nov 3 '18 at 19:58
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ oh I get it its using that fact that n|n itself and n|ab at the same time $\endgroup$ – Y.Z. Nov 3 '18 at 20:13
  • $\begingroup$ Yes, that's it. $\endgroup$ – José Carlos Santos Nov 3 '18 at 20:18
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.