3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Dylan May 15 '18 at 8:54
  • $\begingroup$ 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. $\endgroup$ – John Smith May 15 '18 at 22:46
6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$). $\endgroup$ – Erick Wong May 15 '18 at 22:28
  • 1
    $\begingroup$ 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. $\endgroup$ – John Smith May 15 '18 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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