Monday, 8 January 2018

Elementary Number Theory Congruence Proof




I’m stuck on the following number theory problem:




Let $a$ and $b$ be integers not divisible by the prime number p.



If $a^{\space p} \space \equiv \space b^{\space p} \space \pmod p,\;$ prove that $a^{\space p} \space \equiv \space b^{\space p} \space \pmod {p^2}.$




Not really sure how to attempt this. My first thought was to use FLT to simplify but that didn't work the way I wanted it to. Any suggestions or tips would be appreciated



Answer



At the heart this is really trivial, a consequence of $\rm\ f(x) = x^p\ \Rightarrow\ f{\:'}(x)\ =\ p\, x^{p-1} \equiv\ 0\:\ (mod\ p).\ $ First I give a simple proof, then I explain the viewpoint in terms of derivatives and multiple roots.



$\rm mod\ p\!:\,\ 0 \equiv a^p - b^p \equiv a-b,\:$ so $\rm\:p\mid a-b.\, $ So to show $\rm\ p^2\:|\:a^p\!-b^p = (a-b)\frac{a^p-b^p}{a-b}\,$ it suffices



$\rm to\ show\ that\ \ p\:|\:a-b\ \Rightarrow\ p\ \,\Big|\frac{a^p-b^p}{a-b}\: =\ a^{p-1}+a^{p-2}\:b+\:\cdots\:+a\:b^{p-2}+b^{n-1}$



$\rm But\ \ \ \ \ \ \ mod\,\ p\!: \ a\equiv b\ \ \ \Rightarrow\ \ \ \frac{a^p-b^p}{a-b}\ \equiv\ a^{p-1}+\:\cdots\:+a^{p-1} \equiv\, p\, a^{p-1}\equiv\, 0\quad $ QED



The prior line is the special case $\rm\ f = x^p,\ x = b\ $ of this polynomial Taylor series approximant:




$\rm\displaystyle\quad\quad\quad\quad\quad \frac{f(x)-f(a)}{x-a} \: \equiv\ f\:'(a)\ \ \ (mod\ \:x-a)\quad$ for $\rm\ f(x)\in \mathbb Z[x]$



$\qquad $ i.e. $\rm\quad\ f(x)\ =\ f(a) +\: f\:'(a)\ (x-a) \:+\: (x-a)^2\: g(x)\quad$ for some $\rm\ g(x) \in \mathbb Z[x]$



Therefore this result about numbers is just a special case of the following well-known result about functions (here polynomials): $ $ a root $\rm\ x = a\ $ of $\rm\ f(x)\ $ has multiplicity $\rm > 1\ \iff\ f\:'(a) \:=\: 0.\:$ In fact, like above, many results about numbers are actually specializations of results about functions. Moreover, because functions have richer structure than numbers - e.g. having derivatives available - we can exploit this structure in the function realm before specializing to numbers. A powerful example of this is Mason's ABC theorem - which has a trivial high-school level proof for polynomials, but is an unproven conjecture for numbers. It yields as a consequence a trivial proof of FLT for polynomials. The moral is: to prove a result about numbers, try to interpret it as special case of a result about functions.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...