Saturday, May 13, 2017

elementary number theory - Proof : aequivbpmodnimpliesaiequivbipmodn




The congruence equation a\equiv b \pmod n \implies \exists k \in \mathbb{Z}, a -b = kn.
Taking the i-th power of both sides : (a -b)^i = k^in^i.




(a-b)(a-b)^{i-1}=k^in^i.
n\mid (a-b), (a-b) \mid (a-b)^i \implies n\mid (a-b)^i \implies \exists m \in \mathbb {Z}, (a-b)^i = mn.



But, my proof is incomplete, as it does not show still that a^i - b^i = kn.






All the comments and answer have ignored the fact that how to get the term a^i - b^i in the first place.
It seems that all have taken the approach to simply take the a^i- b^i=kn as a new equality, not derived from the original one. Just it uses the property of n \mid (a-b) of the original one.



Answer



It might be easier to use a = kn + b and the Binomial theorem. Then a^i = (kn+b)^i = \sum_{j=0}^i \binom{i}{j}(kn)^jb^{i-j}. All of these terms have a factor of n in them except for the 0^{th} one, so this equation may be written in the form a^i = pn + b^i. Hence the claim.


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