2
$\begingroup$

This question already has an answer here:

If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$.
Also... $a,b$ and $n$ are natural numbers. I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from there...

$\endgroup$

marked as duplicate by Martin Sleziak, Cornman, YuiTo Cheng, Lee David Chung Lin, Lord Shark the Unknown May 4 at 6:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

Because $n$ is coprime to $a$ and $b$, we know there are linear combinations that equal one. Let the coefficients be $x,y,z,w$ such that $ax + ny = 1$ and $bz + nw = 1$. Multiply these together: $$abxz + axnw + bzny + n^2yw = 1 \cdot 1$$ $$ab(xz) + n(axw + bzy + nyw) = 1$$

So there's a linear combination of $ab$ and $n$ that is equal to $1$. Thus they are coprime.

$\endgroup$
  • $\begingroup$ Try not doing the whole problem. It sort of defeats the whole purpose, don't you think? $\endgroup$ – LASV Nov 30 '13 at 6:15
  • $\begingroup$ I usually don't. But this was pretty much what the OP stated already (use EEA and multiply the GCDs). $\endgroup$ – Henry Swanson Nov 30 '13 at 6:23
3
$\begingroup$

Hint: Suppose that $p$ is a prime divisor of $ab$ and of $n$; since $p$ is prime, it's necessarily true that $p \mid a$ or $p \mid b$. Can you take it from here?

$\endgroup$
  • $\begingroup$ Where did you get that p is a prime divisor of ab and n? Is that from coprimeness and divisibility? $\endgroup$ – user242743 Nov 30 '13 at 6:08
  • $\begingroup$ @user242743 I suppose that $p$ exists, intending a contradiction. $\endgroup$ – user61527 Nov 30 '13 at 6:08
  • $\begingroup$ Okay, I understand it now! Thanks. @T.Bongers $\endgroup$ – user242743 Nov 30 '13 at 6:10
2
$\begingroup$

In general gcd(a,n)=1 means there is no common divisor of a and n.. That is the composition multiples of a and n are different from each Other.. And gcd(b,n)=1 also gives the same result.. So now on multiplying a and b, there composition multiples will remain different from that of n. So gcd(ab,n)=1.. This is the simplest way to think about.

$\endgroup$
-1
$\begingroup$

There is a useful theorem for these kind of problems that says:

For $a,b \in \Bbb Z,a\neq 0, b\neq 0$ then $gcd(a,b)=1 \Leftrightarrow \exists m,n \in \Bbb Z : am+bn=1$

wich is not difficult to prove.

It is a useful exercise to prove or disprove this theorem when $gcd(a,b)=d$ and $am+bn=d$ where $d\ge 1$

$\endgroup$

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