Relative primes proof

50 Views Asked by At

I've already proven that if gcf$(ab,n) = 1$ then gcf$(a,n) = 1$ and gcf$(b,n) = 1$, by noting that 1 must be the smallest positive linear combination of $ab$ and $n$ and rewriting as linear combinations of $a,n$ and $b,n$.

But I'm having trouble with proving that given gcf$(a,n)=1$ and gcf$(b,n)=1$ then: $$\mbox{gcf}(ab,n) = 1$$

(Of course, by gcf I note the Greatest Common Factor and also I'm not too sure whether the term 'linear combination' exists as such, I'm translating from spanish.)

[Edit: I managed to come up with a solution: We can write 1 as the smallest positive linear combination of $(a,n)$ as: $ax + ny = 1$ and also for $(b,n)$ as: $br + ns = 1$. Then multiply these together to get: $$ab(xy)+n(ybr+sax+nys)=1$$ which is the smallest linear combination of $ab$ and $n$, so this must be the greatest common factor for $ab$ and $n$]

1

There are 1 best solutions below

1
On BEST ANSWER

hint: Recall that if $(a,n)=1$ then $\exists x,y\in\Bbb Z$ s.t. $ax+ny=1$