# If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. [duplicate]

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

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

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.

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

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?

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

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.

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$