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

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

==叙述==

若<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>

==举例==

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

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

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

首先测试<math>p=3</math>。我们有：<math>17^{\frac{3-1}{2}}=17^1\equiv 2\pmod{3}\equiv -1\pmod{3}</math>，因此17不是模3的二次剩余。

再来测试<math>p=13</math>。我们有：<math>17^{\frac{13-1}{2}}=17^6\equiv 1\pmod{13}</math>，因此17是模13的二次剩余。实际上我们有：<math>17\equiv 4\pmod{13}</math>，而<math>2^2=4</math>.

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

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

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

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

但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算<math>3^{\frac{17-1}{2}}=3^8\equiv 81^2\equiv (-4)^2\equiv -1\pmod{17} </math>，然后由欧拉准则判定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:包含证明的条目]]
[[Category:同余]]
[[Category:二次剩余]]
[[Category:数论中的平方]]
[[Category:素数定理]]