wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Prime congruence...
        
(Message started by: Michael_Dagg on Sep 17^th, 2007, 3:15pm)

Title: Prime congruence...
Post by Michael_Dagg on Sep 17^th, 2007, 3:15pm

With p prime, show that

(x + y)ⁿ = xⁿ + yⁿ (mod p) iff n is a power of p.

Title: Re: Prime congruence...
Post by pex on Sep 18^th, 2007, 1:29am

on 09/17/07 at 15:15:23, Michael_Dagg wrote:

With p prime, show that

(x + y)ⁿ = xⁿ + yⁿ (mod p) iff n is a power of p.

Really?

(1 + 2)⁵ = 1⁵ + 2⁵ (mod 3)

Title: Re: Prime congruence...
Post by Aryabhatta on Sep 18^th, 2007, 1:31am

I think he meant for all x,y...

Title: Re: Prime congruence...
Post by Barukh on Sep 18^th, 2007, 2:37am

I guess it may be shown by using this property (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1139008533;start=0#2).

Title: Re: Prime congruence...
Post by Michael_Dagg on Sep 18^th, 2007, 8:34am

It was meant as a polynomial congruence.

Title: Re: Prime congruence...
Post by JP05 on Sep 18^th, 2007, 6:40pm

I smell the binomial theorem. If you subtract the right from the left in that congruence you get
(x+y)^n - x^n - y^n = sum(k=1 to n-1) B(n,k) x^k y^(n-k), where B(n,k) is n!/(k!(n-k)!).

Pondering this I think I could come up with a method by contradiction if I spent more time with it since it must be that if n is not a power of p then not all of the B(n,k) are divisible by p.

I am thinking.

Title: Re: Prime congruence...
Post by Eigenray on Sep 18^th, 2007, 7:00pm

Remark: For each prime p, define

a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/preceq_p b <-> C(b,a) is not divisible by p.

It may be interesting to note that this is actually a partial order on the set of natural numbers. Personally, I find it even more interesting that this partial order is actually useful!

Edit: Here C(b,a) = (^bC_a) = {b \choose a} = b!/(a!(b-a)!) is a binomial coefficient.

Title: Re: Prime congruence...
Post by JP05 on Sep 18^th, 2007, 7:22pm

Eigenray I understand your left side of that relation as partial order but what do you mean by C(b,a)?

Title: Re: Prime congruence...
Post by JP05 on Sep 18^th, 2007, 11:22pm

Duh! Thanks. Your C(n,k) is my B(n,k).

Title: Re: Prime congruence...
Post by Michael_Dagg on Sep 19^th, 2007, 11:19am

> think I could come up with a method by contradiction

But that's not enough.