Results 1 to 3 of 3

Math Help - More on Congruence mod primes

  1. #1
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8

    More on Congruence mod primes

    Hi ... I'm going through the Zhao and Sun proof of "Some Curious Congruences Modulo Primes", and I'm stuck in several places, hehehe. In particular, I was wondering how the following congruence was shown.
    For i = 1,2,...,p-1

    \frac{(-1)^{i-1}}{p} \left(\begin{array}{cc}p\\i\end{array}\right) = \frac{(-1)^{i-1}}{i} \left(\begin{array}{cc}p-1\\i-1\end{array}\right) \equiv \frac{1}{i} \ (mod \ p)

    I get the equality part, no problem. But it's not so clear (for me) how the congruence can be shown. Any help would be great ... I'm learning quite a bit
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    The congruence is clearly true for p=2. Suppose p is odd. We have

    p-1\equiv-1\,(\bmod\,p)

    p-2\equiv-2\,(\bmod\,p)

    \vdots

    p-(p-i)\equiv-(p-i)\,(\bmod\,p)

    Hence

    i\cdot(i+1)\cdot\cdots\cdot(p-1)\equiv(-1)^{p-i}(p-i)!\,(\bmod\,p)\equiv(-1)^{i-1}(p-i)!\,(\bmod\,p)

    as p is odd. Therefore

    (p-1)!\equiv(-1)^{i-1}(i-1)!(p-i)!\,(\bmod\,p)


    \implies\ \frac{(-1)^{i-1}(p-1)!}{(i-1)!([p-1]-[i-1])!}\equiv1\,(\bmod\,p)

    and you can easily complete the proof from here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Ah, thank you ... I thought it was related to set congruences somehow, but I wasn't too sure how. I should have spotted that though, hehehe ... but still, I wouldn't claim the congruence right away, it's not that obvious to me
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence and Mersenne primes.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 11th 2010, 07:20 PM
  2. primes...
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 28th 2010, 06:53 PM
  3. Congruence Modulo Primes
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 11th 2009, 08:43 AM
  4. Primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 8th 2009, 02:26 PM
  5. primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2008, 01:21 AM

Search Tags


/mathhelpforum @mathhelpforum