Prime Divisibility Property: Proving p^2 divides a^p - b^p for Integers a and b

[math_grl]

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 p is a prime that divides a - b, then show that p^2 divides a^p - b^p, where a, b \in \mathbb{Z}.

 

[math_grl]

Nevermind I figured it out using binomial theorem. But it looked like to me that p doesn't necessarily have to be prime. Am I correct?

 

[lpetrich]

I have a solution. Let a = b + n*p

Then
a^p - b^p = (b + np)^p - b^p = \sum_{k=1}^p \binom{p}{k} n^k p^k b^{p-k}

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

Thus, all the terms are divisible by p², implying that the whole expression is also.

 

[lpetrich]

Nevermind I figured it out using binomial theorem. But it looked like to me that p doesn't necessarily have to be prime. Am I correct?

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.

 

[robert Ihnot]

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.

 

[math_grl]

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?

 

[lpetrich]

It's very easy to test. Let a = b + 2*k. I find

a² - b² = (b+2*k)² - b² = 4*k² + 4*k*b = 4*k*(k+b)

4 = 2², of course.

ETA: robert Ihnot's argument will work for p being any integer >= 2.

 

[math_grl]

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.

 

[Raphie]

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)

?

 

[al-mahed]

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

a^p\equiv\ a\ mod\ p\text{, and }b^p\equiv\ b\ mod\ p\ ==&gt;\ a^p-b^p\equiv\ a-b\ mod\ p

it is always true only if p is prime or a carmichael number

 

[Raphie]

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.

 

[al-mahed]

you can use the identity a^p-b^p\equiv (a-b)^P\ mod\ p

of coursely if p|a-b\ ==&gt;\ a^p-b^p\equiv\ 0\equiv\ (a-b)^P\ mod\ p

if p \geq 2,\ p|a-b ==&gt; p^2|p^p|(a-b)^p

now you can conclude that p^2|a^p-b^p with some observation

 

[Raphie]

A trivial point, but...

if p \geq 2,\ p|a-b ==&gt; p^2|p^p|(a-b)^p

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

 

[robert Ihnot]

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.

 

[Raphie]

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.

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)

 

[robert Ihnot]

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.

 

[frowdow]

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

 

[Raphie]

Edit

 

[al-mahed]

Robert, what you want to prove is: a^p\equiv\ b^p\ mod\ p^2

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, a^{p^e}-b^{p^e}\equiv\ (a-b)^{p^e}\ mod\ p^e

 

[robert Ihnot]

you can use the identity a^p-b^p\equiv (a-b)^P\ mod\ p

of coursely if p|a-b\ ==&gt;\ a^p-b^p\equiv\ 0\equiv\ (a-b)^P\ mod\ p

if p \geq 2,\ p|a-b ==&gt; p^2|p^p|(a-b)^p

now you can conclude that p^2|a^p-b^p with some observation

Right above!

 

[robert Ihnot]

Robert, what you want to prove is: a^p\equiv\ b^p\ mod\ p^2

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, a^{p^e}-b^{p^e}\equiv\ (a-b)^{p^e}\ mod\ p^e

I would be helpful to give a reference or show a proof.

 

[robert Ihnot]

Here is a case for mod 9. Now since phi of 9 = 6, we need only raise these numbers to the cube, but if you like, use 9 instead of 3.

2^3+5^3 \equiv133\equiv7 Mod 9.
But 7^3\equiv 1 Mod 9.

 

[al-mahed]

my source is

http://planetmath.org/encyclopedia/FrobeniusAutomorphism4.html

 

[robert Ihnot]

The point of the situation with regards to p^2, is that, for example p=3, we have terms like 9!/(3!*6!) in the binominal expansion of (a+b)^9. In the mention term = 84, we have only 3, not 9, as a divisor.

Fermat's Little Theorm can be shown by induction: 1^p ==1, (x+1)^p ==x^p+1, but this is because all the intermediate terms in the binomial expansion contain p, a prime, which does not divide out. BUT THIS DOES NOT CARRY OVER TO P^2.

 

[al-mahed]

The point of the situation with regards to p^2, is that, for example p=3, we have terms like 9!/(3!*6!) in the binominal expansion of (a+b)^9. In the mention term = 84, we have only 3, not 9, as a divisor.

Fermat's Little Theorm can be shown by induction: 1^p ==1, (x+1)^p ==x^p+1, but this is because all the intermediate terms in the binomial expansion contain p, a prime, which does not divide out. BUT THIS DOES NOT CARRY OVER TO P^2.

