Note: I've asked this question before, but this one offers a proposed solution and I'm checking for verification.

$a$ and $b$ are relatively prime if the greatest common divisor of them is $1$. I am given this fact:

  • $a, b ∈ N$ are relatively prime if and only if there exist integers $α, β$ such that $1 = α · a + β · b$

I used induction to attempt this proof. In the case $k = 1$, I get $(a^1 = a)$ and $b$ are relatively prime, which is given, so this case works. Next, I assumed the case holds for $k$, and now I want to prove that it holds for $k+1$. With my given fact, I can show this is true if I get $1 = α · a^{k+1} + β · b$ for some integers $α$ and $β$.

Because the formula holds for $k$, $1 = α' · a^k + β' · b$ (I used $α'$ and $β'$ to avoid confusion with the previous equality). Multiplying both sides by $α · a + β · b$, which equals $1$ because this is the true case where $k = 1$, I get $1 = (α · a + β · b)(α' · a^k + β' · b)$, which cleans up to $1 = (α'a)(a^{k+1}) + (α'a + β'αa^k + β'βb)(b)$. Everything in this expression is an integer, so I have $1 = $ an integer times $a^{k+1} + $ an integer times $b$, which means $a^{k+1}$ and $b$ are relatively prime by the given fact above.

Is this correct? Hopefully my algebra checks out.

  • 2
    $\begingroup$ Yes, this is correct! Here's the same proof, without induction: if $1=\alpha a+\beta b$, then $$1=(\alpha a+\beta b)^k = (\alpha^k) a^k + \bigg( \sum_{j=1}^k \binom kj \alpha^{k-j} a^{k-j} \beta^j b^{j-1} \bigg) b.$$ $\endgroup$ – Greg Martin Apr 25 '16 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.