查看“欧拉准则”的源代码

在[[数论]]中，[[二次剩余]]的'''歐拉判別法'''（又稱'''歐拉準則'''）是用来判定给定的[[整数]]是否是一个[[质数]]的[[二次剩余]]。

==叙述==

若<math>p</math>是奇[[質數]]且<math>p</math>不能整除<math>d</math>，則：

: <math>d</math>是模<math>p</math>的二次剩余[[当且仅当]]：

:: <math>d^{ \frac{p-1}{2}} \equiv 1 \pmod{p}</math>

: <math>d</math>是模<math>p</math>的非二次剩余当且仅当：

:: <math>d^{ \frac{p-1}{2}} \equiv -1 \pmod{p}</math>

以[[勒让德符号]]表示，即為：
<math>d^{ \frac{p-1}{2}} \equiv \left( \frac{d}{p}\right) \pmod{p}</math>

==举例==

===例子一：对于给定数，寻找其为二次剩余的模数===

令''a'' = 17。对于怎样的质数''p''，17是模''p''的二次剩余呢？

根据判别法里给出的准则，我们可以从小的质数开始检验。 

首先测试''p'' = 3。我们有：17<sup>(3 &minus; 1)/2</sup> = 17<sup>1</sup> &equiv; 2 (mod 3) &equiv; -1 (mod 3)，因此17不是模3的二次剩余。

再来测试''p'' = 13。我们有：17<sup>(13 &minus; 1)/2</sup> = 17<sup>6</sup> &equiv; 1 (mod 13)，因此17是模13的二次剩余。实际上我们有：17 &equiv; 4 (mod 13)，而2<sup>2</sup> = 4.

运用同余性质和[[勒让德符号]]可以加快检验速度。继续算下去，可以得到：
:对于质数''p'' =<math>13, 19, \cdots</math>，(17/''p'') = +1（也就是说17是模这些质数的二次剩余）。
:对于质数''p'' =<math>3, 5, 7, 11, 23, \cdots</math>，(17/''p'') = -1（也就是说17是模这些质数的[[二次剩余|二次非剩余]]）。

===例子二：对指定的质数''p''，寻找其二次剩余===

哪些数是模17的二次剩余？

我们可以手工计算：
: 1<sup>2</sup> = 1
: 2<sup>2</sup> = 4
: 3<sup>2</sup> = 9
: 4<sup>2</sup> = 16
: 5<sup>2</sup> = 25 &equiv; 8 (mod 17)
: 6<sup>2</sup> = 36 &equiv; 2 (mod 17)
: 7<sup>2</sup> = 49 &equiv; 15 (mod 17)
: 8<sup>2</sup> = 64 &equiv; 13 (mod 17)
 
于是得到：所有模17的二次剩余的集合是<math>{1,2,4,8,9,13,15,16}</math>。要注意的是我们只需要算到8，因为9=17-8，9的平方与8的平方模17是同余的：9<sup>2</sup> = (&minus;8)<sup>2</sup> = 8<sup>2</sup>  &equiv; 13 (mod 17).（同理不需计算比9大的数）。  

但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算3<sup>(17 &minus; 1)/2</sup> = 3<sup>8</sup> &equiv; 81<sup>2</sup> &equiv; ( &minus; 4)<sup>2</sup> &equiv; &minus; 1 (mod 17)，然后由欧拉准则判定3不是模17的二次剩余。

欧拉准则与[[高斯引理]]以及[[二次互反律]]有关，并且在定义[[欧拉-雅可比伪素数]]（见[[伪素数]]）时会用到。

==證明==
首先，由于<math>p</math>是一个奇素数，由[[费马小定理]]，<math>d^{p-1} \equiv 1 \pmod{p}</math>。但是<math>p-1</math>是一个偶数，所以有
:<math>(d^{ \frac{p-1}{2} } -1) \cdot (d^{ \frac{p-1}{2} }+1) \equiv 0 \pmod{p}</math>

<math>p</math>是一个素数，所以<math>d^{ \frac{p-1}{2} } -1</math>和<math>d^{ \frac{p-1}{2} }+1 </math>中必有一个是<math>p</math>的倍数。因此<math>d^{ \frac{p-1}{2} } </math>模<math>p</math>的余数必然是1或-1。

* 證明若<math>d</math>是模<math>p</math>的二次剩餘，則<math>d^{ \frac{p-1}{2}} \equiv 1 \pmod{p}</math>

若<math>d</math>是模<math>p</math>的二次剩餘，則存在<math>x^2 \equiv d \pmod{p}</math>，<math>p</math>跟<math>d,x</math>[[互質]]。根據[[費馬小定理]]得：

: <math>d^{ \frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod{p}</math>

* 證明若<math>d^{ \frac{p-1}{2} } \equiv 1 \pmod{p}</math>，則<math>d</math>是模<math>p</math>的二次剩餘

<math>p</math>是一个奇素数，所以关于<math>p</math>的[[原根]]存在。设<math>a</math>是<math>p</math>的一个[[原根]]，则存在<math>1 \le j \le p-1</math>使得<math>d=a^j</math>。于是 
:<math>a^{j \frac{p-1}{2} } \equiv 1 \pmod{p}</math>

<math>a</math>是<math>p</math>的一个[[原根]]，因此<math>a</math>模<math>p</math>的指数是<math>p-1</math>，于是<math>p-1</math>整除<math> \frac{ j(p-1) }{2} </math>。这说明<math>j</math>是一个偶数。令<math>i = \frac{j}{2}</math>，就有<math>(a^i)^2 =a^{2i} = d</math>。<math>d</math>是模<math>p</math>的二次剩余。

==參考资料==
* [http://grosz.math.txstate.edu/~dhaz/prob_sets/notes/node30.html#eqnnp12 Legendre Symbol]{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }}
*[http://www.math.ntu.edu.tw/msa/act/mathcamp/95page/lecture/K.doc 二次互反律]{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }}
*  潘承洞、潘承彪，《初等数论》，北京大学出版社。

==外部链接==
*[http://lxy.hztc.edu.cn/cdsl/wlkt/html/ch5/ch5_5.htm 参考证明(中文)]{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }}
[[Category:二次剩余]]