证明:
对奇素数p 和与p互素的整数a，a, 2a, …, (p-1)/2×a 这(p-1)/2 个数全都与p互素
① 如果设这(p-1)/2 个数模p 的最小正剩余是 a₁, a₂, …, a[(p-1)/2]，其中存在λ个大于p/2
再设(p-1)/2个正整数b₁ 到b[(p-1)/2]，满足
若a[i]<p/2，则b[i]=a[i]，若a[i]>p/2，则b[i]= p-a[i]
那 b₁×b₂×…×b[(p-1)/2] ≡ (-1)^μ ×a₁×a₂×…×a[(p-1)/2] ≡ (-1)^μ× a^(p-1)/2 × [(p-1)/2] ! (mod p)

② 如果设i×a 和 j×a中不同的两个，满足1≤i<j≤(p-1)/2
则i×a - j×a =-(j-i)×a， j×a -i×a = (j-i)×a，j×a+i×a = (j+i)×a
由于 1≤j-i < j+i ≤p-2，所以j-i 和 j+i 都与p互素，而a也与p互素，则i×a - j×a，j×a -i×a 和 j×a+i×a 都不被p整除
所以对任何1≤i<j≤(p-1)/2，a[i]+a[j]≠0(mod p)，a[i]-a[j]≠0(mod p)
假设存在1≤i<j≤(p-1)/2 使b[i]≡b[j] (mod p)
如果b[i]=a[i], b[j]=a[j]，则a[i]≡a[j](mod p)，矛盾
如果b[i]=p-a[i], b[j]=a[j]，则a[i]+a[j]≡0(mod p)，矛盾
如果b[i]=a[i], b[j]=p-a[j]，则a[i]+a[j]≡0(mod p)，矛盾
如果b[i]=p-a[i], b[j]=p-a[j]，则a[i]≡a[j](mod p)，矛盾
所以对任何1≤i<j≤(p-1)/2 ，b[i]≠b[j](mod p)

③ 对任何i满足1≤i≤(p-1)/2
如果1≤a[i]<p/2，则1≤b[i]<p/2
如果p/2<a[i]≤p，由于a[i]和p互素，a[i]≤p-1，b[i]= p-a[i]，则1≤b[i]<p/2
所以每个b[i]都满足1≤b[i]≤(p-1)/2

综合②③，b₁,b₂, …, b[(p-1)/2]这(p-1)/2 个不超过(p-1)/2的正整数模p两两不同
所以它们组成的(可重复)集合{b₁, b₂, …, b[(p-1)/2]} = {1, 2, …, (p-1)/2}
所以 b₁×b₂×…×b[(p-1)/2] = [(p-1)/2] !
由于[(p-1)/2]! 和p互素，由①可得1≡(-1)^μ × a^[(p-1)/2] (mod p)
最后由欧拉准则 (a/p)≡a^[(p-1)/2] (mod p)可得(a/p)×(-1)^μ≡1(mod p)
也就是(a/p)≡(-1)^μ (mod p)
所以 (a/p) = (-1)^μ

推论: p为奇素数时Legendre符号(2/p) = (-1)^[(p²-1)/8]
当p≡1或7(mod 8)时 (2/p)= 1
当p≡3或5(mod 8)时 (2/p)= -1
这是因为
①当(p-1)/2 是奇数，(p+1)/2 是偶数时
2, 4, …, p-1 这(p-1)/2 个偶数中有 [(p-1) -(p-3)/2] /2 = (p+1)/4 个数 > p/2
则(2/p)= (-1)^(p+1)/4 = (-1)^[(p+1)(p-1)/8]
②当(p-1)/2 是偶数，(p+1)/2 是奇数时
2, 4, …, p-1 这(p-1)/2 个偶数中有 [(p-1) - (p-1)/2 ] /2 = (p-1)/4 个数 > p/2
则(2/p)= (-1)^(p-1)/4 = (-1)^[(p+1)(p-1)/8]

推论2 : 对奇素数p和与p互素的奇数a
令S(a, p)= ∑[a×i /p]，其中 i=1~(p-1)/2，[x]表示不超过x的最大整数
则 Legendre符号(a / p) = (-1)^S(a, p)
证明:
和2楼一样，对每个i 满足1≤i≤(p-1)/2，设a[i]表示a×i 模p的最小正剩余
若a[i]<p/2，则b[i]=a[i]，若a[i]>p/2，则b[i]=p-a[i]
每个a[i]都与p互素，那[a×i / p]= (a×i - a[i])/p
又因为5楼证明{b₁, b₂, …, b[(p-1)/2]} = {1, 2, …, (p-1)/2}
所以 p× S[a, p] = a× (1+2+…+(p-1)/2) - ∑a[i] = a ×∑b[i] -∑a[i]
因为存在μ个a[i]>p/2，对应的b[i]= p-a[i]，p为奇素数，所以对这些i，b[i]≡a[i]+1 (mod 2)
所以∑b[i]≡∑a[i]+ μ (mod 2)
而a 是奇数，a≡1(mod 2)
所以 S(a, p)≡p×S(a, p)≡∑b[i] - ∑a[i]≡μ (mod 2)
由引理 (a / p) = (-1)^μ = (-1)^S(a, p)