Thursday, April 14, 2016

elementary number theory - Why is $a^n - b^n$ divisible by $a-b$?



I did some mathematical induction problems on divisibility




  • $9^n$ $-$ $2^n$ is divisible by 7.

  • $4^n$ $-$ $1$ is divisible by 3.

  • $9^n$ $-$ $4^n$ is divisible by 5.




Can these be generalized as
$a^n$ $-$ $b^n$$ = (a-b)N$, where N is an integer?
But why is $a^n$ $-$ $b^n$$ = (a-b)N$ ?



I also see that $6^n$ $- 5n + 4$ is divisible by $5$ which is $6-5+4$ and $7^n$$+3n + 8$ is divisible by $9$ which is $7+3+8=18=9\cdot2$.



Are they just a coincidence or is there a theory behind?



Is it about modular arithmetic?



Answer



They are all special cases of the Factor Theorem: $\rm\: x-y\:$ divides $\rm\:f(x)-f(y),\:$ for $\rm\:f\:$ a polynomial with integer coefficients, i.e. $\rm\:f(x)-f(y) = (x-y)\:g(x,y)\:$ for a polynomial $\rm\:g\:$ with integer coefficients. The divisibility relation remains true when one evaluates the indeterminates $\rm\:x,y\:$ at integer values (this yields your examples if we let $\rm\:f(z) = z^n).$



Said simpler: $\rm\: mod\ x\!-\!y\!:\ \ x\equiv y\:\Rightarrow\: f(x)\equiv f(y)\ $ by the Polynomial Congruence Rule.



for example: $\ \rm\ mod\ 9\!-\!4\!:\ \ 9\equiv 4\:\Rightarrow\: 9^n\equiv 4^n$


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...