yes, agreed, I know that, I didn't say the proof was complete, in fact I thought it would take only a few steps more, but that's not the case (I was trying to complete the proof here using what I've done, but gave me trouble, it is more complicated, I think)

 

[Raphie]

I come back to this statement as the one that I sense as key here, but can't put my finger on as to why...

p (mod 2) == 1, clearly divides a (mod p) - b (mod p)

We could not make a similar statement for p (mod 3), because, while we know that 1 divides any (a - b), and we also know, as a given, that p divides (a -b), we do not know that p (mod 3) divides any (a-b).

For example, let p (mod 3) = 2 (true if, for instance, p = 11, or any other prime of the form 6x - 1). Then if (a - b) is odd, 2 won't divide 11 or any other prime > 2 evenly.

These two statements in isolation...

p | n*mod (p) for any n
p | (a - b)

... if my initial instincts were correct, are not enough for a proof as per Robert's comments because they do not carry over to p^2. The "uniquety" of p (mod 2) == 1 and 1 | a (mod p) - b (mod p) needs to work in here somewhere. But, as I mentioned already, I can't say why.

 

[Landau]

@ralphie: a statement like "x divides a (mod p) - b (mod p)" does not make any sense to me. "x divides y" is defined for integers x and y (namely: y=kx for some integer k).

You are taking y to be 'a (mod p) - b (mod p)' which is not an integer, but an equivalence class of integers. So I'm not really sure what you mean by it.

 

[Landau]

(a+b)^p=a^p+b^p holds in the field \mathbb{F}_p of characteristic p=prime. This is sometimes called freshman's dream[/url].

 

[al-mahed]

(a+b)^p=a^p+b^p holds in the field \mathbb{F}_p of characteristic p=prime. This is sometimes called freshman's dream[/url].

yes, that's exactly what I told to Robert, see the link I pasted for him above

anyway ipetrich already closed the case quite elengantly at page 1

 

[Landau]

yes, that's exactly what I told to Robert, see the link I pasted for him above

Ah, I missed that, sorry.

 

[al-mahed]

Ah, I missed that, sorry.

don't worry

anyway, I was thinking on a similar problem, to prove (or disprove) the statement:p^5 never divides a^p+b^p, that is, the contrary proplem (a superior limit), ohh, and gcd(a,p)=(b,p)=1

 

[robert Ihnot]

Another way to approach this whole thing depends upon using the Taylor Theorem, but in a very truncated form. I will give an example:

F(x) = 2^5 + x^5 == 0. Mod 5. In this case, x=3. It is very easy to move to the case Modulus=25, which has already been show, first by lpetnich, and then by me: Using the Taylor method we arrive at:

F(x+hp) = F(x) +hpF'(x) +(hp)^2(F''(x)) ++++ But in this case we don't even need the term (hp)^2(F''(x)).

BUT since F'(x) =5x^4, we already have arrive at the p^2 = 25 situation, and we are left with just F(3) = 2^5+3^5 ==0 Mod 25.

However to give this proof some legitimacy, let's look at raising the example to Modulus 5^3 = 125, and using only the form 5kF'(x).
F(x+hp) = F(x) + hpF&#039;(x) \equiv 0 Mod 125.
hpF&#039;(3) \equiv -(2^5+3^5) Mod 125
Since F'(3) =5*3^4, and dividing out 25 from the numerator, we have: h=\frac{-2^5-3^5}{25*81} = -11/81=-1 Mod 5,.

Thus h=-1 and 3+(-1)*5 = =-2==123 Mod 125.

Thus moving up in p as an exponent, we have: 2^{25}+123^{25} \equiv 0 Mod 125.

But since again we get the simplist case as before for Mod 25, the above case works for
2^{25}+123^{25}\equiv 0 Mod 625.

While it might look pulling a rabbit out of the hat, if we always raise by F(x)+h(p^k)F'(x) Modulus p^(k+1), which would have been the normal expectation for a higher power,we get always the simplist case; so that nothing is need but to raise the exponent:2+3==0 Mod5. 2^5+3^5 == 0 Mod 25, 2^25+3^25 ==0 Mod 125, 2^125+3^125 ==0 Mod 625, 2^625+3^625 ==0 Mod 3125.

Remember all these cases involve division by powers of p, they do not handle the case (a-b)^(p^k)==a^(p^k)-b^(p^k) Mod p^(k), as the first part of the Freshman's Dream indicates. The last part of the Freshman's Dream is nothing but a generalization of Fermat's Little Theorem. I thought I handled that by indicating proof by induction 1^p==1 Mod p, (k+1)^p ==k^p + 1 Mod p, because all middle terms in the binominal expansion contain p. Thus x^p==x Mod p for the multiplicative group mod p.

 

[robert Ihnot]

Check me out page 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