I am given this statement: $a, b \in \mathbb{N}$ are relatively prime if and only if there exist integers $\alpha, \beta$ such that $1 = \alpha \cdot a + \beta \cdot b$.

I know that $\gcd(a^k,b) = 1$ means $a^k$ and $b$ are relatively prime, so if I use this to show $\gcd(a^{k+1}, b) = 1$ then I can prove this by induction.

When $k = 1$, $\gcd(a,b) = 1$ because $a$ and $b$ are relatively prime. So this works for $k = 1$.

Next, I'm assuming the formula holds $\gcd(a^k) = 1$ and now I have to show that $\gcd(a^{k+1}) = 1$.

Because $a^k$ and $b$ are relatively prime, $1 = \alpha \cdot a^k + \beta \cdot b$. I'm pretty sure if I can show that $1 = \alpha \cdot a^{k+1} + \beta \cdot b$, that would complete the proof. This is where I'm stuck.

  • 2
    $\begingroup$ If a prime $p$ divides $a^k$, then necessarily it divides $a$. $\endgroup$
    – neth
    Apr 13, 2016 at 3:40
  • $\begingroup$ Did you mean to write "Next, I'm assuming $\gcd(a^k, b) = 1$, and now I have to show that $\gcd(a^{k + 1}, b) = 1$"? $\endgroup$ Apr 13, 2016 at 10:02
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ Apr 13, 2016 at 10:07

1 Answer 1


Hint. You can do it without induction. If $$1=\alpha a+\beta b$$ then by the binomial theorem, $$1=[\alpha^k]a^k+\left[\binom k1\alpha^{k-1}a^{k-1}\beta+\binom k2\alpha^{k-2}a^{k-2}\beta^2b+\cdots+\binom k{k-1}\alpha a\beta^{k-1}b^{k-2}+\beta^kb^{k-1}\right]b\ ,$$ and the terms in square brackets are integers.

See if you can fill in the details.


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.