1
$\begingroup$

Let $a, b$ and $n$ be natural numbers. Prove that if $a^n$ and $b^n$ are relatively prime, then $a$ and $b$ are relatively prime.

I have been able to prove the above statement by contrapositive in the following way: If $a$ and $b$ are not relatively prime, then $a^n$ and $b^n$ are not relatively prime.

Suppose $a$ and $b$ are not relatively prime. Then $\exists d \in \mathbb{N}$ such that $ d \vert a \wedge d \vert b $ where $d>1$.

Let $n \in \mathbb{N}$.

Since $$a^n = \overbrace{a\cdot a \dots \cdot a}^{n\text{-times}}$$ and $$b^n = \overbrace{b\cdot b \dots \cdot b}^{n\text{-times}}$$ then $$d \vert a^n \wedge d \vert b^n$$ which just implies that $a^n$ and $b^n$ are not relatively prime.

Could someone also show the direct proof?

$\endgroup$
  • 3
    $\begingroup$ Your proof is correct and it is 'direct'. $\endgroup$ – Kabo Murphy Mar 21 at 10:06
2
$\begingroup$

Since $\gcd(a^n,b^n)=1,\exists x,y\in\Bbb Z|a^nx+b^ny=1\implies a\cdot(a^{n-1}x)+b\cdot(b^{n-1}y)=1$.

Thus, $\exists p=a^{n-1}x,q=b^{n-1}y$, both integers, such that $ap+bq=1\implies\gcd(a,b)=1$.

$\endgroup$
0
$\begingroup$

Hint: If a prime $p$ divides the product $x=ab$, then it divides a factor, i.e., $p\mid a$ or $p\mid b$.

$\endgroup$
  • 1
    $\begingroup$ I think the asker is quite aware of this. $\endgroup$ – YFP Mar 21 at 10:08
0
$\begingroup$

$\,\cal P(n) := $ set of prime factors of $\,n.\,$ By unique factorization, $\,\cal \color{#c00}{P(a^k) = \cal P(a)}\,$ for $\,k\ge 1,\,$ so

$$\gcd(a,b)\!=\!1\!\iff\! \cal P(a)\cap \cal P(b) = \emptyset\color{#c00}\!\iff\! P(a^m)\cap \cal P(b^n) =\emptyset \!\iff\! \gcd(a^m,b^n)\! =\! \rm1,\ \,m,n\ge 1 $$

$\endgroup$

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.