# Thread: Congruence Modulo Primes

1. ## 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.

$\displaystyle \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)$

$\displaystyle (\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.

2. Originally Posted by Bingk
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.

$\displaystyle \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$

$\displaystyle \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 $\displaystyle \Bigl(\frac{i}{3}\Bigr)(-1)^i$ is +1 if $\displaystyle i\equiv1\text{ or }2\!\!\! \pmod 6$, –1 if $\displaystyle i\equiv4\text{ or }5\!\!\! \pmod 6$, and 0 if $\displaystyle i\equiv3\!\!\! \pmod 6$. That explains why the values of $\displaystyle 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 $\displaystyle \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 $\displaystyle \Bigl(\frac{i}{3}\Bigr)(-1)^i$ will be +1 every time, and the sum becomes $\displaystyle \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 $\displaystyle \mathbb{Z}_5$ are respectively 1,3,2,4, so the above sum is equal to $\displaystyle 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.

3. 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 $\displaystyle \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

4. Hi, sorry ... I'm a little scatter brained, but shouldn't $\displaystyle \Bigl(\frac{i}{3}\Bigr)(-1)^i$ be -1 all the time, not +1.

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

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

I just wanted to make sure, since I'm not too familiar with Legendre ...

5. Originally Posted by Bingk
Hi, sorry ... I'm a little scatter brained, but shouldn't $\displaystyle \Bigl(\frac{i}{3}\Bigr)(-1)^i$ be -1 all the time, not +1.

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

For $\displaystyle i_1=2$ we have $\displaystyle \Bigl(\frac{2}{3}\Bigr)(-1)^2=(-1)(1)=-1$
That is correct. But for $\displaystyle i_1=4$ we have $\displaystyle \Bigl(\frac{4}{3}\Bigr)(-1)^4= \Bigl(\frac{1}{3}\Bigr)(-1)^4=(1)(1)=1$, and for $\displaystyle i_1=5$ we have $\displaystyle \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 $\displaystyle i_1\equiv1\text{ or }2\!\!\!\pmod6$ and –1 for $\displaystyle i_1\equiv4\text{ or }5\!\!\!\pmod6$, but in fact it's the other way round.)

6. 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)

7. Originally Posted by Bingk
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
$\displaystyle -1^{-1} -2^{-1} +4^{-1} +5^{-1} -7^{-1} -8^{-1} +10^{-1} = -1-6+3+9-8-7+10 = 0,$
and if p=13 it is
\displaystyle \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 $\displaystyle \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.

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