There are at least two proofs of the above conjecture now.
To disprove the above you would need to find a Proth Number of
the form
This is non-trivial*
*No counter-examples exist for t<=30,000 in our limited testing
The following conjecture might be easier to disprove
In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter
In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter
In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter
In this post we continue through the OEIS 047713 Pseudoprimes tabulating the results of power (p-1)/4 as a filter
.
In the previous post we offered a partial answer to proving a Proth Number is prime
The result would be a probable prime to base 2.
.
74665 is not a Proth Number. Is 74665 a strong Euler-Jacobi Pseudoprime?
Of the 37 initial terms in OEIS sequence A047713 we found the following:
One Pseudoprime passed the filter – 74665
Three were Incalculable as p-1 not divisible by 4
Five were marked ‘not applicable’ as we can only apply our filter when (2/p)=1
One in twenty-nine passed the filter which means we eliminated 96% of the Pseudoprimes using this extra filter.
If you count the 8 for which our filter could not be used then we still eliminated 3/4 of the Pseudoprimes.
For the conjecture at the top of this page, we would always be dealing with (p-1) divisible by 8 and 2^((p-1)/2) = 1 mod p
So our filter would likely achieve near the 96% we achieved here.
Having amended the previous post, this filter is already incorporated into our prime test.
If reading this post has got you interested in Probable Prime theory then the following resources might offer some further reading:
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 you interested in quadratic residues, then here are some resources to consider:
What follows is an introduction and proof of the Conjecture provided by Natalia Skirrow
Let N = N(k) = (2^k-1)*2^(k+3)+1, and M = A000225(k+1) = 2^(k+1)-1.
17 divides N if k == 1,4 (mod 8).
As a Proth number, N is prime iff there exists an integer c such that c^((N-1)/2) == -1 (mod N).
The conjecture can be strengthened to the statement that 2^((N-1)/4) == -1 (mod N) iff N is prime.
Proof of conjecture:
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).
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.
Thus val_2(o) = k+2, so (by Fermat’s little theorem) 2^(k+2) | p-1, and p >= 2^(k+2)+1. N < 2^(2*k+3), so this implies p > sqrt(N).
However, dividing N by p would produce a divisor of N that is < sqrt(N), a contradiction.
Proof of conjecture’s converse:
N = 2*M^2 – 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.
Thus Euler’s criterion for quadratic residuehood gives that M^((N-1)/2) == -1 (mod N).
However, 2*M^2 == 1 (mod N), so M^((N-1)/2) == (M^2)^((N-1)/4) == 2^(-(N-1)/4) (mod N).
Thus, if N is prime, 2^((N-1)/4) == -1 (mod N).
Note that 2^((N-1)/4) == -1 => 2^((N-1)/2) == 1, which by Euler’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’s test, sqrt(2) (mod N) always exists and is among them.
Proofs that are a page or two and involve classic theorems including Euler criterion are I believe possible.
Do verify any proofs given on this page.
There may be several AI proofs, the first by looking at the 2-adic valuation involved has been completed [but not verified] by Opus 5.5 Claude
Although AI can spot the potential for generalising a proof, it does not offer to do that, instead observing “statement hold for far more general N”
There are many ways that Mathematical discovery can happen.
Doing an Undergraduate degree or Masters or PhD are ways that discoveries can be made.
Working in Algebra for many years and asking “what if” is another way.
My discovery, depending on your point of view, is one or more of the following:
Thought it worth describing the process that has allowed that to happen and will talk subjectively about that next.
( Do jump ahead to the Conjectures at the bottom of this post if you are interested more in that )
Have spent many years working in the set
Documented lots of algebraic observations, and through them, was able to come up with an order conjecture involving a least common multiple.
Nothing too exciting so far.
Through thinking about order of two elements in particular, began to see the importance of thinking lengthwise about things with decreasing and increasing values of t.
This is in contrast to thinking about isomorphism primarily, where we tend to view order as an important separator and then move laterally between [groups].
Went so far as to propose a new definition “sturdy element” to facilitate this thinking.
Tabulated [a lot] of group examples using those elements.
( See other posts on this site )
Adjusted the set definition slightly from
to nearby sets
This was a key step
Broke away from considering only sets we can describe as Proth numbers and considered other sets.
Still thinking about order and patterns and came up with some new conjectures.
To try and add a few chapters to my draft book, returned to sets of Proth numbers but considered slightly different powers.
This was another key step.
During this time was always asking “what if” and “suppose” type questions of what I was seeing.
This supposing and enquiring was another key step.
Spotted something interesting when working with groups in set
Factored the order of a couple of groups to see if there was anything to see.
Made a supposition and tested it for a couple of examples.
Found that the pattern did not apply in all cases.
Asked the question did it only apply to primes.
There was the discovery [ see conjecture next ]
Created a script to test things out.
Used a computer algebra package to run the script to see it work with larger examples.
The largest prime found [9769 digits] using this probable prime test as a filter is next.
Looked for a further set with something that looked algebraic
The largest prime found [386 digits] using this probable prime test as a filter is next.
The early build up to my discovery involved tabulating over 100 groups.
This tabulation is documented in the early chapters of my (draft) book.
Consider the Proth space
Using the above conjecture we have established the following
By tabulating order of groups next we provide examples where order follows the conjecture and other examples where the Proth number used is composite.
We will be using generating element 2
When t=3 we have P=1+9×64 and the set of elements modulo P is a multiplicative group.
The subgroup generated by 2 has 144 elements
Order is (2^4)×(1+2^3) so we are a [probable] prime.
The elements in TPc144 are as shown next
{ 2, 4, 8, 16, 32, 64, 128, 256, 512, 447,
317, 57, 114, 228, 456, 335, 93, 186, 372, 167,
334, 91, 182, 364, 151, 302, 27, 54, 108, 216,
432, 287, 574, 571, 565, 553, 529, 481, 385, 193,
386, 195, 390, 203, 406, 235, 470, 363, 149, 298,
19, 38, 76, 152, 304, 31, 62, 124, 248, 496,
415, 253, 506, 435, 293, 9, 18, 36, 72, 144,
288, -1, 575, 573, 569, 561, 545, 513, 449, 321,
65, 130, 260, 520, 463, 349, 121, 242, 484, 391,
205, 410, 243, 486, 395, 213, 426, 275, 550, 523,
469, 361, 145, 290, 3, 6, 12, 24, 48, 96,
192, 384, 191, 382, 187, 374, 171, 342, 107, 214,
428, 279, 558, 539, 501, 425, 273, 546, 515, 453,
329, 81, 162, 324, 71, 142, 284, 568, 559, 541,
505, 433, 289, 1 }
Next we look at 2177=7*311 and see order is 465 so does not follow the rule established in the conjecture as the Proth number is composite.
For 2177 from t=4 the 465 elements in TPc465 are not tabulated here
For 8449 from t=5 the 840 elements in TPc840 are not tabulated here
For 33281 from t=6 the 7953 elements in TPc7953 are not tabulated here
For 132097 from t=7 the 6972 elements in TPc6972 are not tabulated here
For 526337 from t=8 the 17688 elements in TPc17688 are not tabulated here
For 2101249 from t=9 the 525312 elements in TPc525312 are not tabulated here
For 8396801 from t=10 the 298680 elements in TPc298680 are not tabulated here
A script based on the conjecture is shown next
Running that script for t to 500 gives some small examples that fit with the conjecture
A question that applies to all such searches once t becomes large is whether the primes exist.
This is an open question not answered here.
Do adjust the value for starter to search from the starting t value you require and run the script in Pari/GP or adapt it for your favoured computer algebra package.
Consider the Proth space
Using the above conjecture we have established the following
By tabulating order of groups next we provide examples where order follows the conjecture and other examples where the Proth number used is composite.
We will be using generating element 2
When t=1 we have P=1+1×16 and the set of elements modulo P is a multiplicative group.
The subgroup generated by 2 has 8 elements
Using prefix TNz to avoid clashing with existing letter conventions for groups.
Prefer G or S? Replace them in your local copy.
The elements in TNz8 are { 2, 4, 8, -1, 15, 13, 9, 1 }
If TNz8 is really a group then we need inverses so let us document those next.
Later we look at 1921=17*113 and see order is 56 so does not follow the rule established in the conjecture as the Proth number is composite.
For 97 from t=2 the 48 elements in TNz48 are as shown next.
{ 2, 4, 8, 16, 32, 64, 31, 62, 27, 54,
11, 22, 44, 88, 79, 61, 25, 50, 3, 6,
12, 24, 48, -1, 95, 93, 89, 81, 65, 33,
66, 35, 70, 43, 86, 75, 53, 9, 18, 36,
72, 47, 94, 91, 85, 73, 49, 1 }
For 449 from t=3 the 224 elements in TNz224 are as shown next.
{ 2, 4, 8, 16, 32, 64, 128, 256, 63, 126,
252, 55, 110, 220, 440, 431, 413, 377, 305, 161,
322, 195, 390, 331, 213, 426, 403, 357, 265, 81,
162, 324, 199, 398, 347, 245, 41, 82, 164, 328,
207, 414, 379, 309, 169, 338, 227, 5, 10, 20,
40, 80, 160, 320, 191, 382, 315, 181, 362, 275,
101, 202, 404, 359, 269, 89, 178, 356, 263, 77,
154, 308, 167, 334, 219, 438, 427, 405, 361, 273,
97, 194, 388, 327, 205, 410, 371, 293, 137, 274,
99, 198, 396, 343, 237, 25, 50, 100, 200, 400,
351, 253, 57, 114, 228, 7, 14, 28, 56, 112,
224, -1, 447, 445, 441, 433, 417, 385, 321, 193,
386, 323, 197, 394, 339, 229, 9, 18, 36, 72,
144, 288, 127, 254, 59, 118, 236, 23, 46, 92,
184, 368, 287, 125, 250, 51, 102, 204, 408, 367,
285, 121, 242, 35, 70, 140, 280, 111, 222, 444,
439, 429, 409, 369, 289, 129, 258, 67, 134, 268,
87, 174, 348, 247, 45, 90, 180, 360, 271, 93,
186, 372, 295, 141, 282, 115, 230, 11, 22, 44,
88, 176, 352, 255, 61, 122, 244, 39, 78, 156,
312, 175, 350, 251, 53, 106, 212, 424, 399, 349,
249, 49, 98, 196, 392, 335, 221, 442, 435, 421,
393, 337, 225, 1 }
For 1921 from t=4 the 56 elements in TNz56 are as shown next.
{ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
127, 254, 508, 1016, 111, 222, 444, 888, 1776, 1631,
1341, 761, 1522, 1123, 325, 650, 1300, 679, 1358, 795,
1590, 1259, 597, 1194, 467, 934, 1868, 1815, 1709, 1497,
1073, 225, 450, 900, 1800, 1679, 1437, 953, 1906, 1891,
1861, 1801, 1681, 1441, 961, 1 }
For 7937 from t=5 the 3968 elements in TNz3968 are not tabulated here
For 32257 from t=6 the 16128 elements in TNz16128 are not tabulated here
For 130049 from t=7 the 10603 elements in TNz10603 are not tabulated here
For 522241 from t=8 the 14457 elements in TNz14457 are not tabulated here
For 2093057 from t=9 the 20520 elements in TNz20520 are not tabulated here
For 8380417 from t=10 the 4190208 elements in TNz4190208 are not tabulated here
For 33538049 from t=11 the 16769024 elements in TNz16769024 are not tabulated here
For 134184961 from t=12 the 246480 elements in TNz246480 are not tabulated here
Prime testing of some of the larger examples found using the conjecture is shown next
Further work on this set of numbers has produced the following improved conjecture
