ガウスの補題 (数論)
n は後者の範囲に属するような倍数 ka の個数を数え、このとき −ka は前者の範囲に入るから、
Z ≡ ( − 1 ) n ( | a | ⋅ | 2 a | ⋅ | 3 a | ⋅ ⋯ ⋯ | p − 1 2 a | ) {\displaystyle Z\equiv (-1)^{n}\left(|a|\cdot |2a|\cdot |3a|\cdot \cdots \cdots \left|{\frac {p-1}{2}}a\right|\right)}
となる。
さて値 |ra| が r = 1, 2, ..., (p − 1)/2 に対して相異なることを見る。実際、a は p と互いに素であるから、
| r a | ≡ | s a | ( mod p ) ⟹ r a ≡ ± s a ( mod p ) ⟹ r ≡ ± s ( mod p ) {\displaystyle {\begin{aligned}|ra|&\equiv |sa|{\pmod {p}}\\\implies ra&\equiv \pm sa{\pmod {p}}\\\implies r&\equiv \pm s{\pmod {p}}\end{aligned}}}
任意の奇素数 p に対して、a を p と互いに素な整数とする。
整数
a , 2 a , 3 a , ... , p − 1 2 a {\displaystyle a,\,2a,\,3a,\,\dots ,\,{\frac {p-1}{2}}a}
と、それらを p で割った(正の)余りを考える。(これらの余りはすべて相異なるので、全部で (p − 1)/2 個ある。)
その余りが p/2 よりも大きいものの個数を n とする。このとき
( a p ) = ( − 1 ) n {\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}
となる。ただし ( a p ) {\displaystyle \left({\frac {a}{p}}\right)} はルジャンドル記号である。