Results 1 to 8 of 8

Math Help - Congruence Modulo Primes

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

    Congruence Modulo Primes

    Hi, I was reading a thesis paper, and I guess I'm having problems with the notation.

    n is a positive odd integer and p > n+1, p is a prime.

    \sum_{0<i_1<\cdot\cdot\cdot<i_n<p}(\frac{i_1}{3})\  frac{(-1)^{i_1}}{i_1 \cdot\cdot\cdot i_n} \equiv 0\ (mod\ p)

    (\frac{i_1}{3}) is the Legendre symbol

    The above was given, but I can't get it to work ... and I think the indexes might be only those integers congruent to either 1 or 2 (mod 6), OR 4 or 5 (mod 6) (I got this part from reading the proof, you can read it at arxiv.org, do a math category search, journal reference 0904.1162, the title is "Some Curious Congruences Modulo Primes", by Li-Lu Zhao and Zhi-Wei Sun).

    I'm pretty sure I don't know enough to figure out what's going on, but it looked like an interesting thesis, and I wanted to try and figure it out ... so if you could guide me to some reading material (preferably free and online ), or explain the notation, and any limitations on the indexes, that would be great.

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Bingk View Post
    Hi, I was reading a thesis paper, and I guess I'm having problems with the notation.

    n is a positive odd integer and p > n+1, p is a prime.

    \sum_{0<i_1<\ldots<i_n<p}\Bigl(\frac{i_1}{3}\Bigr)  \frac{(-1)^{i_1}}{i_1 \cdots i_n} \equiv 0\!\!\! \pmod p

    \Bigl(\frac{i_1}{3}\Bigr) is the Legendre symbol

    The above was given, but I can't get it to work ... and I think the indexes might be only those integers congruent to either 1 or 2 (mod 6), OR 4 or 5 (mod 6)
    The expression \Bigl(\frac{i}{3}\Bigr)(-1)^i is +1 if i\equiv1\text{ or }2\!\!\! \pmod 6, 1 if i\equiv4\text{ or }5\!\!\! \pmod 6, and 0 if i\equiv3\!\!\! \pmod 6. That explains why the values of i_1 are treated that way in the paper.

    The simplest case that can arise (given that p is an odd prime and n has to be an odd integer) is when p=5 and n=3. We then have to form the sum \sum_{0<i<j<k<5}\Bigl(\frac{i}{3}\Bigr)\frac{(-1)^{i}}{ijk} \!\!\! \pmod 5. In this expression, there are four possible triples (ijk), namely (123), (124), (134), (234). In each case i, the smallest integer in the triple, is 1 or 2. So the value of \Bigl(\frac{i}{3}\Bigr)(-1)^i will be +1 every time, and the sum becomes \frac1{1\cdot2\cdot3} + \frac1{1\cdot2\cdot4} + \frac1{1\cdot3\cdot4} + \frac1{2\cdot3\cdot4} (evaluated mod 5). The inverses of 1,2,3,4 in the field \mathbb{Z}_5 are respectively 1,3,2,4, so the above sum is equal to 3\cdot2 + 3\cdot4 + 2\cdot4 + 3\cdot2 \cdot4 \equiv 1+2+3+4\equiv0 \!\!\! \pmod 5.

    So the result is correct in this case. As soon as the numbers p and n become larger, the number of terms in the sum gets too big for numerical verifications to be any fun.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Ah, okay ... thanks, that helped quite a bit. I thought the "fractions" are treated as common fractions . Inverses makes more sense though. Um, just a few extras ... how is \mathbb{Z}_5 a field? Scratch that question ... sorry, I forgot to use mod on it

    Thanks again, that really helped . Makes much more sense now, hehehe
    Last edited by Bingk; August 9th 2009 at 03:08 PM. Reason: Thought about it
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Hi, sorry ... I'm a little scatter brained, but shouldn't \Bigl(\frac{i}{3}\Bigr)(-1)^i be -1 all the time, not +1.

    For i_1=1 we have \Bigl(\frac{1}{3}\Bigr)(-1)^1=(1)(-1)=-1

    For i_1=1 we have \Bigl(\frac{2}{3}\Bigr)(-1)^2=(-1)(1)=-1

    I just wanted to make sure, since I'm not too familiar with Legendre ...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Bingk View Post
    Hi, sorry ... I'm a little scatter brained, but shouldn't \Bigl(\frac{i}{3}\Bigr)(-1)^i be -1 all the time, not +1.

    For i_1=1 we have \Bigl(\frac{1}{3}\Bigr)(-1)^1=(1)(-1)=-1

    For i_1=2 we have \Bigl(\frac{2}{3}\Bigr)(-1)^2=(-1)(1)=-1
    That is correct. But for i_1=4 we have \Bigl(\frac{4}{3}\Bigr)(-1)^4= \Bigl(\frac{1}{3}\Bigr)(-1)^4=(1)(1)=1, and for i_1=5 we have \Bigl(\frac{5}{3}\Bigr)(-1)^5= \Bigl(\frac{2}{3}\Bigr)(-1)^5=(-1)(-1)=1 (from which it is obvious that I made a mistake previously. I said it was +1 for i_1\equiv1\text{ or }2\!\!\!\pmod6 and –1 for i_1\equiv4\text{ or }5\!\!\!\pmod6, but in fact it's the other way round.)
    Last edited by Opalg; August 11th 2009 at 12:00 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Ah, okay ... thanks ...

    Also, it's kinda neat that the equality works ... I tried it with p=7 and n=5, still manageable, but the next prime is 11, and I think the fun would end there (unless we take n=1, which is kinda trivial)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Bingk View Post
    I tried it with p=7 and n=5, still manageable, but the next prime is 11, and I think the fun would end there (unless we take n=1, which is kinda trivial)
    I don't agree that the case n=1 is trivial. For example, if p=11 and n=1 then the sum becomes
    -1^{-1} -2^{-1} +4^{-1} +5^{-1} -7^{-1} -8^{-1} +10^{-1} = <br />
-1-6+3+9-8-7+10 = 0,
    and if p=13 it is
    \begin{aligned}-1^{-1} -2^{-1} &+4^{-1} +5^{-1} -7^{-1} -8^{-1} +10^{-1} +11^{-1} \\ &= -1-7+10+8-2-5+4+6\equiv0\!\!\!\pmod{13}.\end{aligned}

    In both cases the formula works, but in neither case is there an obvious underlying reason why this should be the case (as far as I can see).

    In fact, if you want to understand the paper by Zhao and Sun, it would probably be a very good exercise to go through their proof in the case n=1, in the hope that it would then become simpler and more transparent. More generally, this is an excellent strategy for approaching a difficult proof: try to find a special case in which the result becomes simpler without being totally trivial, and try to understand how the proof works in that case.

    So here is your homework for today. Prove the result \sum_{j=1}^{p-1}\Bigl(\frac j3\Bigr)(-1)^jj^{-1}\equiv0\!\!\!\pmod{p} (where p is an odd prime), by adapting and simplifying the argument given by Zhao and Sun.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    Ah, you're right ... it's not so trivial. But the calculations are simpler, since n=1, and we consider the inverses of 1/i, we basically get a summation (with negatives where appropriate) of some of the i's (the inverses of the i's that are multiples of 3 will go away since the Legendre is 0 for those cases). Somehow that summation becomes a multiple of p. I thought the combination of the negatives and the inverses would somehow make it go to zero always (for the case of n=1, but it doesn't )

    I'll work on that proof later , hehehe
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Modulo and congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 26th 2010, 05:10 PM
  2. Odd Primes with Modulo
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 18th 2009, 08:59 AM
  3. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 06:47 PM
  4. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 07:59 PM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 22nd 2007, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum