ในทฤษฎีจำนวน ทฤษฎีบทของโพรธ ( Proth's theorem)เป็นทฤษฎีบทที่เป็นพื้นฐานของการทดสอบความเป็นจำนวนเฉพาะสำหรับจำนวนโพรธซึ่งรู้จักกันในชื่อการทดสอบของโพรธ (Proth's test ) จำนวนโพรธ หรือบางครั้งเรียกว่าจำนวนโพรธชนิดที่หนึ่ง (Proth Numbers of the First Kind ) คือจำนวนเต็มpที่มีรูปแบบp = k²n + 1 โดย ที่kเป็นจำนวนคี่ และk < ²ⁿสำหรับจำนวนโพรธชนิดที่สอง (Proth Numbers of the Second Kind) ^โปรดดูหัวข้อที่เกี่ยวข้องคือจำนวนรีเซล (Riesel numbers ) ทฤษฎีบทนี้ยังตั้งชื่อตามนักคณิตศาสตร์ชาวฝรั่งเศสและผู้เผยแพร่ทฤษฎีบทนี้คนแรก คือ ฟรองซัวส์ โพรธ ( François Proth)

ทฤษฎีบทระบุ ว่า ^{[ 1 ] [ 2 ]}สำหรับจำนวน Proth ใดๆ (ชนิดแรก) pแล้วpจะเป็นจำนวนเฉพาะถ้ามีจำนวนเต็มa อยู่ ซึ่งเกณฑ์ของออยเลอร์ให้ผลลัพธ์เป็น –1 นั่นคือ

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

ในกรณีนี้pเรียกว่าจำนวนเฉพาะโปรธ (Proth prime ) และข้อความแย้งก็เป็นจริงเช่นกัน: ถ้าpเป็นจำนวนประกอบโปรธ (Proth composite) แล้วจะไม่มีจำนวนa ดัง กล่าวอยู่

จำเป็นต้องหาค่าa เพียงค่าเดียวเท่านั้นเพื่อให้การทดสอบยืนยันความเป็นจำนวนเฉพาะได้อย่างแน่นอน โดยมีเงื่อนไขว่า pเป็นจำนวนโปรธ การตรวจสอบว่าpเป็นจำนวนโปรธนั้นเป็นเรื่องง่ายมาก

นี่เป็นการทดสอบเชิงปฏิบัติ เพราะถ้าpเป็นจำนวนเฉพาะ โอกาสที่ ค่า a ที่เลือกมา จะใช้ได้ผลมีประมาณ 50 เปอร์เซ็นต์ และถ้าpไม่ใช่จำนวน เฉพาะ ค่า a ที่เลือกมาทั้งหมดก็ จะใช้ไม่ได้ผล นอกจากนี้ เนื่องจากการคำนวณเป็นการหารด้วยโมดูลัส pจึงต้องพิจารณา เฉพาะค่าaที่น้อยกว่าp เท่านั้น

ถ้าpเป็นจำนวนประกอบของ Proth แล้ว ฐานa ใดๆ ก็ไม่ สามารถใช้เป็นพยานยืนยันความเป็นจำนวนเฉพาะได้ ถ้ามีฐานa ใดๆ สามารถใช้เป็นพยานยืนยันได้ ก็จะยืนยันความเป็นจำนวนเฉพาะได้ ถ้าไม่มีฐาน a ใดๆ สามารถใช้เป็นพยานยืนยันได้ ก็จะยืนยันความเป็นจำนวนประกอบได้ เนื่องจาก ทฤษฎีบท ผกผันของ Proth ก็เป็นจริงเช่นกัน:

ถ้าไม่มี จำนวน a ใดที่ทำให้และpเป็นจำนวนโปรธ แล้วpเป็นจำนวนประกอบ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$

ประโยคแย้งของ ข้อความ นี้คือ ถ้าpเป็นจำนวนเฉพาะ Proth ค่า a ดังกล่าว จะต้องมีอยู่แน่นอน

