Thursday, August 11, 2016

elementary number theory - Prove by induction that $a-b|a^n-b^n$




Given $a,b,n \in \mathbb N$, prove that $a-b|a^n-b^n$. I think about induction. The assertion is obviously true for $n=1$. If I assume that assertive is true for a given $k \in \mathbb N$, i.e.: $a-b|a^k-b^k$, I should be able to find that $a-b|a^{k+1}-b^{k+1}$, but I can't do it. Any help is welcome. Thanks!


Answer



To complete the induction, note that



$a^{k + 1} - b^{k + 1} = a^{k + 1} - a^kb + a^kb - b^{k + 1} = a^k(a - b) + b(a^k - b^k), \tag{1}$



then simply observe that




$(a - b) \mid a^k(a - b), \tag{2}$



which is obvious, and that



$(a - b) \mid (a^k -b^k) \tag{3}$



by the induction hypothesis



$(a - b) \mid (a^k - b^k). \tag{4}$




Since $a - b$ divides both summands, it divides their sum.QED



Hope this helps. Cheerio,



and as always,



Fiat Lux!!!


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...