quick problem?


by math_grl
Tags: None
math_grl
math_grl is offline
#1
Jan24-11, 04:32 PM
P: 50
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].
Phys.Org News Partner Science news on Phys.org
NASA's space station Robonaut finally getting legs
Free the seed: OSSI nurtures growing plants without patent barriers
Going nuts? Turkey looks to pistachios to heat new eco-city
math_grl
math_grl is offline
#2
Jan24-11, 04:53 PM
P: 50
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?
lpetrich
lpetrich is offline
#3
Jan24-11, 04:55 PM
P: 514
I have a solution. Let a = b + n*p

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

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.

lpetrich
lpetrich is offline
#4
Jan24-11, 05:01 PM
P: 514

quick problem?


Quote Quote by math_grl View Post
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.
robert Ihnot
robert Ihnot is offline
#5
Jan24-11, 06:15 PM
PF Gold
P: 1,059
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
math_grl is offline
#6
Jan25-11, 10:51 AM
P: 50
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
lpetrich is offline
#7
Jan25-11, 11:49 AM
P: 514
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.
math_grl
math_grl is offline
#8
Jan25-11, 12:09 PM
P: 50
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
Raphie is offline
#9
Jan25-11, 12:12 PM
P: 153
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
al-mahed is offline
#10
Jan25-11, 12:18 PM
P: 258
Quote Quote by Raphie View Post
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
Raphie
Raphie is offline
#11
Jan25-11, 12:27 PM
P: 153
Quote Quote by al-mahed View Post
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
al-mahed is offline
#12
Jan25-11, 01:20 PM
P: 258
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
Raphie
Raphie is offline
#13
Jan27-11, 04:22 AM
P: 153
A trivial point, but...
Quote Quote by al-mahed View Post
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
robert Ihnot
robert Ihnot is offline
#14
Jan27-11, 07:07 PM
PF Gold
P: 1,059
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
Raphie is offline
#15
Jan27-11, 08:12 PM
P: 153
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.

Quote Quote by Raphie View Post
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
robert Ihnot is offline
#16
Jan27-11, 09:50 PM
PF Gold
P: 1,059
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
frowdow is offline
#17
Jan28-11, 04:35 AM
P: 4
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
Raphie is offline
#18
Jan28-11, 05:22 AM
P: 153
Edit


Register to reply

Related Discussions
I need some help on a quick UAM problem Introductory Physics Homework 0
Quick C++ problem Calculus & Beyond Homework 14
quick emf problem Introductory Physics Homework 2
Quick problem! Introductory Physics Homework 3