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.