{"id":341,"date":"2026-09-19T17:25:56","date_gmt":"2026-09-19T17:25:56","guid":{"rendered":"https:\/\/mathrelated.co.uk\/?p=341"},"modified":"2026-09-29T19:30:04","modified_gmt":"2026-09-29T19:30:04","slug":"proving-proth-number-prime-using-euler","status":"publish","type":"post","link":"https:\/\/mathrelated.co.uk\/index.php\/2026\/09\/19\/proving-proth-number-prime-using-euler\/","title":{"rendered":"Proving Proth number prime using Euler"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">It is not always necessary to use the Proth Theorem to prove a Proth number prime.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">What follows is a proof that is possible because the base we have chosen is a quadratic residue.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"652\" height=\"948\" src=\"https:\/\/mathrelated.co.uk\/wp-content\/uploads\/2026\/09\/mathsturdyChap31provingprime-3.jpeg\" alt=\"Proof of Proth Number using Euler plus\" class=\"wp-image-366\" srcset=\"https:\/\/mathrelated.co.uk\/wp-content\/uploads\/2026\/09\/mathsturdyChap31provingprime-3.jpeg 652w, https:\/\/mathrelated.co.uk\/wp-content\/uploads\/2026\/09\/mathsturdyChap31provingprime-3-206x300.jpeg 206w\" sizes=\"auto, (max-width: 652px) 100vw, 652px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Next we include a flowchart of a decision process regarding use of Proth theorem or not<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"708\" height=\"973\" src=\"https:\/\/mathrelated.co.uk\/wp-content\/uploads\/2026\/09\/mathsturdyChap31provingprime_flowchart-4.jpeg\" alt=\"\" class=\"wp-image-416\" srcset=\"https:\/\/mathrelated.co.uk\/wp-content\/uploads\/2026\/09\/mathsturdyChap31provingprime_flowchart-4.jpeg 708w, https:\/\/mathrelated.co.uk\/wp-content\/uploads\/2026\/09\/mathsturdyChap31provingprime_flowchart-4-218x300.jpeg 218w\" sizes=\"auto, (max-width: 708px) 100vw, 708px\" \/><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">If the above has got you interested in quadratic residues, then here are some resources to consider:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Second chapter of <a href=\"https:\/\/www.sciencepublishinggroup.com\/book\/ISBN\/978-1-940366-74-6\" target=\"_blank\" rel=\"noopener nofollow\">Number Theory and Algebraic Equations<\/a><\/li>\n\n\n\n<li><a href=\"https:\/\/ocw.mit.edu\/courses\/18-781-theory-of-numbers-spring-2012\/d5cdd1b802194a2a236eed934da8ae36_MIT18_781S12_lec9.pdf\" target=\"_blank\" rel=\"noopener nofollow\">MIT: Theory of Numbers &#8211; Lecture 9<\/a><\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">What follows is an introduction and proof of the Conjecture provided by Natalia Skirrow<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Let N = N(k) = (2^k-1)*2^(k+3)+1, and M = <a href=\"https:\/\/oeis.org\/A000225\" target=\"_blank\" rel=\"noopener nofollow\">A000225<\/a>(k+1) = 2^(k+1)-1.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">17 divides N if k == 1,4 (mod 8).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">As a Proth number, N is prime iff there exists an integer c such that c^((N-1)\/2) == -1 (mod N).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The conjecture can be strengthened to the statement that 2^((N-1)\/4) == -1 (mod N) iff N is prime.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Proof of conjecture:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Suppose that 2^((N-1)\/4) == -1 (mod N) but N is composite, i.e. there exists a nontrivial prime divisor p | N, and let o be the multiplicative order of 2 (mod p). <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The supposition implies 2^((N-1)\/4) == -1 (mod p), so o is a divisor of (N-1)\/2 but not of (N-1)\/4.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"> Thus val_2(o) = k+2, so (by Fermat&#8217;s little theorem) 2^(k+2) | p-1, and p &gt;= 2^(k+2)+1. N &lt; 2^(2*k+3), so this implies p &gt; sqrt(N). <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">However, dividing N by p would produce a divisor of N that is &lt; sqrt(N), a contradiction.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Proof of conjecture&#8217;s converse:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">N = 2*M^2 &#8211; 1, and since N == -1 (mod M), the Jacobi symbol (N|M) = (-1|M) = -1. If N is prime, then since N == 1 (mod 4), quadratic reciprocity gives (M|N) = (N|M) = -1. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Thus Euler&#8217;s criterion for quadratic residuehood gives that M^((N-1)\/2) == -1 (mod N).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">However, 2*M^2 == 1 (mod N), so M^((N-1)\/2) == (M^2)^((N-1)\/4) == 2^(-(N-1)\/4) (mod N). <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Thus, if N is prime, 2^((N-1)\/4) == -1 (mod N).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Note that 2^((N-1)\/4) == -1 =&gt; 2^((N-1)\/2) == 1, which by Euler&#8217;s criterion means 2 is a quadratic residue, so the conjecture is equivalent to the statement that if any numbers exist as primality witnesses for Proth&#8217;s test, sqrt(2) (mod N) always exists and is among them.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Proofs that are a page or two and involve classic theorems including Euler criterion are I believe possible.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Do verify any proofs given on this page.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">There may be several AI proofs, the first <a href=\"https:\/\/claude.ai\/share\/78e29034-08f0-49ac-8c8c-b7c8f0f1f28f\" target=\"_blank\" rel=\"noopener nofollow\">by looking at the 2-adic valuation involved<\/a> has been completed [but not verified] by Opus 5.5 Claude<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Although AI can spot the potential for generalising a proof, it does not offer to do that, instead observing &#8220;statement hold for far more general N&#8221;<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>It is not always necessary to use the Proth Theorem to prove a Proth number prime. What follows is a proof that is possible because the base we have chosen is a quadratic residue. Next we include a flowchart of a decision process regarding use of Proth theorem or not If the above has got [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,6],"tags":[14],"class_list":["post-341","post","type-post","status-publish","format-standard","hentry","category-mathematics","category-numbertheory","tag-prime"],"_links":{"self":[{"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/posts\/341","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/comments?post=341"}],"version-history":[{"count":11,"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/posts\/341\/revisions"}],"predecessor-version":[{"id":419,"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/posts\/341\/revisions\/419"}],"wp:attachment":[{"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/media?parent=341"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/categories?post=341"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathrelated.co.uk\/index.php\/wp-json\/wp\/v2\/tags?post=341"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}