อันที่จริง ถ้าp เป็นจำนวนเฉพาะโปรธ เราคาดว่าค่า aประมาณครึ่งหนึ่งจะสอดคล้องกับความสอดคล้องในกรณีทั่วไป ในทางกลับกัน ถ้าเงื่อนไขที่สองไม่เป็นไปตามที่กำหนด – ถ้าpไม่ใช่จำนวนเฉพาะโปรธ – ก็ไม่สามารถรับประกันความเป็นจำนวนประกอบได้ (โดยทั่วไปแล้วสิ่งที่ตรงกันข้ามจะไม่เป็นจริงสำหรับจำนวนที่ไม่ใช่โปรธ) แม้ว่าเงื่อนไขแรกของความสอดคล้องจะเป็นไปตามที่กำหนดก็ตาม

ด้วยเหตุนี้ เราจึงสามารถตรวจสอบค่าฐานทั้งหมด [2, p − 1] อย่างเป็นระบบเพื่อยืนยันความเป็นจำนวนประกอบ (โปรดทราบว่าa = 0 และa = 1 จะใช้ไม่ได้ผล) จนกว่าจะพบค่าใดค่าหนึ่งที่ยืนยันความเป็นจำนวนเฉพาะ กระบวนการนี้ แม้จะเป็นวิธีที่ตรงไปตรงมาและง่ายที่สุด แต่ก็สามารถทำให้มีประสิทธิภาพมากขึ้นได้

โดยหลักการแล้ว เนื่องจากถ้าp เป็นจำนวนเฉพาะ โอกาสที่ค่า aที่เลือกจะพิสูจน์ความเป็นจำนวนเฉพาะนั้นมีประมาณ 50% เราจึงสามารถทำให้กระบวนการมีประสิทธิภาพมากขึ้นเล็กน้อยโดยการตรวจสอบค่า aประมาณครึ่งหนึ่งของค่าที่เป็นไปได้ทั้งหมดที่น้อยกว่าp เราคาดว่าครึ่งหนึ่งของค่าเหล่านั้นจะตรงตามเงื่อนไขความสอดคล้อง เมื่อตรวจสอบค่า a ที่แตกต่างกัน มากกว่าp /2 ค่าแล้วความเป็นจำนวนประกอบจะเป็นแบบกำหนดได้ เนื่องจากถ้าpเป็นจำนวนเฉพาะ เราคาดว่าครึ่งหนึ่งของฐานทั้งหมดจะให้หลักฐาน ตามหลักการรังนกพิราบเมื่อตรวจสอบมากกว่าครึ่งแล้ว เราสามารถสรุปได้ว่าไม่มีฐานใดให้หลักฐาน และถ้าไม่มีค่าฐานa ใดที่ใช้ได้ แสดงว่าpเป็นจำนวนประกอบ ในทางกลับกัน ถ้าp เป็นจำนวนเฉพาะ อย่างน้อยหนึ่งค่าที่ตรวจสอบแล้วจะต้องให้หลักฐานอย่างหลีกเลี่ยงไม่ได้ เช่นเดียวกับค่าที่เหลือทั้งหมดที่ยังไม่ได้ตรวจสอบ การทดสอบรูปแบบนี้คล้ายกับการ ทดสอบความเป็นจำนวนเฉพาะของแฟร์มาต์แบบกำหนดได้

วิธีการแบบง่าย ๆ ทั้งสองแบบนี้ไม่มีประสิทธิภาพอย่างมากและไม่เคยถูกนำมาใช้ในทางปฏิบัติ โปรดทราบว่าทั้งสองวิธีนี้ต้องใช้การคำนวณมากกว่าการหารแบบลองผิดลอง ถูกอย่างง่าย (วิธีของโรงเรียน) ในกรณีที่เลวร้ายที่สุดเสียอีก

