ในทฤษฎีจำนวนเกณฑ์ของออยเลอร์เป็นสูตรสำหรับตรวจสอบว่าจำนวนเต็ม นั้น เป็นเศษเหลือกำลังสองมอดูลของ จำนวนเฉพาะหรือ ไม่กล่าวคือ

ให้pเป็น จำนวน เฉพาะคี่และaเป็นจำนวนเต็มที่ไม่มีตัวหารร่วมกับpแล้ว^{[ 1 ] [ 2 ] [ 3 ]}

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {\begin{cases}\;\;\,1{\pmod {p}}&{\text{ if there is an integer }}x{\text{ such that }}x^{2}\equiv a{\pmod {p}},\\-1{\pmod {p}}&{\text{ if there is no such integer.}}\end{cases}}}$

เกณฑ์ของออยเลอร์สามารถกำหนดใหม่ได้อย่างกระชับโดยใช้สัญลักษณ์เลอจองเดอร์ : ^{[ 4 ]}

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}$

เกณฑ์ดังกล่าวมีที่มาจากเอกสารของLeonhard Eulerใน ปี 1748 ^{[ 5 ] [ 6 ]}

การพิสูจน์ใช้ข้อเท็จจริงที่ว่าชั้นเศษเหลือมอดูลจำนวนเฉพาะเป็นฟิลด์ดูบทความเรื่องฟิลด์จำนวนเฉพาะเพื่อดูรายละเอียดเพิ่มเติม

เนื่องจากค่าสัมบูรณ์เป็นจำนวนเฉพาะทฤษฎีบทของลากรองจ์จึงใช้ได้: พหุนามดีกรีk จะมี รากได้มากที่สุดk รากเท่านั้น โดยเฉพาะอย่าง ^ยิ่งx² ≡ a (mod p )จะมีคำตอบมากที่สุด 2 คำตอบสำหรับแต่ละaซึ่งหมายความโดยทันทีว่า นอกจาก 0 แล้ว ยังมีเศษเหลือกำลังสองที่แตกต่างกันอย่างน้อย p − 1/2 ค่า มอดูลัสp : แต่ละค่าที่เป็นไปได้ของx p − 1 ค่าจะมีเพียงค่าเดียวเท่านั้นที่ให้เศษเหลือเดียวกัน

ในความเป็นจริง,${\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}.}$เป็นเพราะว่า${\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.}$ ดังนั้น${\displaystyle {\tfrac {p-1}{2}}}$เศษกำลังสองที่แตกต่างกัน ได้แก่: ${\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.}$

เนื่องจากaเป็นจำนวนเฉพาะสัมพัทธ์กับp ทฤษฎีบทเล็กของแฟร์มาต์จึงกล่าวว่า

${\displaystyle a^{p-1}\equiv 1{\pmod {p}},}$

ซึ่งสามารถเขียนได้ดังนี้

${\displaystyle \left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.}$

เนื่องจากจำนวนเต็ม mod pเป็นฟิลด์ ดังนั้นสำหรับแต่ละaตัวประกอบตัวใดตัวหนึ่งในฟิลด์นี้จะต้องเป็นศูนย์ ดังนั้น

${\displaystyle a^{\tfrac {p-1}{2}}\equiv 1{\pmod {p}}}$หรือ

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {-1}{\pmod {p}}.}$

ถ้าa ^เป็นเศษเหลือกำลังสองa ≡ x²

${\displaystyle a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.}$

ดังนั้นเศษกำลังสองทุกตัว (mod p ) จะทำให้ตัวประกอบตัวแรกเป็นศูนย์

เมื่อนำทฤษฎีบทของลากรองจ์มาใช้อีกครั้ง เราจะพบว่ามีค่าของaที่ทำให้ตัวประกอบแรกเป็นศูนย์ได้ไม่เกิน p − 1/2 ค่า แต่ดังที่เราได้กล่าวไว้ในตอนต้น มีค่าตกค้างกำลังสองที่แตกต่างกันอย่างน้อยp − 1/2 ค่า( mod p ) ( นอกเหนือจาก 0 )ดังนั้น ค่าตกค้างเหล่านี้จึงเป็นค่าที่ทำให้ตัวประกอบแรกเป็นศูนย์ ส่วนค่าตกค้างอีกp − 1/2 ค่า ที่เหลือซึ่งไม่ใช่ค่าตกค้าง จะต้องทำให้ตัวประกอบที่สองเป็นศูนย์ มิฉะนั้นจะไม่สอดคล้องกับทฤษฎีบทเล็กของแฟร์มาต์ นี่คือเกณฑ์ของออยเลอร์

ตัวอย่างที่ 1: การหาจำนวนเฉพาะที่aเป็นเศษเหลือ

ให้a = 17 สำหรับจำนวนเฉพาะp ใดบ้าง ที่ 17 เป็นเศษเหลือกำลังสอง?

เราสามารถทดสอบ ค่า p ที่เป็นจำนวนเฉพาะ ได้ด้วยตนเอง โดยใช้สูตรข้างต้น

