I was just browsing for some small problems the other day and came across this problem and I am unsure if it should be obvious and have a quick answer. In any case, I couldn't figure it out. If [tex]p[/tex] is a prime that divides [tex]a - b[/tex], then show that [tex]p^2[/tex] divides [tex]a^p - b^p[/tex], where [tex]a, b \in \mathbb{Z}[/tex].
Nevermind I figured it out using binomial theorem. But it looked like to me that [tex]p[/tex] doesn't necessarily have to be prime. Am I correct?
I have a solution. Let a = b + n*p Then [itex]a^p - b^p = (b + np)^p - b^p = \sum_{k=1}^p \binom{p}{k} n^k p^k b^{p-k}[/itex] Let's now consider each of the terms. For k = p, then it's p^{p}, and since p >= 2, this is evenly divisible by p^{2}. For the remaining terms, 1 <= k <= p-1, and from that inequality, the binomial coefficient is divisible by p, p^{k} is also divisible by p, and thus, all these terms are divisible by p^{2}. Thus, all the terms are divisible by p^{2}, implying that the whole expression is also.
That's not the case. That is because binomial(n,k) for 1 <= k <= n-1 is always evenly divisible by n if n is a prime. For n composite, that need not be the case. Counterexample: binomial(4,2) = 6, which is not divisible by 4.
In general for an odd prime: (a^p-b^P) =(a-b)(a^(p-1)+(a^p-2)b +a^(p-3)(b^2)+++(a^0)b^(p-1). Since there are p terms in the second expression and a==b Mod p was given, the second term goes to p(a^(p-1))==0 Mod p. In fact, for the above situation, we need only an odd integer, not a prime.
robert, i like your expansion of a^p - b^p....but I'm afraid I don't understand why exactly it has to be an odd integer. Are you saying that there will not be p terms on the right hand side something if p is even? You started with p odd prime, does that mean the original question does not work for p = 2?
It's very easy to test. Let a = b + 2*k. I find a^{2} - b^{2} = (b+2*k)^{2} - b^{2} = 4*k^{2} + 4*k*b = 4*k*(k+b) 4 = 2^{2}, of course. ETA: robert Ihnot's argument will work for p being any integer >= 2.
Right that's what I thought, which is why I got confused when he said that we only need odd integers.
Forgive me if I am off here, but since we know that p divides a - b, then isn't this question essentially equivalent to stating, by Fermat's Little Theorem: Can... p (mod 2) divide a (mod p) - b (mod p)? p divides n*mod (p) for any n p divides a - b and p (mod 2) , which equals (or is congruent to..) 1, clearly divides a (mod p) - b (mod p) ?
I don't know exactly what you mean, but I think you're saying that if gcd(a,p)=gcd(b,p)=1, then by fermat [tex]a^p\equiv\ a\ mod\ p\text{, and }b^p\equiv\ b\ mod\ p\ ==>\ a^p-b^p\equiv\ a-b\ mod\ p[/tex] it is always true only if p is prime or a carmichael number
I believe the assumption here is that p is prime. Honestly, however, I was not necessarily thinking in terms of gcd, but, rather, in the case of p being prime, then the above statements ought to cover all cases (i.e. permutations) of how a, b, and p can combine. If I am not off-base here, one need only think about how p can "interact" with a - b, (a - b)(mod p) = n (mod p) & p(mod 2) can "interact" with a(mod p) - b(mod p). - RF P.S. Sorry, but the Latex editor does not work with my computer system.
you can use the identity [tex]a^p-b^p\equiv (a-b)^P\ mod\ p[/tex] of coursely if [tex]p|a-b\ ==>\ a^p-b^p\equiv\ 0\equiv\ (a-b)^P\ mod\ p[/tex] if [tex]p \geq 2,\ p|a-b ==> p^2|p^p|(a-b)^p[/tex] now you can conclude that [tex]p^2|a^p-b^p[/tex] with some observation
A trivial point, but... p > or = to 2 is unnecessary to state since all p, by common definition, are > or = to 2. Thank you, al mahed, for presenting in clear manner that which I was trying to get across in a less clear manner. - RF
We know that (a-b)^p ==a^p-b^p Mod p. That is not the same as showing that (a-b)^p ==a^p-b^p Mod p^p, as you are suggesting above. It is not the case that 10^7-3^7 is divisble by 7^7, in fact, 49 is the highest 7 divisor.
Hi Robert (see below post), I realize I completely reversed terms here in rather dyslexic manner and so, in response to your post, and in the interests of not virally spreading misinformation, I am simply replacing what I posted previously with my initial surmise, which I believe was of value.
p^2 divides p^(a - b), which is congruent to p^a - p^b. By Fermat's Litle Theorm, Modulus p. Fermat's Little Theorem says nothing about modulus P^2.
This is a weird coincidence since i was trying to solve a similar problem which is: Prove that if a ^ p + b ^p = 0 (mod p) then a ^ p + b ^p = 0 (mod p ^ 2) The logic is exactly similar i guess except that p as to be odd & greater than 2. Can somebody please look into & give me clues to solving the problem i posted a couple of days back with the subject line similar to "reduced residues" involving the Euler phi function? I would really appreciate it. Thanks in advance, -- Sachin
Robert, what you want to prove is: [tex]a^p\equiv\ b^p\ mod\ p^2[/tex] Fermat don't say nothing about p^2 modulo, but euler do, where did you see modulus p^p in my post?? generally, if I'm not mistaken, [tex]a^{p^e}-b^{p^e}\equiv\ (a-b)^{p^e}\ mod\ p^e[/tex]