1
$\begingroup$

Show that if $\gcd(a,b) = 1$ and $a|n$, $b|n$ then $ab|n$

What I have is as follows:

If $\gcd(a,b) = 1$ and $a|n$ and $a|n$ we know that:

$a=mn$ and $b=sn$ were $m,s \in \mathbb{Z}$

$ab|n = (mn)(sn)|n = n(ms)|n = \frac{(n)(ms)}{n} = ms$

This is were I am stuck. Im I done here or am I missing something?

$\endgroup$
2
  • 2
    $\begingroup$ In the body, you wrote $a|n$ twice where I think you meant $b|n$. Also, $a|n$ means $n=ka$, not $a=mn$ $\endgroup$
    – J. W. Tanner
    Feb 26, 2020 at 4:00
  • 2
    $\begingroup$ $a\mid n$ implies $n=am$, $\endgroup$
    – Alain Remillard
    Feb 26, 2020 at 4:10

1 Answer 1

Reset to default
3
$\begingroup$

Since $gcd(a,b)=1$ we have that $ar+bs=1$ for some integers $r,s$ (Bézout's identity)

Also, $a|n\implies ak=n$ for some $k\in\mathbb{Z}$and $b|n\implies bc=n$ for some $c\in\mathbb{Z}.$

If we multiply $ar+bs=1$ by $n$, we have $arn+bsn=n$, which looks complicated until we realize we can use $ak=bc=n$ to substitute into that equation, and rearrange into something that makes a tad more sense: $$arn+bsn=n$$ $$ar(bc)+bs(ak)=n$$ $$ab(rc)+ab(sk)=n$$ $$(ab)(rc+sk)=n$$ $$(ab)C=n$$ And the last line implies that $ab|n$, where $C=rc+sk\in\mathbb{Z}$.

$\endgroup$
2
  • $\begingroup$ More relevantly, $rc + sk \in \mathbb Z$. $\endgroup$
    – eyeballfrog
    Feb 26, 2020 at 4:57
  • $\begingroup$ oops, that's a typo. I'll fix that now. Thanks :) $\endgroup$
    – Hadi
    Feb 26, 2020 at 4:59

Not the answer you're looking for? Browse other questions tagged .