Register to reply 
Quick problem?by math_grl
Tags: None 
Share this thread: 
#1
Jan2411, 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]. 


#2
Jan2411, 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?



#3
Jan2411, 04:55 PM

P: 518

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^{pk}[/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 <= p1, 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. 


#4
Jan2411, 05:01 PM

P: 518

Quick problem?
Counterexample: binomial(4,2) = 6, which is not divisible by 4. 


#5
Jan2411, 06:15 PM

PF Gold
P: 1,059

In general for an odd prime: (a^pb^P) =(ab)(a^(p1)+(a^p2)b +a^(p3)(b^2)+++(a^0)b^(p1). Since there are p terms in the second expression and a==b Mod p was given, the second term goes to p(a^(p1))==0 Mod p.
In fact, for the above situation, we need only an odd integer, not a prime. 


#6
Jan2511, 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?



#7
Jan2511, 11:49 AM

P: 518

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. 


#8
Jan2511, 12:09 PM

P: 50




#9
Jan2511, 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) ? 


#10
Jan2511, 12:18 PM

P: 258

[tex]a^p\equiv\ a\ mod\ p\text{, and }b^p\equiv\ b\ mod\ p\ ==>\ a^pb^p\equiv\ ab\ mod\ p[/tex] it is always true only if p is prime or a carmichael number 


#11
Jan2511, 12:27 PM

P: 153

If I am not offbase 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. 


#12
Jan2511, 01:20 PM

P: 258

you can use the identity [tex]a^pb^p\equiv (ab)^P\ mod\ p[/tex]
of coursely if [tex]pab\ ==>\ a^pb^p\equiv\ 0\equiv\ (ab)^P\ mod\ p[/tex] if [tex]p \geq 2,\ pab ==> p^2p^p(ab)^p[/tex] now you can conclude that [tex]p^2a^pb^p[/tex] with some observation 


#13
Jan2711, 04:22 AM

P: 153

A trivial point, but...
Thank you, al mahed, for presenting in clear manner that which I was trying to get across in a less clear manner.  RF 


#14
Jan2711, 07:07 PM

PF Gold
P: 1,059

We know that (ab)^p ==a^pb^p Mod p. That is not the same as showing that (ab)^p ==a^pb^p Mod p^p, as you are suggesting above.
It is not the case that 10^73^7 is divisble by 7^7, in fact, 49 is the highest 7 divisor. 


#15
Jan2711, 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. 


#16
Jan2711, 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. 


#17
Jan2811, 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 


#18
Jan2811, 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 