เนื่องจากคาดว่า 50% ของฐานaจะยืนยันความเป็นจำนวนเฉพาะ ดังนั้นหากpเป็นจำนวนเฉพาะจริง เราสามารถสร้าง การทดสอบความน่าจะเป็นแบบ มอนเตคาร์โลได้ดังนี้: หากทำการทดสอบซ้ำm ครั้ง โดยแต่ละครั้งใช้ค่า aแบบสุ่มและแต่ละครั้งไม่สามารถยืนยันความเป็นจำนวนเฉพาะได้ เราอาจสรุปได้ว่าp น่าจะเป็น จำนวนประกอบ ซึ่งแตกต่างจาก ผลลัพธ์ ที่น่าจะเป็นจำนวนเฉพาะที่พบได้ทั่วไปในอัลกอริธึมมอนเตคาร์โลอื่นๆ เช่นการทดสอบมิลเลอร์-ราบิน นอกจากนี้ยังสามารถอนุมาน ความน่าจะเป็นของข้อผิดพลาดขอบเขตบนโดยประมาณε < 2 ^{− m}ที่จำนวนเฉพาะถูกระบุว่าเป็นจำนวนประกอบอย่างผิดพลาดได้ อย่างไรก็ตาม จำนวนประกอบจะไม่ถูกระบุว่าเป็นจำนวนเฉพาะอย่างผิดพลาดอย่างแน่นอน

การนำวิธีการเชิงความน่าจะเป็นนี้มาใช้โดยทั่วไปนั้นไม่ค่อยได้ใช้กัน แม้ว่าจะมีประสิทธิภาพมากกว่าการทดสอบแบบง่ายๆ ที่กำหนดผลลัพธ์ได้แน่นอน โดยมีประสิทธิภาพในการคำนวณเทียบเท่ากับการทดสอบของมิลเลอร์-ราบิน แต่ก็ยังสามารถปรับปรุงให้ดีขึ้นได้ทั้งในด้านประสิทธิภาพการทำงานและความแม่นยำ (หรือความแน่นอน)

สูตรการทดสอบของ Proth ในลาสเวกัสเป็นวิธีที่มีประสิทธิภาพที่สุดในบรรดาตัวเลือกต่างๆ และให้ผลลัพธ์ที่แน่นอนเทียบเท่ากับวิธีแบบกำหนดผลลัพธ์ตายตัว นี่คือวิธีที่นิยมใช้กันทั่วไป แม้ว่าจะมีรายละเอียดปลีกย่อยบางประการในวิธีการนำไปใช้ก็ตาม

ในทางปฏิบัติ จะพบค่าที่ไม่ใช่เศษกำลังสองของpและนำมาใช้เป็นค่าของaเนื่องจากถ้าaเป็นค่าที่ไม่ใช่เศษกำลังสองมอดูล pแล้วบทกลับของทฤษฎีบทของ Proth ก็จะเป็นจริงด้วย (ถ้าเกณฑ์ของ Euler ไม่ให้ค่า –1 แสดงว่าpเป็นจำนวนประกอบ) และการทดสอบก็จะสรุปได้ (แบบสองทิศทาง) อาจกล่าวได้ว่าทฤษฎีบทนี้กล่าวใหม่ได้ดังนี้:

