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

  • Thread starter math_grl
  • Start date
In summary, Robert found a solution to the problem that p does not have to be prime to divide a - b. However, he did not understand why it had to be an odd integer. Robert then showed that the assumption that p is prime is true if p is odd, and that the statement p^2|a^p-b^p covers all cases of how a, b, and p can combine.
  • #1
math_grl
49
0
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].
 
Physics news on Phys.org
  • #2
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?
 
  • #3
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 pp, and since p >= 2, this is evenly divisible by p2. For the remaining terms, 1 <= k <= p-1, and from that inequality, the binomial coefficient is divisible by p, pk is also divisible by p, and thus, all these terms are divisible by p2.

Thus, all the terms are divisible by p2, implying that the whole expression is also.
 
  • #4
math_grl said:
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?
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.
 
  • #5
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.
 
Last edited:
  • #6
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?
 
  • #7
It's very easy to test. Let a = b + 2*k. I find

a2 - b2 = (b+2*k)2 - b2 = 4*k2 + 4*k*b = 4*k*(k+b)

4 = 22, of course.

ETA: robert Ihnot's argument will work for p being any integer >= 2.
 
  • #8
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.
 
  • #9
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)

?
 
Last edited:
  • #10
Raphie said:
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

[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
 
  • #11
al-mahed said:
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.
 
Last edited:
  • #12
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
 
  • #13
A trivial point, but...
al-mahed said:
if [tex]p \geq 2,\ p|a-b ==> p^2|p^p|(a-b)^p[/tex]

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
 
  • #14
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.
 
Last edited:
  • #15
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.

Raphie said:
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)
 
Last edited:
  • #16
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.
 
  • #17
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
 
  • #18
Edit
 
Last edited:
  • #19
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]
 
  • #20
al-mahed said:
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

Right above!
 
  • #21
al-mahed said:
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]

I would be helpful to give a reference or show a proof.
 
  • #22
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.

[tex]2^3+5^3 \equiv133\equiv7 Mod 9.[/tex]
But [tex] 7^3\equiv 1 Mod 9.[/tex]
 
  • #23
my source is

http://planetmath.org/encyclopedia/FrobeniusAutomorphism4.html [Broken]
 
Last edited by a moderator:
  • #24
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.
 
  • #25
robert Ihnot said:
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)
 
  • #26
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.
 
Last edited:
  • #27
@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.
 
  • #28
(a+b)^p=a^p+b^p holds in the field [itex]\mathbb{F}_p[/itex] of characteristic p=prime. This is sometimes called [URL [Broken] freshman's dream[/url].
 
Last edited by a moderator:
  • #29
Landau said:
(a+b)^p=a^p+b^p holds in the field [itex]\mathbb{F}_p[/itex] of characteristic p=prime. This is sometimes called [URL [Broken] 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
 
Last edited by a moderator:
  • #30
al-mahed said:
yes, that's exactly what I told to Robert, see the link I pasted for him above
Ah, I missed that, sorry.
 
  • #31
Landau said:
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
 
  • #32
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).
[tex] F(x+hp) = F(x) + hpF'(x) \equiv 0 Mod 125. [/tex]
[tex] hpF'(3) \equiv -(2^5+3^5) Mod 125[/tex]
Since F'(3) =5*3^4, and dividing out 25 from the numerator, we have: [tex] h=\frac{-2^5-3^5}{25*81} = -11/81=-1 Mod 5, [/tex].

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

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

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

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.
 
Last edited:
  • #33
Check me out page 2.

frowdow said:
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
 

1. What is the Prime Divisibility Property?

The Prime Divisibility Property states that for any prime number p, p^2 will divide the difference of two numbers a and b raised to the power of p, meaning that p^2 is a factor of (a^p - b^p).

2. How is the Prime Divisibility Property proven?

The Prime Divisibility Property can be proven using mathematical induction. This involves showing that the property holds for a base case (usually p = 2) and then using the assumption that it holds for p = k to prove that it also holds for p = k+1.

3. Can the Prime Divisibility Property be extended to non-prime numbers?

No, the Prime Divisibility Property only applies to prime numbers. This is because the property relies on the fact that the prime number p cannot be factored into smaller prime numbers, making p^2 the smallest possible factor.

4. What are some practical applications of the Prime Divisibility Property?

The Prime Divisibility Property is used in various fields of mathematics, such as number theory and algebra. It also has applications in cryptography, where it is used to ensure the security of certain encryption algorithms.

5. Can the Prime Divisibility Property be generalized to higher powers?

Yes, the Prime Divisibility Property can be generalized to higher powers. In fact, it can be shown that for any positive integer k, p^k will divide (a^p - b^p) for any integers a and b. This is known as the Fermat's Little Theorem.

Similar threads

  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
761
  • Linear and Abstract Algebra
Replies
1
Views
623
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
Back
Top