ในกรณีหนึ่ง เมื่อทดสอบp = 3 เราจะได้ 17 ^{(3 − 1)/2} = 17 ¹ ≡ 2 ≡ −1 (mod 3) ดังนั้น 17 จึงไม่ใช่เศษเหลือกำลังสองโมดูล 3

ในอีกกรณีหนึ่ง เมื่อทดสอบp = 13 เราจะได้ 17 ^{(13 − 1)/2} = 17 ⁶ ​​≡ 1 (mod 13) ดังนั้น 17 จึงเป็นเศษเหลือกำลังสองโมดูลัส 13 เพื่อเป็นการยืนยัน โปรดสังเกตว่า 17 ≡ 4 (mod 13) และ 2 ² = 4

เราสามารถคำนวณสิ่งเหล่านี้ได้เร็วขึ้นโดยใช้คุณสมบัติทางคณิตศาสตร์แบบโมดูลาร์และสัญลักษณ์เลอจองเดอร์ต่างๆ

ถ้าเราคำนวณค่าต่อไปเรื่อยๆ เราจะพบว่า:

(17/ p ) = +1 สำหรับp = {13, 19, ...} (17 คือเศษเหลือกำลังสองโมดูลัสของค่าเหล่านี้)

(17/ p ) = −1 สำหรับp = {3, 5, 7, 11, 23, ...} (17 ไม่ใช่เศษเหลือกำลังสองโมดูลัสของค่าเหล่านี้)

ตัวอย่างที่ 2: การหาเศษเหลือเมื่อกำหนดโมดูลัสเฉพาะp

จำนวนใดบ้างที่เป็นกำลังสองของเศษเหลือมอดูลัส 17 (เศษเหลือกำลังสองของเศษเหลือมอดูลัส 17)?

เราสามารถคำนวณด้วยตนเองได้ดังนี้:

1 ² = 1

2 ² = 4

3 ² = 9

4 ² = 16

5 ² = 25 ≡ 8 (mod 17)

6 ² = 36 ≡ 2 (mod 17)

7 ² = 49 ≡ 15 (mod 17)

8 ² = 64 ≡ 13 (mod 17)

ดังนั้นเซตของเศษกำลังสองมอดูล 17 คือ {1,2,4,8,9,13,15,16} โปรดสังเกตว่าเราไม่จำเป็นต้องคำนวณกำลังสองสำหรับค่า 9 ถึง 16 เนื่องจากค่าเหล่านั้นเป็นค่าลบของค่ากำลังสองก่อนหน้านี้ (เช่น 9 ≡ −8 (mod 17) ดังนั้น 9² ^≡ (−8) ^² = 64 ≡ 13 (mod 17))

เราสามารถหาเศษเหลือกำลังสองหรือตรวจสอบได้โดยใช้สูตรข้างต้น เพื่อทดสอบว่า 2 เป็นเศษเหลือกำลังสองมอดูล 17 หรือไม่ เราคำนวณได้ 2 ^{(17 − 1)/2} = 2 ⁸ ≡ 1 (mod 17) ดังนั้น 2 จึงเป็นเศษเหลือกำลังสอง เพื่อทดสอบว่า 3 เป็นเศษเหลือกำลังสองมอดูล 17 หรือไม่ เราคำนวณได้ 3 ^{(17 − 1)/2} = 3 ⁸ ≡ 16 ≡ −1 (mod 17) ดังนั้น 3 จึงไม่ใช่เศษเหลือกำลังสอง

เกณฑ์ของออยเลอร์มีความเกี่ยวข้องกับกฎการแลกเปลี่ยนกำลังสอง

ในทางปฏิบัติ การใช้อัลกอริทึมของยูคลิด แบบขยาย เพื่อคำนวณสัญลักษณ์จาโคบีนั้น มีประสิทธิภาพมากกว่า${\displaystyle \left({\frac {a}{n}}\right)}$. ถ้า${\displaystyle n}$เป็นจำนวนเฉพาะคี่ ซึ่งเท่ากับสัญลักษณ์เลอจองเดอร์ และเป็นตัวตัดสินว่า${\displaystyle a}$เป็นเศษเหลือกำลังสองโมดูลัส${\displaystyle n}$.

ในทางกลับกัน เนื่องจากความเท่าเทียมกันของ${\displaystyle a^{\frac {n-1}{2}}}$เงื่อนไขความสอดคล้องของสัญลักษณ์ Jacobi ใช้ได้กับจำนวนเฉพาะคี่ทั้งหมด แต่ไม่จำเป็นต้องใช้กับจำนวนประกอบ การคำนวณทั้งสองเงื่อนไขและเปรียบเทียบกันสามารถใช้เป็นการทดสอบความเป็นจำนวนเฉพาะได้ โดยเฉพาะอย่างยิ่งการทดสอบความเป็นจำนวนเฉพาะของ Solovay–Strassenจำนวนประกอบที่เงื่อนไขความสอดคล้องนี้ใช้ได้กับค่าที่กำหนด${\displaystyle a}$เรียกว่าจำนวนเฉพาะเทียมออยเลอร์-จาโคบีที่มีฐานเป็นจำนวนเฉพาะ เทียมออยเลอร์-จาโคบี${\displaystyle a}$.

• หอจดหมายเหตุออยเลอร์