Product of 2 coprime $a$ and $b$ both less than $n$ and both coprime to $n$ can never be $xn$ where $x$ is any positive integer

Question

I am having trouble proving that product of two coprime $a$ and $b$ can never generate a number multiple of some greater number which is coprime to both $a$ and $b$.

Have you try reductio ad absurdum? It seems to me that if you could generate it, $a$ and $b$ would not be co-prime to $n$ at first place. — Pspl, Dec 26 '19 at 10:08

score 1 · Answer 1 · answered Dec 26 '19 at 10:51

Suppose that $ab=xn$, with your notation.

As $a$ is coprime with $n$ and $a|xn$, $a|x$, because $a$ or any divisor of $a$ cannot divide n. The same reasoning applies to $b$.

But now we have $ab=xn$ and $ab|x$. Thus, $ab=x$ and $n=1$, which is a contradiction (for example it would imply $a=b=0$).

score 1 · Accepted Answer · answered Dec 26 '19 at 11:07

1

We know that $n\mid xn.$ For $ab=xn$ , it follows that $n\mid ab$ . But we are given that $n\not\mid a,b$ , a contradiction.

Hence for coprimes $a,b$ it follows that $ab \ne xn.$

answered Dec 26 '19 at 11:07

The Demonix _ Hermit

3,478

What does | stands for? Sorry I don't know that. – Darshan Dec 26 '19 at 11:20
1

@darshan if $a$ divides $b$ , then we write it as $a\mid b$ , meaning that the number after $\mid$ is divisible by the number before $\mid.$ – The Demonix _ Hermit Dec 26 '19 at 11:22

Product of 2 coprime $a$ and $b$ both less than $n$ and both coprime to $n$ can never be $xn$ where $x$ is any positive integer

2 Answers2