Legendre符号的定义和基本性质

2024-06-30 00:19| 来源: 网络整理| 查看: 265

索引定义意义若干性质 1. ( a p ) ≡ a p − 1 2 m o d p \left( \frac{a}{p} \right)\equiv { {a}^{\frac{p-1}{2}}}\text{ }\bmod p (pa)≡a2p−1 modp 2. ( 1 p ) = 1 \left( \frac{1}{p} \right)=1 (p1)=1 3. ( − 1 p ) = ( − 1 ) p − 1 2 = { 1 , p ≡ 1 m o d 4 − 1 , p ≡ 3 m o d 4 \left( \frac{-1}{p} \right)={ {\left( -1 \right)}^{\frac{p-1}{2}}}=\left\{ \begin{aligned} & 1,\text{ }p\equiv 1\text{ }\bmod 4 \\ & -1,\text{ }p\equiv 3\text{ }\bmod 4 \\ \end{aligned} \right. (p−1)=(−1)2p−1={ 1, p≡1 mod4−1, p≡3 mod4 4. a ≡ b m o d p ⇒ ( a p ) = ( b p ) a\equiv b\text{ }\bmod p\text{ }\Rightarrow \text{ }\left( \frac{a}{p} \right)=\left( \frac{b}{p} \right) a≡b modp ⇒ (pa)=(pb) 5-1. ( a b p ) = ( a p ) ( b p ) \left( \frac{ab}{p} \right)=\left( \frac{a}{p} \right)\left( \frac{b}{p} \right) (pab)=(pa)(pb) 5-2. ( a 1 a 2 ⋯ a n p ) = ( a 1 p ) ( a 2 p ) ⋯ ( a n p ) \left( \frac{ { {a}_{1}}{ {a}_{2}}\cdots { {a}_{n}}}{p} \right)=\left( \frac{ { {a}_{1}}}{p} \right)\left( \frac{ { {a}_{2}}}{p} \right)\cdots \left( \frac{ { {a}_{n}}}{p} \right) (pa1a2⋯an)=(pa1)(pa2)⋯(pan) 6. p ∣ b ⇒ ( a b 2 p ) = ( a p ) p\cancel{|}b\text{ }\Rightarrow \text{ }\left( \frac{a{ {b}^{2}}}{p} \right)=\left( \frac{a}{p} \right) p∣ b ⇒ (pab2)=(pa) 7. ( 2 p ) = ( − 1 ) p 2 − 1 8 = { 1 , p ≡ ± 1 m o d 8 − 1 , p ≡ ± 3 m o d 8 \left( \frac{2}{p} \right)={ {\left( -1 \right)}^{\frac{ { {p}^{2}}-1}{8}}}=\left\{ \begin{aligned} & 1,\text{ }p\equiv \pm 1\text{ }\bmod 8 \\ & -1,\text{ }p\equiv \pm 3\text{ }\bmod 8 \\ \end{aligned} \right. (p2)=(−1)8p2−1={ 1, p≡±1 mod8−1, p≡±3 mod8 8. 若 gcd ⁡ ( a , p ) = 1 , 2 ∣ a \gcd \left( a,p \right)=1,\text{ }2\cancel{|}a gcd(a,p)=1, 2∣ a，则有 ( a p ) = ( − 1 ) ∑ k = 1 p − 1 2 [ a k p ] \left( \frac{a}{p} \right)={ {\left( -1 \right)}^{\sum\limits_{k=1}^{\frac{p-1}{2}}{\left[ \frac{ak}{p} \right]}}} (pa)=(−1)k=1∑2p−1[pak] 9. 若 p , q p,q p,q均为奇素数， gcd ⁡ ( p , q ) = 1 \gcd \left( p,q \right)=1 gcd(p,q)=1（即奇素数 p ≠ q p \ne q p=q），则有 ( q p ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 ( p q ) \left( \frac{q}{p} \right)={ {\left( -1 \right)}^{\frac{p-1}{2}\centerdot \frac{q-1}{2}}}\left( \frac{p}{q} \right) (pq)=(−1)2p−1⋅2q−1(qp) 推论：设 p ≠ q p\ne q p=q都是奇素数，则有 ( q p ) = { ( p q ) , p ≡ 1 m o d 4 或 q ≡ 1 m o d 4 − ( p q ) , p ≡ 3 m o d 4 且 q ≡ 3 m o d 4 \left( \frac{q}{p} \right)=\left\{ \begin{aligned} & \left( \frac{p}{q} \right),p\equiv 1\text{ }\bmod 4\text{ }或\text{ }q\equiv 1\text{ }\bmod 4 \\ & -\left( \frac{p}{q} \right),p\equiv 3\text{ }\bmod 4\text{ }且\text{ }q\equiv 3\text{ }\bmod 4 \\ \end{aligned} \right. (pq)=⎩⎪⎪⎪⎨⎪⎪⎪⎧(qp),p≡1 mod4 或 q≡1 mod4−(qp),p≡3 mod4 且 q≡3 mod4 命题: 存在无穷多个素数 p p p，满足 p ≡ 1 m o d 4 p\equiv 1\text{ }\bmod 4 p≡1 mod4。

定义

p p p是一个奇素数， a ∈ Z a\in \mathbb{Z} a∈Z，定义 ( a p ) = { 1 , a 是模 p 的平方剩余且 p ∣ a − 1 , a 是模 p 的平方非剩余 0 , p ∣ a \left( \frac{a}{p} \right)=\left\{ \begin{aligned} & 1,\text{ }a是模p的平方剩余且p\cancel{|}a \\ & -1,\text{ }a是模p的平方非剩余 \\ & 0,\text{ }\left. p \right|a \\ \end{aligned} \right. (pa)=⎩⎪⎨⎪⎧1, a是模p的平方剩余且p∣ a−1, a是模p的平方非剩余0, p∣a 读作 a a a对 p p p的Legendre符号。该符号必须有圆括号；该符号不是分式的意思。

注 Legendre符号的定义也可以写作 ( a p ) = a p − 1 2 m o d p \left( \frac{a}{p} \right)={ {a}^{\frac{p-1}{2}}}\bmod p (pa)=a2p−1modp 其中 a p − 1 2 m o d p { {a}^{\frac{p-1}{2}}}\bmod p a2p−1modp表示用 p p p除 a p − 1 2 { {a}^{\frac{p-1}{2}}} a2p−1得到的余数 r ( r ∈ Z ≥ 0 , r < p ) r\left( r\in { {\mathbb{Z}}_{\ge 0}},\text{ }r{x}^{2}}\equiv a\equiv 0\text{ }\bmod p x2≡a≡0 modp 有唯一解 x ≡ 0 m o d p x\equiv 0\text{ }\bmod p x≡0 modp（ p p p是素数， Z / p {\mathbb{Z}}/{p}\; Z/p是域，是整环）。当 ( a p ) = − 1 \left( \frac{a}{p} \right)=-1 (pa)=−1时， a a a是模 p p p的平方非剩余，由平方非剩余的定义，同余式无解。

若干性质 1. ( a p ) ≡ a p − 1 2 m o d p \left( \frac{a}{p} \right)\equiv { {a}^{\frac{p-1}{2}}}\text{ }\bmod p (pa)≡a2p−1 modp

证明

若 p ∣ a p\cancel{|}a p∣ a，由于 p p p是一个素数，因此有 gcd ⁡ ( a , p ) = 1 \gcd \left( a,p \right)=1 gcd(a,p)=1。此时由Euler判别法和Legendre符号的定义，有 a 是模 p 的平方剩余 ⇒ { a p − 1 2 ≡ 1 m o d p ( a p ) = 1 ⇒ a p − 1 2 ≡ ( a p ) m o d p a 是模 p 的平方非剩余 ⇒ { a p − 1 2 ≡ − 1 m o d p ( a p ) = − 1 ⇒ a p − 1 2 ≡ ( a p ) m o d p \begin{aligned} & a是模p的平方剩余\text{ }\Rightarrow \text{ }\left\{ \begin{aligned} & { {a}^{\frac{p-1}{2}}}\equiv 1\text{ }\bmod p \\ & \left( \frac{a}{p} \right)=1 \\ \end{aligned} \right.\text{ }\Rightarrow \text{ }{ {a}^{\frac{p-1}{2}}}\equiv \left( \frac{a}{p} \right)\text{ }\bmod p \\ & a是模p的平方非剩余\text{ }\Rightarrow \text{ }\left\{ \begin{aligned} & { {a}^{\frac{p-1}{2}}}\equiv -1\text{ }\bmod p \\ & \left( \frac{a}{p} \right)=-1 \\ \end{aligned} \right.\text{ }\Rightarrow \text{ }{ {a}^{\frac{p-1}{2}}}\equiv \left( \frac{a}{p} \right)\text{ }\bmod p \\ \end{aligned} a是模p的平方剩余 ⇒ ⎩⎪⎨⎪⎧a2p−1≡1 modp(pa)=1 ⇒ a2p−1≡(pa) modpa是模p的平方非剩余 ⇒ ⎩⎪⎨⎪⎧a2p−1≡−1 modp(pa)=−1 ⇒ a2p−1≡(pa) modp

若 p ∣ a \left. p \right|a p∣a，由Legendre符号的定义有 ( a p ) = 0 \left( \frac{a}{p} \right)=0 (pa)=0 且此时有 a ≡ 0 m o d p a\equiv 0\text{ }\bmod p a≡0 modp，因此也有 a p − 1 2 ≡ 0 p − 1 2 = 0 m o d p { {a}^{\frac{p-1}{2}}}\equiv { {0}^{\frac{p-1}{2}}}=0\text{ }\bmod p a2p−1≡02p−1=0 modp 因此有 a p − 1 2 ≡ ( a p ) m o d p { {a}^{\frac{p-1}{2}}}\equiv \left( \frac{a}{p} \right)\text{ }\bmod p a2p−1≡(pa) modp

2. ( 1 p ) = 1 \left( \frac{1}{p} \right)=1 (p1)=1

证明 ( 1 p ) ≡ 1 p − 1 2 = 1 m o d p ( 1 p ) ∈ { 0 , ± 1 } } ⇒ ( 1 p ) = 1 \left. \begin{aligned} & \left( \frac{1}{p} \right)\equiv { {1}^{\frac{p-1}{2}}}=1\text{ }\bmod p \\ & \left( \frac{1}{p} \right)\in \left\{ 0,\pm 1 \right\} \\ \end{aligned} \right\}\text{ }\Rightarrow \text{ }\left( \frac{1}{p} \right)=1 (p1)≡12p−1=1 modp(p1)∈{ 0,±1}⎭⎪⎪⎪⎬⎪⎪⎪⎫ ⇒ (p1)=1

3. ( − 1 p ) = ( − 1 ) p − 1 2 = { 1 , p ≡ 1 m o d 4 − 1 , p ≡ 3 m o d 4 \left( \frac{-1}{p} \right)={ {\left( -1 \right)}^{\frac{p-1}{2}}}=\left\{ \begin{aligned} & 1,\text{ }p\equiv 1\text{ }\bmod 4 \\ & -1,\text{ }p\equiv 3\text{ }\bmod 4 \\ \end{aligned} \right. (p−1)=(−1)2p−1={ 1, p≡1 mod4−1, p≡3 mod4

【本文地址】

公司简介

联系我们