สำหรับจำนวนโปรธp ทุกตัว และสำหรับค่าที่ไม่ใช่เศษกำลังสองa ใดๆ ของpนั้นpจะเป็นจำนวนเฉพาะก็ต่อเมื่อ${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$

ค่าที่ไม่ใช่เศษกำลังสองaของpสามารถระบุได้เมื่อสัญลักษณ์เลอจองเดอร์คือ –1 ดังนั้นสำหรับ ค่า a ดังกล่าว :

${\displaystyle \left({\frac {a}{p}}\right)=-1.}$

สำหรับค่าa ดังกล่าว การทดสอบจะให้ผลที่แน่นอนทั้งในเรื่องความเป็นจำนวนเฉพาะและความเป็นจำนวนประกอบ ดังนั้น สำหรับค่าa ดังกล่าว การตรวจสอบตามเกณฑ์ของ Proth/Euler จึงต้องการเพียงการวนซ้ำเพียงครั้งเดียวเท่านั้น ความสอดคล้องหรือไม่สอดคล้องกับ -1 นั้นบ่งบอกถึงความเป็นจำนวนเฉพาะได้อย่างสมบูรณ์ ความยากอยู่ที่การหาค่าaที่เหมาะสม

ค่าของaอาจหาได้โดยการตรวจสอบค่าอย่างเป็นระบบในช่วง [2, p − 1] ผ่านการเลือกและตรวจสอบแบบสุ่ม หรือโดยการคำนวณโดยตรงกว่า (ซึ่งมีประสิทธิภาพมากกว่า) เทียบกับสัญลักษณ์เลอจองเดอร์ ไม่ว่าในกรณีใด เมื่อค่าของaได้รับการตรวจสอบแล้วว่าตรงกับสัญลักษณ์เลอจองเดอร์และเป็นค่าที่เป็นไปได้ และดังนั้นจึงเป็นจำนวนกำลังสองที่ไม่เหลือเศษ ก็สามารถนำค่าดังกล่าวไปใช้ในเกณฑ์ของ Proth/Euler เพื่อตัดสินความเป็นจำนวนเฉพาะหรือจำนวนประกอบได้อย่างแน่ชัด

การตรวจสอบอย่างเป็นระบบโดยทั่วไปแล้วไม่ได้ไร้ประสิทธิภาพอย่างร้ายแรง ผู้สมัครค่อนข้างพบได้ทั่วไป และน่าจะพบได้ภายในไม่กี่ครั้ง ไม่ว่าpจะเป็นจำนวนเฉพาะหรือจำนวนประกอบก็ตาม แม้ว่าเศษเหลือกำลังสองจะพบได้ทั่วไปไม่ว่าpจะเป็นจำนวนเฉพาะหรือไม่ก็ตาม แต่ในทางทฤษฎีแล้ว เศษเหลือกำลังสองเหล่านี้จะหายากหรือไม่มีอยู่เลยเมื่อpเป็นจำนวนประกอบ เราสามารถสรุปได้อย่างแน่ชัดว่าpเป็นจำนวนประกอบหากไม่พบเศษเหลือกำลังสอง การค้นหาอย่างละเอียดถี่ถ้วนนั้นต้องใช้ทรัพยากรการคำนวณสูง

การเลือกแบบสุ่มก็ไม่ได้ไร้ประสิทธิภาพอย่างมากในกรณีทั่วไป ความน่าจะเป็นที่จะพบตัวเลือกที่เหมาะสมนั้นอยู่ที่ประมาณ 50% ต่อรอบ แม้ว่าการค้นหาด้วยวิธีนี้จะเป็นปัญหาเชิงความน่าจะเป็น แต่เมื่อพบแล้ว คำตอบจะเป็นแบบกำหนดได้ เราอาจอนุมานความเป็นองค์ประกอบเชิงความน่าจะเป็น (มอนเตคาร์โล) ด้วยระดับความเชื่อมั่น หากผ่านการเลือกแบบสุ่มแล้วไม่พบค่าที่ไม่ใช่เศษเหลือที่ตรงตามสัญลักษณ์เลอจองเดอร์ภายในจำนวนครั้งที่เหมาะสม แม้ว่าจะมีโอกาสที่ผลลัพธ์จะผิดพลาดอยู่เสมอซึ่งไม่ใช่ศูนย์ก็ตาม

ด้วยเหตุผลที่กล่าวมาข้างต้น โดยทั่วไปจึงใช้วิธีการคำนวณโดยตรงกว่าผ่านอัลกอริทึมแบบยุคลิดที่ดัดแปลงแล้ว .. เพื่อรับประกันการทดสอบที่แน่นอน (และมีประสิทธิภาพ) หากการคำนวณโดยตรงของค่าตกค้างกำลังสองล้มเหลว – เนื่องจากไม่มีอยู่จริง – ก็สามารถอนุมานความเป็นจำนวนประกอบได้ด้วยความแน่นอนอย่างสมบูรณ์

ดังนั้น เมื่อเปรียบเทียบกับการทดสอบความเป็นจำนวนเฉพาะแบบมอนเตคาร์โลหลายๆ วิธี (อัลกอริธึมแบบสุ่มที่อาจให้ผลบวกเท็จหรือผลลบเท็จ ) อัลกอริธึมการทดสอบความเป็นจำนวนเฉพาะแบบกำหนดได้นี้จึงเป็นอัลกอริธึมแบบลาสเวกัสซึ่งจะให้คำตอบที่ถูกต้องเสมอ แต่มีระยะเวลาการทำงาน ที่แปรผันแบบ สุ่ม

การตรวจสอบตามเกณฑ์ของ Proth ซึ่ง เป็นการดำเนินการ ยกกำลังแบบโมดูลาร์ อย่างง่าย เมื่อกำหนดค่าa แล้ว จะใช้เวลาในการทำงานประมาณความยาวบิตของ pดังนั้น ความผันแปรแบบสุ่มในเวลาการทดสอบโดยรวมจึงเป็นผลมาจากการค้นหา ค่า a ที่เหมาะสมเป็นหลัก ไม่ว่าจะทำได้ด้วยวิธีใดก็ตาม

เมื่อกำหนดเลขพรอธp = k 2 ⁿ + 1 แล้ว ได้มีการระบุรูปแบบเฉพาะของp , kและnที่สอดคล้องกับค่าที่ไม่ใช่เศษเหลือกำลังสองที่กำหนดไว้ล่วงหน้าซึ่งเหมาะสมสำหรับการใช้งาน และได้แสดงให้เห็นแล้วว่า:

• ถ้าและแล้วจะเป็นค่าที่ไม่ใช่เศษเหลือกำลังสอง (ผู้สมัคร) เสมอ และด้วยเหตุนี้จึงเป็นฐานที่ถูกต้องในการตรวจสอบ และดังนั้น:${\displaystyle p>3}$${\displaystyle 3\nmid k}$${\displaystyle a=3}$

${\displaystyle 3^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$ก็ต่อเมื่อpเป็นจำนวน เฉพาะเท่านั้น

นี่คือพื้นฐานของการทดสอบของเปแปงสำหรับจำนวนแฟร์มาต์และจำนวนเฉพาะที่สอดคล้องกัน โดยที่k = 1 หารด้วย 3 ไม่ลงตัว

• ถ้าp เป็น 3 หรือ 5 มอดูล 8 แล้ว จะเป็น ค่าที่ไม่ใช่เศษเหลือกำลังสอง (ตัวเลือก) เสมอ และดังนั้นจึงเป็นฐานที่ถูกต้องที่จะตรวจสอบ และด้วยเหตุนี้:${\displaystyle p>8}$${\displaystyle a=2}$

${\displaystyle 2^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$ก็ต่อเมื่อpเป็นจำนวน เฉพาะเท่านั้น

• ถ้าp เป็น 2 หรือ 3 มอดูล 5 แล้ว จะเป็น ค่าที่ไม่ใช่เศษเหลือกำลังสอง (ตัวเลือก) เสมอ และดังนั้นจึงเป็นฐานที่ถูกต้องที่จะตรวจสอบ และด้วยเหตุนี้:${\displaystyle p>5}$${\displaystyle a=5}$

${\displaystyle 5^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$ก็ต่อเมื่อpเป็นจำนวน เฉพาะเท่านั้น

แม้ว่าจะไม่มีกฎง่ายๆ เช่นนั้นสำหรับกรณีที่pเป็น 1 หรือ 4 มอดูล 5 แต่ในกรณีหลัง 4 มอดูล 5 นั้น เราสามารถเพิ่มโอกาสในการค้นหาตัวเลือกที่ไม่ใช่เศษเหลือที่เป็นกำลังสองได้อย่างเป็นระบบโดยการตรวจสอบค่าในบริเวณใกล้เคียงแคบๆ ของรากที่สองที่แตกต่างกันสองค่าของ 5 มอดูล pหากไม่มีรากที่สองที่แตกต่างกันสองค่าอย่างแน่นอน (ดูอัลกอริทึม Tonelli-Shanks ) แสดงว่าpไม่ใช่จำนวนเฉพาะ การคำนวณค่าที่ไม่ใช่เศษเหลือโดยตรงน่าจะมีประสิทธิภาพมากกว่า

ตัวอย่างของทฤษฎีบทนี้ได้แก่:

• สำหรับp = 3 = 1(2 ¹ ) + 1 เราจะได้ว่า 2 ^(3−1)/2 + 1 = 3 หารด้วย 3 ลงตัว ดังนั้น 3 เป็นจำนวนเฉพาะ
• สำหรับp = 5 = 1(2 ² ) + 1 เราจะได้ว่า 3 ^(5−1)/2 + 1 = 10 หารด้วย 5 ลงตัว ดังนั้น 5 จึงเป็นจำนวนเฉพาะ
• สำหรับp = 13 = 3(2 ² ) + 1 เราจะได้ว่า 5 ^(13−1)/2 + 1 = 15626 หารด้วย 13 ลงตัว ดังนั้น 13 เป็นจำนวนเฉพาะ
• สำหรับp = 9 ซึ่งไม่ใช่จำนวนเฉพาะ จะไม่มีค่า aใดๆ ที่ทำให้a ^(9−1)/2 + 1 หารด้วย 9 ลงตัว

ข้อเท็จจริงที่ว่าp = 9 ไม่ใช่จำนวนเฉพาะ สามารถตรวจสอบได้อย่างแน่นอนโดยการตรวจสอบว่าไม่มีค่า a ใดๆ (ในมอด 9) ที่เป็นไปได้ ซึ่งอาจทำได้โดยการตรวจสอบค่าa แต่ละค่า ตั้งแต่ 2 ถึง 8 อย่างเป็นระบบ ( a = 0 และa = 1 จะใช้ไม่ได้กับp ใดๆ ) อย่างไรก็ตาม การตรวจสอบค่าตั้งแต่ 2 ถึง 5 หรือครึ่งหนึ่งของค่าที่เป็นไปได้ทั้งหมดที่ต่ำกว่า 9 ก็เพียงพอแล้ว หาก 9 เป็นจำนวนเฉพาะแล้ว ตามหลักการรังนกพิราบ อย่างน้อยหนึ่งในค่า a เหล่านี้จะยืนยันว่าเป็นจำนวนเฉพาะ เนื่องจากคาดว่าครึ่งหนึ่งของค่าเหล่านั้นจะยืนยันได้

อีกทางเลือกหนึ่ง หากเราใช้รูปแบบเชิงกำหนดซึ่งคำนวณค่าที่ไม่ใช่เศษกำลังสองโดยตรง งานดังกล่าวจะต้องการการวนซ้ำน้อยลงเพื่อยืนยันทั้งความเป็นจำนวนประกอบและความเป็นจำนวนเฉพาะ:

• สำหรับp = 97 = 3(2 ⁵ ) + 1 เรามีเศษเหลือที่ไม่เป็นกำลังสองของa = 5 และ 5 ^(97−1)/2 + 1 = 3552713678800500929355621337890626 หารด้วย 97 ลงตัว ดังนั้น 97 เป็นจำนวนเฉพาะ
• สำหรับp = 1537 = 3(2 ⁹ ) + 1 เรามีเศษเหลือกำลังสองของa = 5 และ 5 ^(1537−1)/2 + 1 = 1052 (mod 1537) หารด้วย 1537 ไม่ลงตัว ดังนั้น 1537=29×53 จึงไม่ใช่จำนวนเฉพาะ

ในตัวอย่างสองตัวอย่างก่อนหน้านี้ ค่าa ที่เหมาะสม ถูกคำนวณโดยตรงโดยใช้การคำนวณเศษเหลือกำลังสอง ซึ่งทำให้ผลการทดสอบมีความชัดเจน กล่าวคือ เป็นเศษเหลือกำลังสองที่ถูกต้องทั้งในกรณีจำนวนเฉพาะและจำนวนประกอบ ไม่จำเป็นต้องค้นหาค่าa อย่างเป็นระบบ เพื่อยืนยันกรณีจำนวนเฉพาะ หรือทำการทดสอบซ้ำหลายครั้งเพียงพอสำหรับกรณีจำนวนประกอบ หากไม่พบเศษเหลือกำลังสอง หรือหากไม่มีอยู่จริง เราสามารถถือว่านี่เป็นการยืนยันว่าจำนวนนั้นเป็นจำนวนประกอบ

เกณฑ์ของออยเลอร์ให้ข้อมูลเชิงลึกเพิ่มเติมเกี่ยวกับจำนวนpซึ่งไม่จำเป็นต้องเป็นส่วนประกอบของทฤษฎีบทของพรอธ ข้อเท็จจริงเหล่านี้เป็นข้อเท็จจริงรองที่ส่วนใหญ่มาจากทฤษฎีบทอื่นๆ ซึ่งสามารถประเมินได้อย่างง่ายดายในระหว่างการใช้งานการทดสอบของพรอธ จำนวนpไม่จำเป็นต้องเป็นจำนวนของพรอธเพื่อให้เกณฑ์นี้มีประโยชน์ กำหนดให้จำนวนเต็มpให้เราเลือก ค่า a ใดๆ จงประเมินเกณฑ์ของออยเลอร์:

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

โดยทั่วไปแล้วจะมีผลลัพธ์ที่แตกต่างกันห้าแบบ ผลลัพธ์บางอย่างเหล่านี้ไม่ขึ้นอยู่กับว่าpเป็นจำนวนเฉพาะแบบ Proth หรือไม่ ดังนั้นจึงใช้ได้กับจำนวนเฉพาะที่เป็นไปได้ทุกรูปแบบ

ความเป็นจำนวนเฉพาะของp :

• ถ้าb = −1 เงื่อนไขของ Proth จะได้รับการตอบสนอง และ pได้รับการยืนยันว่าเป็นจำนวนเฉพาะของ Proth ตามทฤษฎีบทของ Proth หากpเป็นจำนวน Proth จริงๆ

If p is not a Proth number yet b = −1, then this is indicative, but not conclusive, of primality. Refer to the probabilistic Solovay–Strassen primality test and the Miller-Rabin test.

Inconclusive result:

• b = 1, in which case the test is inconclusive and must be tried again with a new a value.

This condition is what requires reiteration and makes the test probabilistic, as if p were prime, then b = ±1 occurs with roughly equal probability, though the b = 1 condition may still be met with p either composite or non-Proth.

This is true unless a happens to also be a quadratic nonresidue of a Proth number p, in which case compositeness is indicated.

Compositeness of p, as per Euler's criterion and the Legendre symbol, which offer early exit conditions when b ≠ ±1. In each of these cases p is not prime and also need not be a Proth number:

• b² = 1, with nontrivial divisors of p being GCD(b ± 1, p).
• b² ≠ 1, where p is proven composite by Fermat's test, base a.
• b = 0, where p has a nontrivial divisor GCD(a, p).

ใบรับรองProthคือใบรับรองความเป็นจำนวนเฉพาะที่เกี่ยวข้องกับจำนวน Proth และการทดสอบของ Proth โดยเฉพาะ เป็นเอกสารหรือหลักฐานดิจิทัลที่ใช้ตรวจสอบเงื่อนไขใดๆ ที่พิสูจน์ความเป็นจำนวนเฉพาะ (หรือความเป็นจำนวนประกอบ) โดยทั่วไปจะมีค่าkและnที่ประกอบกันเป็นจำนวน Proth, pซึ่งพิสูจน์ว่าเป็นจำนวน Proth รวมถึง ค่า aที่พิสูจน์ความเป็นจำนวนเฉพาะ นอกจากนี้ยังอาจพิสูจน์ความเป็นจำนวนประกอบได้หากเหมาะสม ใบรับรองมักแสดงขั้นตอนการพิสูจน์ รวมถึงหลักฐานว่าaเป็นจำนวนควาดราติกที่ไม่ใช่เศษเหลือ เป็นต้น หากจำเป็น

ไพรเมอร์ Proth ตัวแรกคือ (ลำดับA080076ในOEIS ):

3, 5, 13, 17, 41 , 97 , 113 , 193 , 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ....

จำนวนเฉพาะ Proth ที่ใหญ่ที่สุดที่รู้จักในปี 2016 คือ 10223 × 2 ^31172165 + 1 และมีความยาว 9,383,761 หลัก^{[ 3 ]}ค้นพบโดย Peter Szabolcs ใน โครงการ คำนวณอาสาสมัครPrimeGrid ซึ่งประกาศเมื่อวันที่ 6 พฤศจิกายน 2016 ^{[ 4 ]}เป็นจำนวนเฉพาะที่ใหญ่ที่สุดอันดับที่ 11 ที่รู้จัก ณ เดือนมกราคม 2024 เป็นจำนวนเฉพาะที่ไม่ใช่ Mersenne ที่ใหญ่ที่สุดที่รู้จัก จนกระทั่งถูกแซงหน้าในปี 2023 ^{[ 5 ]}และเป็นจำนวน Colbert ที่ใหญ่ที่สุด จำนวนเฉพาะ Proth ที่ใหญ่ที่สุดอันดับสองที่รู้จักคือ 202705 × 2 ^21320516 + 1 ค้นพบโดย PrimeGrid ^{[ 6 ]}

การพิสูจน์ทฤษฎีบทนี้ใช้การทดสอบความเป็นจำนวนเฉพาะของ Pocklington-Lehmerถือเป็นกรณีพิเศษที่ค่อนข้างง่ายในการพิสูจน์ทฤษฎีบทของ Proth จากการทดสอบนี้ นอกจากนี้ยังคล้ายคลึงกับการพิสูจน์การทดสอบของ Pépin อย่างมาก การพิสูจน์สามารถพบได้ในหน้า 52 ของ^{[ 1 ]}

เมื่อk = nจำนวน Proth จะอยู่ในรูปp = n²n + 1 ถ้าเราผ่อนปรนเงื่อนไขที่กำหนดให้k (หรือⁿ )ต้องเป็นจำนวนคี่ จำนวนเหล่านี้จะเรียกว่าจำนวน Cullenซึ่งมี จำนวน เฉพาะ Cullen ที่สอดคล้องกัน แม้ว่าการทดสอบของ Proth จะใช้ได้ผลเมื่อn เป็นจำนวนคี่ แต่จำนวน Cullen ก็มีการทดสอบความเป็นจำนวนเฉพาะของตัวเองสำหรับ nใดๆก็ตาม

นอกจากนี้ การทดสอบความเป็นจำนวนเฉพาะของคัลเลนยังสามารถขยายไปสู่จำนวนในรูปแบบp = nc ⁿ + 1 สำหรับฐานc ใดๆ ก็ได้

François Proth (1852–1879) เผยแพร่ทฤษฎีบทในปี 1878 ^{[ 7 ] [ 8 ]}

• การทดสอบของเปแปง (กรณีพิเศษk  = 1 โดยเลือกa  = 3)
• หมายเลข Sierpiński

• ไวส์สไตน์, เอริค ดับเบิลยู. "ทฤษฎีบทของโพรธ" . แมธเวิลด์ .