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.

2. 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 $\displaystyle a,b$ be two odd positive odd numbers >1.

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

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

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

3. Originally Posted by ThePerfectHacker
It remains to prove,
$\displaystyle \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:

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

That is they contribute iff
$\displaystyle 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 $\displaystyle p_j\equiv 3$ (mod 4) and the number of q_i such that $\displaystyle q_i\equiv 3$ (mod 4) must both be odd or the sum is zero (mod 2).

Now

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

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

Now $\displaystyle (p_1...p_n-1)\cdot(p_1...p_n-1)/4\equiv 0$ if $\displaystyle (p_1...p_n)\equiv 1$ or $\displaystyle (q_1...q_m)\equiv 1$. Conversely $\displaystyle (p_1...p_n-1)\cdot(p_1...p_n-1)/4\equiv 1$ (mod 2) if $\displaystyle (p_1...p_n) \equiv 3$ and $\displaystyle (q_1...q_m) \equiv 3$.

4. If $\displaystyle A,B$ are odd then $\displaystyle (AB-1)/2 \equiv (A-1)/2 + (B-1)/2 (\bmod 2)$. Proof: $\displaystyle (A-1)(B-1)\equiv 0(\bmod 4)$ thus $\displaystyle AB - A - B + 1 \equiv 0 (\bmod 4)$ and so $\displaystyle (AB-1) \equiv (A-1) + (B-1) (\bmod 4)$. Thus, $\displaystyle (AB-1)/2 \equiv (A-1)/2 + (B-1)/2 (\bmod 2)$.

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

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