第一种证法是先证明 (a/p)×(p-1)! ≡-a^((p-1)/2) (mod p) 对任何奇素数和任何整数a都成立
引理:
如果p是素数，对任给的与p互素的整数a，和任给的满足1≤i≤p-1的整数i，都存在唯一一个整数j满足1≤j≤p-1 且 j×i≡a(mod p)
这是因为i, 2i, 3i, …, (p-1)i 这p-1个数全都和p互素
并且其中任意两个不同数mi和ni (假设m<n) 的差为(n-m)i , i与p互素，而1≤n-m≤p-2，所以n-m也与p互素，则(n-m)i≠0(mod p)
所以这p-1个数模p两两不同余，组成模p的既约剩余系，其中有且仅有一个j满足1≤j≤p-1且j×i≡a(mod p)

证明:
①当p ℓ a时，(a/p)×(p-1)!≡0≡-a^((p-1)/2) (mod p)
②当a N p时，由引理对任意i满足1≤i≤p-1，都存在唯一的j满足1≤j≤p-1且j×i≡a(mod p)
并且由于x²≡a(mod p)无解，所以j≠i(mod p)
则1~p-1 可以分为(p-1)/2对，每一对的乘积≡a(mod p)
所以(a/p)×(p-1)! ≡ -(p-1)!≡-a^[(p-1)/2] (mod p)
③当a R p时，存在x使1≤x≤p-1且x²≡a(mod p)，则(p-x)²≡a(mod p)也成立
由Lagrange定理x²≡a(mod p)最多只有两个模p不同的解，而x≠p-x(mod p)
所以对任何i满足1≤i≤p-1且i≠x, i≠p-x，i²≠a(mod p)
由引理, 对每个i存在唯一的j使得i×j≡a(mod p)，则j≠i (mod p)
因此剩下的(p-3)个数可以两两配成一对，每对的乘积≡a(mod p)
则 (a/p)(p-1)! ≡(p-1)!≡ x(p-x)a^[(p-3)/2] ≡-x²a^[(p-3)/2]≡-a^[(p-1)/2] (mod p)

其中a=1时，由于(1/p)=1，1^((p-1)/2)= 1，就得到(p-1)!≡-1(mod p)
再代入就得到 -(a/p)≡-a^((p-1)/2) (mod p)，也就是a^((p-1)/2)≡(a/p) (mod p)
这种方法同时也证明了Fermat小定理和Wilson定理

另一种证法:
引理1 : 若p为奇素数，当1≤k≤p-2时1^k+2^k+…+(p-1)^k ≡0(mod p)
江苏省2017复赛最后题目用到的，怎么证明...
引理2: 当p为奇素数，与p互素的模p的二次剩余正好有(p-1)/2个
这是因为1², 2², …, [(p-1)/2]² 这(p-1)/2个数全都是模p的二次剩余，并且都与p互素
而且对任何i, j满足1≤i < j≤(p-1)/2，j²-i²=(j+i)(j-i)，1≤j-i < j+i ≤p-2，所以j²-i²与p互素，j²≠i²(mod p)，它们两两模p不同余
而对任何满足a与p互素且a R p的整数a，存在x使x²≡a(mod p)，则(p-x)²≡a(mod p)也成立
由于a与p互素，则x也与p互素，总存在满足1≤x≤p-1的解，x 和 p-x 至少有一个在1~(p-1)/2 范围内，所以a 一定和1², 2², …, [(p-1)/2]²中的一个模p同余
说明与p互素的模p的二次剩余正好有(p-1)/2个

证明:
若p为奇素数，整数a与p互素，由费马小定理a^((p-1)/2) ²≡a^(p-1)≡1(mod p)
p 整除 a^((p-1)/2) ²-1 = (a^((p-1)/2)+1)(a^((p-1)/2)-1)
则要么p整除 a^((p-1)/2)+1，要么p整除a^((p-1)/2)-1，也就是 a^((p-1)/2)≡±1 (mod p)
假设一共存在k个不同的整数x 使得1≤x≤p-1且x^[(p-1)/2]≡-1(mod p)，则其余(p-1-k)个整数y满足 y^[(p-1)/2]≡1(mod p)
求和得到 (-1)×k + 1×(p-1-k)≡1^[(p-1)/2]+2^[(p-1)/2]+…+(p-1)^[(p-1)/2] (mod p)
因为p≥3, 则1≤(p-1)/2≤p-2，由引理1，右边≡0(mod p)
所以左边≡-2k-1≡0(mod p)，则k≡(p-1)/2(mod p)
而0≤k≤p，只可能k=(p-1)/2
所以满足x^[(p-1)/2]≡-1(mod p)且1≤x≤p-1的不同整数恰有(p-1)/2个
由引理2，正好存在(p-1)/2个不同整数y使1≤b≤p-1且b R p，对这些b，存在整数n使n²≡b(mod p)，n一定与p互素，所以由费马小定理 b^((p-1)/2)= n^(p-1)≡1(mod p)
假如存在某个与p互素的二次非剩余 a N p 满足a^[(p-1)/2]≡1(mod p)，则满足x^[(p-1)/2]≡-1(mod p)且1≤x≤p-1的不同整数个数不超过(p-1)-(p-1)/2-1 = (p-3)/2个，矛盾
所以对每个与p互素的二次非剩余a，a^[(p-1)/2]≡-1(mod p)都成立
再加上p ℓ a 时 a^[(p-1)/2]≡0≡(a/p) (mod p)，就得到a^[(p-1)/2]≡(a/p) (mod p)对任何整数a 恒成立

推论1 : 对奇素数p，Legendre符号(-1/p) = (-1)^[(p-1)/2]
如果奇素数p≡1(mod 4)，则 -1 R p
如果奇素数p≡3(mod 4)，则 -1 N p
推论2 : 对奇素数p和任何整数a, b，都有Legendre符号 (a/p)×(b/p) = (ab/p)