Let $a,m,n, \in \mathbb{N}$. I want to show that if $a$ and $mn$ are relatively prime, then $a$ and $m$ are relatively prime.

To start us off, To say $a$ and $mn$ are relatively prime means that gcd($a,mn) = 1.$ I've tried using Bezout's Identity, but have not gotten anywhere. Also, can we assume that $a$ and $n$ are relatively prime?

• If you tried Bezout's Lemma, then I'm not sure what the difficulty was. We have that $ax + mny = 1$ for some integers $x$ and $y$. But then $ax + m(ny) = 1$, so if we rename $x$ to $s$, and $ny$ to $t$, then we see that there are integers $s$ and $t$ such that $as + mt = 1$, which implies that $a$ and $m$ are relatively prime. – Dylan May 15 '18 at 8:54
• The difficulty came from knowing what to do next (I should have written out the result on the body of the question.) It never occurred to me to re-label the terms like you did Dylan. – John Smith May 15 '18 at 22:46

Try the contrapositive: If $a$ and $m$ are not relatively prime, then $d=\gcd(a,m)>1$ and clearly $d$ divides both $a$ and $mn$, so $\gcd(a,mn)\ge d > 1$, and thus $a$ and $mn$ are not relatively prime.

Since Not B implies Not A is logically equivalent to A implies B, you are done.

Maybe you need to go more basic than Bézout's identity: every integer can be expressed as the product of two integers in at least one way. Though of course, for the primes, one of those two integers is a unit.

Then $m = st$ and $n = uv$, where $s, t, u, v$ are also integers. If $\gcd(a, m) > 1$, this means that $a$ must share a prime factor with $s$ or $t$.

For example, let's say $a = 14$, $m = 91$ and $n = 19$. We find that $\gcd(14, 1729) = 7$. Then we verify that $14 = 2 \times 7$ and $91 = 7 \times 13$.

Let's say that $a = 15$ instead, $m$ and $n$ remain the same. We find that $\gcd(15, 1729) = 1$ and also $\gcd(15, 91) = 1$ and $\gcd(15, 19) = 1$. Clearly 15 is not divisible by either 7 or 13. Quite obviously 15 is divisible by 1 (and also by $-1$ for that matter), but that's trivial. The important thing is that 15 is not divisible by 19, nor by $-19$.

• Is this really more basic than Bézout's identity? It needlessly invokes unique factorization (if $\gcd(a,st) > 1$ then $a$ must share a prime factor with $s$ or $t$). – Erick Wong May 15 '18 at 22:28
• It gets the job done, but yes, I don't believe this is more basic than applying Bézout's Identity. I will still upvote the answer. – John Smith May 15 '18 at 22:48