Show that if $a$, $b$, and $c$ are positive integers with $\gcd(a, b) = 1$ and $ab = c^n$, then there are positive integers $d$, and $e$ such that $a = d^n$ and $b = e^n$.

  • 3
    $\begingroup$ Have you considered the prime factorizations of $a$, $b$, and $c$? $\endgroup$ – Jon Feb 11 '11 at 15:03
  • $\begingroup$ 1=ax+by => 1=gcd(a^n,b^n) $\endgroup$ – kira Feb 11 '11 at 15:43
  • $\begingroup$ @kira: Please ask questions, don't give orders. Also: please make your titles informative, not sentence fragments. $\endgroup$ – Arturo Magidin Feb 11 '11 at 16:21
  • $\begingroup$ obvious assuming the fundamental theorem of arithmetic $\endgroup$ – yoyo Feb 11 '11 at 19:00
  • $\begingroup$ @kira: The title describes your problem exactly; why did you change it back to not having mark-up and to the old phrasing? $\endgroup$ – Arturo Magidin Feb 11 '11 at 19:46

Of course it is easy using existence and uniqueness of prime factorizations. Below is a more general proof using gcd's (or ideals) that has the benefit of giving an explicit closed form.

$ab=c^n \overset{\rm Lemma}\Rightarrow c=(a,c)(b,c) \,\Rightarrow\, ab = (a,c)^n(b,c)^n\Rightarrow \dfrac{a}{(b,c)^n}\! = \dfrac{(a,c)^n}b$ $\,\Rightarrow\begin{align} a &= (a,c)^n\\ b &= (b,c)^n\end{align}$

where the last inference uses Unique Fractionization [both fractions are irreducible by $(a,b)\!=\!1$]

Lemma $\ \ \color{#c00}{c\mid ab},\,\ \color{#0a0}{(a,b,c)=1}\ \Rightarrow \ c = (a,c)(b,c)\ [=\, (ab,c\color{#0a0}{(a,b,c)}) = (\color{#c00}{ab,c}) = c\,]$

Remark $ $ Alternatively $\ (a,c)^n\! = (a^n,c^n) = (a^n,ab) = a(a^n,b) = a$ and $\,(b,c)^n = b\,$ by symmetry where the first equality employs the Freshman's Dream.

As $ $ Weil remarks, $ $ this result can be viewed as the essence of Fermat's method of infinite descent. $ $ It generalizes to rings of algebraic integers but depends upon much deeper results in this more general context, viz. the finiteness of the class number and Dirichlet's unit theorem.


Been a while since I did any maths, so this is probably the wrong way of going about it. I'd take logs with base $a$ of $ab=c^n$, this will give: $$1 + \log_a(b) = n\log_a(c) \rightarrow 1 = n\log_a(c) - \log_a(b).$$ For the right hand side to equal 1, we need $b = e^n$ (this wouldn't necessarily be the case if $\gcd(a,b) \neq 1$): $$1 = n(\log_a(c) - \log_a(e)).$$ I'd take the inverse log from here, giving $a = \left(\frac{c}{e}\right)^n$. Simple to explain why $\frac{c}{e}$ must be a whole number, $d$.

Bet that's the worst possible solution to this problem


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.