• September 24th 2008, 02:26 AM
Kiwi_Dave
Can anyone point me in the direction of a proof for the generalisation of the Quadratic Reciprocity Law to the Jacobi Symbol?

Alternatively give me some pointers on how to prove it myself.
• September 24th 2008, 05:26 AM
ThePerfectHacker
Quote:

Originally Posted by Kiwi_Dave
Can anyone point me in the direction of a proof for the generalisation of the Quadratic Reciprocity Law to the Jacobi Symbol?

Alternatively give me some pointers on how to prove it myself.

If $a,b$ be two odd positive odd numbers >1.

We want to prove $(a/b)(b/a) = (-1)^{(a-1)/2\cdot (b-1)/2}$

Now let $a=p_1\cdot .... \cdot p_n$ and $b=q_1\cdot ... \cdot q_m$.

Therefore, $(a/b)(b/a) = \prod_{i=1}^n \prod_{j=1}^m (p_i/q_j)(q_j/p_i) = (-1)^{\sum_i \sum_j (q_i-1)/2\cdot(p_j-1)/2}$

It remains to prove,
$\sum_{i} \sum_j (q_i -1)/2\cdot (p_j -1)/2 \equiv (p_1...p_n -1)/2\cdot (q_1...q_m -1)/2 = (a-1)/2\cdot (b-1)/2$
• September 24th 2008, 08:20 PM
Kiwi_Dave
Quote:

Originally Posted by ThePerfectHacker
It remains to prove,
$\sum_{i} \sum_j (q_i -1)/2\cdot (p_j -1)/2 \equiv (p_1...p_n -1)/2\cdot (q_1...q_m -1)/2 = (a-1)/2\cdot (b-1)/2$

Thank's for the help. I can see the truth of the final congruence and will write my argument down. But is there a more susinct argument?

Each summand on the LHS contributes to the sum (mod 4) if none of the following statements are true:

$q_i\equiv 1$ (mod 4)
$p_j\equiv 1$ (mod 4)

That is they contribute iff
$p_j\equiv q_i\equiv 3$ (mod 4)

And the sum is equal to the number of contributions (mod 2). The number of p_j such that $p_j\equiv 3$ (mod 4) and the number of q_i such that $q_i\equiv 3$ (mod 4) must both be odd or the sum is zero (mod 2).

Now

$(p_1...p_n)\equiv 3^r$ where r is the number of p_j that equal 3 (mod 4). Therefore, $(p_1...p_n) \equiv 1$ if there are an even number of p_j that equal 3 (mod 4) and $(p_1...p_n) \equiv 3$ otherwise. In conclusion the sum is only non zero if $(p_1...p_n) \equiv 3$.

Similarly the sum is only non zero if $(q_1...q_m) \equiv 3$.

Now $(p_1...p_n-1)\cdot(p_1...p_n-1)/4\equiv 0$ if $(p_1...p_n)\equiv 1$ or $(q_1...q_m)\equiv 1$. Conversely $(p_1...p_n-1)\cdot(p_1...p_n-1)/4\equiv 1$ (mod 2) if $(p_1...p_n) \equiv 3$ and $(q_1...q_m) \equiv 3$.
• September 25th 2008, 09:09 AM
ThePerfectHacker
If $A,B$ are odd then $(AB-1)/2 \equiv (A-1)/2 + (B-1)/2 (\bmod 2)$. Proof: $(A-1)(B-1)\equiv 0(\bmod 4)$ thus $AB - A - B + 1 \equiv 0 (\bmod 4)$ and so $(AB-1) \equiv (A-1) + (B-1) (\bmod 4)$. Thus, $(AB-1)/2 \equiv (A-1)/2 + (B-1)/2 (\bmod 2)$.

Now generalize this by induction for $A_1,...,A_s$ i.e. $\sum_i (A_i -1)/2 \equiv (A_1...A_s-1)/2 (\bmod 2)$.

Thus, $\sum_i \sum_j (p_j-1)/2 \cdot (q_i -1)/2 \equiv (a-1)/2 \cdot \sum_j (p_j-1)/2 \equiv (a-1)/2\cdot (b-1)/2 (\bmod 2)$.