# If $a, b \in \mathbb{N}$ are relatively prime, show that, for any $k \in \mathbb{N}$, $a^k$ and $b$ are relatively prime.

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.

• If a prime $p$ divides $a^k$, then necessarily it divides $a$. – neth Apr 13 '16 at 3:40
• 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$"? – N. F. Taussig Apr 13 '16 at 10:02
• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Apr 13 '16 at 10:07

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.