6
$\begingroup$

Show that $\gcd(a,bc)=1$ if and only if $\gcd(a,b)=1$ and $\gcd(a,c)=1$.

I am new at proofs and I think I should use Euclid's Lemma which states "If $p$ is a prime that divides $ab$, then $p$ divides $a$ or $p$ divides $b$. However, I am not sure how to create a concrete proof or argument.

Any hints or help would be greatly appreciated. Thanks!

$\endgroup$
8
$\begingroup$

One direction should be clear: If $a$ and $bc$ have no common factors greater than $1$, then certainly neither do $a$ and $b$ nor $a$ and $c$. If this is not quite clear, argue thus: If $q$ divides $c$, then $q$ divides $bc$. So, any common factor of $a$ and $c$ is also a common factor of $a$ and $bc$. Same with $b$ in place of $c$.

For the other direction, Bezout's lemma gives a nice argument. Note that if $m,n$ are integers, and there are integers $x$ and $y$ such that $mx+ny=1$, then $\mathrm{gcd}(m,n)=1$. This is because any common divisor of $m,n$, is also a divisor of $mx+ny$. The other direction also holds, and is the content of Bezout's lemma: If $\mathrm{gcd}(m,n)=1$, then there are integers $x,y$ with $mx+ny=1$.

Accordingly, fix integers $x,y,z,w$ such that $ax+by=1$ and $az+cw=1$. Multiply these two equations, to obtain $$ a(axz+xcw+byz)+bc(yw)=1. $$ The numbers $k=axz+xcw+byz$ and $l=yw$ are integers, and we have $ak+(bc)l=1$, so (as explained above), it follows that $\mathrm{gcd}(a,bc)=1$.

By the way, this idea of multiplying linear combinations given by Bezout allows us to prove many similar results. For example, if $\mathrm{gcd}(a,b)=1$, then also $\mathrm{gcd}(a^2,b^3)=1$, etc. (Several problems along these lines have been asked on the site before.)

$\endgroup$
3
$\begingroup$

For the part that if $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$:

Hint:

If $1=ax+by=au+cv$, then

$$1=(ax+by)(au+cv)=a(aux+cvx+byu)+bc(yv)$$

$\endgroup$
  • $\begingroup$ You used Bézout identity/lemma. By the way, the other part is easier: if $\gcd(a,bc)=1$, then there exist $s,t$ such that $a(s)+bc(t)=1$, i.e. $a(s)+b(ct)=1$, i.e. $a(s)+c(bt)=1$. $\endgroup$ – user236182 Sep 12 '17 at 14:25
0
$\begingroup$

The forward direction. gcd(a,bc) = 1 is postulated. Then there are integers x,y such that $ ax + (bc)y = 1.$

The fetch is to associate the terms $ ax + (bc)y = 1.$ in two ways, to apply Bezout's Identity to precipitate $gcd(a,b)$ and $gcd(a,c)$.

Group cy together to precipitate $ b, a(x) + b(cy) = 1 => gcd(a,b) = 1 $

Group by to precipitate $c, a(x) + (by)c = 1 => gcd(a,c) = 1. $


My proof of the backward direction is founded on https://math.stackexchange.com/a/673135. https://math.stackexchange.com/a/675887 is similar but doesn't color anything. I query the same thing as Bill Dubuque in his comment - I don't know why robjohn rearranges 'before multiplying the Bezout identities?, thence I don't do this.

But can someone please edify me? I want to know.

By reason of Bezout's Identity, there exist $x,y,u,v$ so that $\color{#C00000}{ax+by=1}$ and $\color{#00A000}{au+cv=1}$. The fetch is to multiply both these equations: $ \begin{align} \color{#C00000}{ (ax + by) }\color{#00A000}{ (au + cv) } &=\color{#C00000}{(1)}\color{#00A000}{(1)}\\ \color{magenta}{a}(axu + cv + buy)+\color{magenta}{bc}vy &= \end{align} $

By reason of Bezout's Identity again, the last equation conveys $(\color{magenta}{a},\color{magenta}{bc})=1$.

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