In the Journal of Recreational Mathematics, Volume 14, Number 2, (copyright 1981), I got a small thing published, which is described in the above Summary (it was published as a problem for the reader to solve, so the wording was different). The statement was Mathematically Proved True by one of the
editors of that Journal.
So, for example, in Base 2 the reciprocal of 7 (that is, 1/7) is 0.001001001... --the repeating sequence ("period") is 3 digits long, which means one cannot use that to assume that 7 is a prime number, while in Base 3 the reciprocal of 7 is 0.010212010212... --the repeating section or period is 7-1=6 digits long, which suffices to prove that 7 is a prime number. EVERY prime (p), in at least one Base (heh, actually, an infinite number of Bases), will have a reciprocal such that it includes a period (p-1) digits. 1/7 has period lengths of 6 digits in every Base of the form 7x+3 --thus Base 3 when (x=0), and the ordinary Base Ten when (x=1)-- and also in every Base of the form 7x+5.
Meanwhile, NO composite number in ANY Base can match that property, of reciprocals of primes.
Nevertheless, that Test for Primes is quite impractical to use, when you want to test a large number. If a mere 13-digit number such as 1-trillion-and-1 is prime, then you need to almost literally do long-division for 1 trillion digits, to prove it. AND you may have to do it more than once, to FIND a Base in which the period is a trillion digits long! So there is no practical way to use that Test for significantly larger numbers, say a thousand digits long....
Well, it happens that there are Variations On The Theme, and that's why I'm posting this Idea. One of those variations includes something known as "Fermat's Little Theorem" (see link), which has its own variations. The one that concerns us here is the fact that when (p) is a prime number, you can take another number (a) that is "coprime" --has no divisors in common-- with (p), and raise (a) to the power of (p-1), and then, if you subtract 1 from that power, the result is always exactly divisible by (p). Every prime can do that; most composites can't (but some can, and those are often called "pseudoprimes").
So, an example of the preceding is that if you start with 7-1=6, and take 3-to-the-6th power, and subtract 1, the result (728) is exactly divisible by 7, indicating that 7 is probably a prime. But 3-to-the-9th power, minus one, equals 19682, which is not exactly divisible by 10, proving that 10 is not a prime.
My little published problem, and Fermat's Little Theorem, are revealed to be almost-obviously related if you do a Long Division problem and think about it in the Right Way, so here is 1/7 in Base Ten (ignore commas used as spacers):
, , 0.142857
7 | 1.000000 ,<--1 is the result of the expression 1 mod 7
, , , ,7 , , , , , ,(ignore decimal point; 1000000-1=999999)
, , , ,30 , , , , ,<--3 is 10 mod 7, an "intermediate modulus"
, , , ,28
, , , , ,20 , , , ,<--2 is 30 mod 7, the next intermediate modulus
, , , , ,14
, , , , , ,60 , , ,<--6 is 14 mod 7, the next intermediate modulus
, , , , , ,56
, , , , , , ,40 , ,<--4 is 60 mod 7, the next intermediate modulus
, , , , , , ,35
, , , , , , , ,50 ,<--5 is 40 mod 7, the next intermediate modulus
, , , , , , , ,49
, , , , , , , , ,1 <--1 is 50 mod 7, the last and original modulus (and still "intermediate" if we continue dividing)
So, when 10-to-the-6th power has 1 subtracted from it, the result, 999999, is exactly divisible by 7, yielding 142857, which are the 7-1=6 digits of the reciprocal's period.
However, remember that what I published is related to an impractical Absolute Test for primes, while Fermat's Little Theorem ("FLT") is actually a practical test that can identify PROBABLE primes (the composite pseudoprimes are relatively rare).
This Idea concerns a way to combine the two, that might yield a practical Absolute Test for primes. It involves some things that, so far as I know, haven't been Mathematically Proved yet, but, hey, this is the HalfBakery, so....
First, though (the unProved stuff gets presented later), I need to describe a method regarding how it can be practical to work with a high power, such as might be used by FLT (say, 2-to-the-one-trillionth power). This method involves "modulus" stuff, which is why I included some statements about various moduli in that long division problem above.
If one-trillion-and-one is a prime number, then two-to-the-trillionth-power, minus One, must be exactly divisible by one-trillion-and-one. This is equivalent to saying that if you divided one-trillion-and-one into two-to-the-trillionth power, The Remainder Of The Division (or "modulus") will be One.
Well, it happens that there is a "trick". Look at the Sequence of Moduli in that reciprocal-of-7 long-division problem above: 1,3,2,6,4,5,1. Let us declare that the first 1 is at Position Zero in that sequence (because it existed before we started doing the long division). So, the Modulus in the First Position is 3, and the Modulus in the Second Position is 2, and so on.
You know that you can add 1+1=2; it turns out that the Positions in the Sequence are related to their Occupying Moduli in a VERY useful way: Just Multiply Two Numbers At Any Positions, To Find The (pre)Modulus At The "Sum" Position.
So if 3 is in the First Position, we can multiply it by itself and get 9. Well, 9 mod 7 equals 2, and 2 is the Modulus in the Second Position --and First Plus First Equals Second.
Similarly, 3 multiplied by 2 equals 6, and 6 is in the Third Position --and First Plus Second Equals Third.
Any combination of multiplications will work: Consider Second Plus Second Plus Second Equals Sixth, and use the Modulus of 2 in that Second Position three times: 2*2*2=8, and 8 mod 7 equals 1, and 1 is in the Sixth Position. (Note you could even play with the 1 in the Zeroth Position, except it is not useful, since multiplying by 1, or adding Zero, doesn't get you anywhere.)
Now Connect The Dots: If FLT can be related to a Long-Division Problem, then, for one-trillion-and-one (call it "p"), computing the Modulus of two-to-the-trillionth-power (2^(p-1)) should be equivalent to computing the reciprocal of (p) in Base Two for (p-1) Modulus Positions, and the Modulus exactly at the Trillionth Position of that Long-Divison Problem must be One if (p) is a prime number. But we don't have to compute all the Intermediate Moduli in that Problem, because we can use multiplication to skip through Positions in the Sequence of Moduli!
To implement the Idea efficiently (and for ANY Base), we start with the Base Two Representation of one trillion (a five-byte number): 11101000 11010100 10100101 00010000 00000000. Starting at the farthest-right and working left, one trillion equals the following powers-of-two, added together: 4096 + 65536 + 262144 + 2097152 + 8388608 + 67108864 + 268435456 + 1073741824 + 2147483648 + 34359738368 + 137438953472 + 274877906944 + 549755813888.
Those numbers represent Positions in the Sequence of Moduli. We need to compute, in our chosen Base, the relevant Modulus located at EACH of those Positions --but ONLY those Positions-- and then we simply multiply ALL of those relatively few Moduli together, to figure the (pre)Modulus at the trillionth (or p-1, or "Sum") Position.
Now recall that in any Base-Two (or "Binary") Representation of a number, the right-most digit is in the "ones column" (just like the right-most digit in an ordinary Base Ten number is in the "ones column"). Regardless of whether we need that Position in our Binary Representation of (p-1), we always need to know the Modulus at the First Position, of our Long-Division Problem.
Well, it happens that in any Fermat's Little Theorem situation such as two-to-the-trillionth, or nine-to-the-trillionth, or fifty-to-the-trillionth, ..., the numerical Base in which we are doing our Long-Division problem is two, or nine, or fifty... --and the Modulus at the First Position will also be two, or nine, or fifty.... Please keep in mind that the Binary Representation of (p-1) is completely independent of the Base in which we compute Moduli.
(Recall that the reason the First Postion Modulus was 3 for 1/7, working in Base 10, is simply that 10 is 3 units larger than 7, the divisor. But in the current Long-Division Problem the divisor is one-trillion-and-one, and we are dealing with a Base that is a LOT smaller than that!)
So, since we started talking about two-to-the-trillionth, we will be using Base Two to compute Moduli, so 2 is the Modulus at the First Position. And, just as we computed 3*3=9 to get the (pre)Modulus at the Second Position of 1/7, we now compute 2*2=4. Note that Second Position is equivalent to the "twos column" in the Binary Representation of (p-1) --much like the second column from the right, in Base Ten, is the "tens column".
The NEXT column in our Binary Representation of (p-1) is the "fours column", and this means we need the Modulus at the Fourth Position. Simple: just multiply the Modulus at the Second Position by itself: 4*4=16 (BECAUSE 2+2=4). The next needed Modulus is at the Eighth Position, so again we square the previous Modulus (because 4+4=8). And so on, for all forty columns of our Binary Represenation of one trillion.
A thing that greatly simplifies those mathematical computations is the fact that whenever the result of computing a square is greater than one-trillion-and-one, we can simply call it a (pre)Modulus, and compute the ACTUAL Modulus from it, and then continue using the smaller number instead of the larger number, in later calculations. Go back to the Modulus Sequence for 1/7, and note that after computing 2 at the Second Position from 3*3=9, that 2 was then used in 2*2*2 to obtain 8 (and then 1) for the Sixth Position. Would you rather have done 9*9*9=729, and done 729 mod 7 to obtain that 1? Of course not!
So, when computing the reciprocal of one-trillion-and-one in Base Two, the result of the sixth consecutive squaring (that started from 2), for Position 64, is the first number larger than one-trillion-and-one --by quite a lot: 18446744073709551616. The actual Modulus from that (pre)Modulus is 73691104872, and so that smaller number is the number to square, to obtain the (pre)Modulus at Position 128. And so on...
Here's the list of Moduli we must make special note of, because they are at the Positions needed to compute the Modulus at the "Sum" Position --the trillionth Position:
901897618191 (Position 4096)
427444269405 (Position 65536)
388508461635 (Position 262144)
408891468380 (Position 2097152)
815064031716 (Position 8388608)
169982356552 (Position 67108864)
485504951170 (Position 268435456)
547560287052 (Position 1073741824)
168816582748 (Position 2147483648)
323427014244 (Position 34359738368)
728657465618 (Position 137438953472)
315910419724 (Position 274877906944)
94048842886 (Position 549755813888)
As previously mentioned, we simply mulitply those Moduli together --and of course we can do it in stages, computing actual Moduli from (pre)Moduli along the way-- to obtain the final result, which happens to be...
(drum roll, please)
365134236271
Hey, I never said that one-trillion-and-one was a prime! (It is divisible by 73.) This Idea is about a Primality Test, to FIND OUT if a given number is a prime --or not! And one thing is guaranteed already: For some number (p) and the Long-Division Problem 1/(p), if at Position (p-1) in the Modulus Sequence the number is not equal to 1, then (p) is NOT a prime, period.
On the other hand, just because the Modulus at Position (p-1) might be 1, that does not automatically mean (p) is a prime. See, if we skip through the Modulus Series like we did for one-trillion-and-one, then we are not gathering all the data guaranteed to prove that the period-length of the reciprocal of (p) is equal to (p-1). Note that early in this text was the observation that in Base 2 the reciprocal of 7 is 0.001001001... --its period-length is only 3, which happens to be exactly half of 6=7-1.
It happens that for 1/7 in Base 2 the relevant Modulus Sequence is 1,2,4,1,2,4,1, ... So, if we had skipped directly to the Sixth Position, we could have missed the intermediate 1 at the Third Position. There must NOT be an intermediate 1, if we want to prove that the period length equals (p-1). And it just so happens that the pseudoprimes mentioned earlier have that property; in EVERY coprime Base, the reciprocal of a pseudoprime (p) has a period length that is some exact fraction of (p-1) --which is why they can have a 1 at Position (p-1).
What to do?
Here is where I soon have to start describing some stuff that hasn't yet been Mathematically Proved. Look again at the reciprocal of 7 in Base 10: 0.142857... Its period length of 6 is an even number (and, of course, for every prime (p) greater than 2, (p-1) will be an even number). Suppose we split that period in half and played with it? 142+857=999 --how about that! So far as I have been able to determine experimentally, WHENEVER --including in ANY Base (B)-- the period of 1/(p) has an even length (p-1), thereby proving (p) is a prime, it ALSO happens that that period can be split in half, and the two halves can be added to yield a sequence of numbers such that each and every one of those numbers will equal (B-1). We did 1/7 in Base 10 and got 142+857=999, and 10-1=9, see? (For a longer example than 1/7, here is the length-28 period of 1/29 in Base 10: 0344827586206896551724137931 --and 03448275862068 + 96551724137931 does indeed equal 99999999999999.)
But there is more. When (p) is a prime and the period length of (1/p) equals (p-1)/2, or (p-1)/4, or (p-1)/8, or ..., AND when that length is still an even number, then the thing described in the last paragraph still holds true! The period can be split into two parts and added together, and the result is a sequence of numbers, each being (B-1). An example of this, in Base 10, is 1/13: 0.076923076923... --it's period length is 6, which is (13-1)/2, and 6 is an even number, so 076+923=999.
AND, so far as I've been able to determine, composites numbers do NOT have that property! --when their reciprocals have period-lengths that exactly divide (p-1), that is. I've seen a few composites exhibit that property for other lengths, but none of those matter, since the first part of this Primality Test will filter them out --they don't have a Modulus Series with One at Position (p-1).
Meanwhile, the data we have so far gathered (per the one-trillion-and-one example) involves Moduli, not the digits of the period. Nevertheless, the two groups of numbers are closely related, since, obviously, a Long Division Problem uses the Modulus Series to generate the numbers in the period. So, look again at the Modulus Series for 1/7 in Base 10 (starting at the First Position): 3, 2, 6, 4, 5, 1 --if we split that in half and add the halves, we get 7, 7, 7. And the Modulus Series for 1/29 in Base 10 is: 10, 13, 14, 24, 8, 22, 17, 25, 18, 6, 2, 20, 26, 28, 19, 16, 15, 5, 21, 7, 12, 4, 11, 23, 27, 9, 3, 1 --you are invited to split and add halves of that list, to get 29, 29, 29, ....
So, THAT is what we can test for, using the Modulus data already gathered in the first part of this overall Primality Test. Any even-length Modulus List that can't be split and added, such that every sum equals (p), means that (p) is a composite number.
The following computer code is written in the "GAP" programming language, because GAP is designed to handle very large integers (can do million-digit numbers easily, if your computer has enough RAM) --see link; the language is freely available. Anyone who already knows the "Pascal" computer langage will probably find GAP to be easy to learn. (NOTE: "tilde" (~) characters are being used for indenting on a HalfBakery Web Page, and must be removed.)
# This Function is called "IsAPrime" to avoid
# conflicts with the existing GAP functions
# "IsPrime" and "IsProbablyPrime". This prime
# test returns a short two-item List, as
# follows, without attempting to yield factors
# of any number that is not prime:
# [true, true] --(p) is prime, certainly
# [false, true] --(p) is composite, certainly
# [true, false] --(p) is prime, probably
# [false, false] --(p) is composite, probably
# If certain aspects of this Function become
# mathematically proved, then it can be
# modified to simply return true or false, only.
IsAPrime := function(p)
local r, P, a, B, t, s, i, j, q, n, k, m;
# Variable (p) is the number being tested
# Variable (r) is for any square (or other) roots
# Other variables are described later.
# Start with simple stuff to process dinky numbers
if (not IsInt(p)) then
~ return([false, true]); # (p) must be an integer
fi;
p:=AbsInt(p); # work with a positive value
if (p<2) then
~ return([false, true]); # Zero and One aren't prime
fi;
# Variable (P) holds a List of all primes < 10000
P:=SSortedList(\
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,\
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,\
101, 103, 107, 109, 113, 127, 131, 137, 139,\
149, 151, 157, 163, 167, 173, 179, 181, 191,\
193, 197, 199, 211, 223, 227, 229, 233, 239,\
241, 251, 257, 263, 269, 271, 277, 281, 283,\
293, 307, 311, 313, 317, 331, 337, 347, 349,\
353, 359, 367, 373, 379, 383, 389, 397, 401,\
409, 419, 421, 431, 433, 439, 443, 449, 457,\
461, 463, 467, 479, 487, 491, 499, 503, 509,\
521, 523, 541, 547, 557, 563, 569, 571, 577,\
587, 593, 599, 601, 607, 613, 617, 619, 631,\
641, 643, 647, 653, 659, 661, 673, 677, 683,\
691, 701, 709, 719, 727, 733, 739, 743, 751,\
757, 761, 769, 773, 787, 797, 809, 811, 821,\
823, 827, 829, 839, 853, 857, 859, 863, 877,\
881, 883, 887, 907, 911, 919, 929, 937, 941,\
947, 953, 967, 971, 977, 983, 991, 997, 1009,\
1013, 1019, 1021, 1031, 1033, 1039, 1049,\
1051, 1061, 1063, 1069, 1087, 1091, 1093,\
1097, 1103, 1109, 1117, 1123, 1129, 1151,\
1153, 1163, 1171, 1181, 1187, 1193, 1201,\
1213, 1217, 1223, 1229, 1231, 1237, 1249,\
1259, 1277, 1279, 1283, 1289, 1291, 1297,\
1301, 1303, 1307, 1319, 1321, 1327, 1361,\
1367, 1373, 1381, 1399, 1409, 1423, 1427,\
1429, 1433, 1439, 1447, 1451, 1453, 1459,\
1471, 1481, 1483, 1487, 1489, 1493, 1499,\
1511, 1523, 1531, 1543, 1549, 1553, 1559,\
1567, 1571, 1579, 1583, 1597, 1601, 1607,\
1609, 1613, 1619, 1621, 1627, 1637, 1657,\
1663, 1667, 1669, 1693, 1697, 1699, 1709,\
1721, 1723, 1733, 1741, 1747, 1753, 1759,\
1777, 1783, 1787, 1789, 1801, 1811, 1823,\
1831, 1847, 1861, 1867, 1871, 1873, 1877,\
1879, 1889, 1901, 1907, 1913, 1931, 1933,\
1949, 1951, 1973, 1979, 1987, 1993, 1997,\
1999, 2003, 2011, 2017, 2027, 2029, 2039,\
2053, 2063, 2069, 2081, 2083, 2087, 2089,\
2099, 2111, 2113, 2129, 2131, 2137, 2141,\
2143, 2153, 2161, 2179, 2203, 2207, 2213,\
2221, 2237, 2239, 2243, 2251, 2267, 2269,\
2273, 2281, 2287, 2293, 2297, 2309, 2311,\
2333, 2339, 2341, 2347, 2351, 2357, 2371,\
2377, 2381, 2383, 2389, 2393, 2399, 2411,\
2417, 2423, 2437, 2441, 2447, 2459, 2467,\
2473, 2477, 2503, 2521, 2531, 2539, 2543,\
2549, 2551, 2557, 2579, 2591, 2593, 2609,\
2617, 2621, 2633, 2647, 2657, 2659, 2663,\
2671, 2677, 2683, 2687, 2689, 2693, 2699,\
2707, 2711, 2713, 2719, 2729, 2731, 2741,\
2749, 2753, 2767, 2777, 2789, 2791, 2797,\
2801, 2803, 2819, 2833, 2837, 2843, 2851,\
2857, 2861, 2879, 2887, 2897, 2903, 2909,\
2917, 2927, 2939, 2953, 2957, 2963, 2969,\
2971, 2999, 3001, 3011, 3019, 3023, 3037,\
3041, 3049, 3061, 3067, 3079, 3083, 3089,\
3109, 3119, 3121, 3137, 3163, 3167, 3169,\
3181, 3187, 3191, 3203, 3209, 3217, 3221,\
3229, 3251, 3253, 3257, 3259, 3271, 3299,\
3301, 3307, 3313, 3319, 3323, 3329, 3331,\
3343, 3347, 3359, 3361, 3371, 3373, 3389,\
3391, 3407, 3413, 3433, 3449, 3457, 3461,\
3463, 3467, 3469, 3491, 3499, 3511, 3517,\
3527, 3529, 3533, 3539, 3541, 3547, 3557,\
3559, 3571, 3581, 3583, 3593, 3607, 3613,\
3617, 3623, 3631, 3637, 3643, 3659, 3671,\
3673, 3677, 3691, 3697, 3701, 3709, 3719,\
3727, 3733, 3739, 3761, 3767, 3769, 3779,\
3793, 3797, 3803, 3821, 3823, 3833, 3847,\
3851, 3853, 3863, 3877, 3881, 3889, 3907,\
3911, 3917, 3919, 3923, 3929, 3931, 3943,\
3947, 3967, 3989, 4001, 4003, 4007, 4013,\
4019, 4021, 4027, 4049, 4051, 4057, 4073,\
4079, 4091, 4093, 4099, 4111, 4127, 4129,\
4133, 4139, 4153, 4157, 4159, 4177, 4201,\
4211, 4217, 4219, 4229, 4231, 4241, 4243,\
4253, 4259, 4261, 4271, 4273, 4283, 4289,\
4297, 4327, 4337, 4339, 4349, 4357, 4363,\
4373, 4391, 4397, 4409, 4421, 4423, 4441,\
4447, 4451, 4457, 4463, 4481, 4483, 4493,\
4507, 4513, 4517, 4519, 4523, 4547, 4549,\
4561, 4567, 4583, 4591, 4597, 4603, 4621,\
4637, 4639, 4643, 4649, 4651, 4657, 4663,\
4673, 4679, 4691, 4703, 4721, 4723, 4729,\
4733, 4751, 4759, 4783, 4787, 4789, 4793,\
4799, 4801, 4813, 4817, 4831, 4861, 4871,\
4877, 4889, 4903, 4909, 4919, 4931, 4933,\
4937, 4943, 4951, 4957, 4967, 4969, 4973,\
4987, 4993, 4999, 5003, 5009, 5011, 5021,\
5023, 5039, 5051, 5059, 5077, 5081, 5087,\
5099, 5101, 5107, 5113, 5119, 5147, 5153,\
5167, 5171, 5179, 5189, 5197, 5209, 5227,\
5231, 5233, 5237, 5261, 5273, 5279, 5281,\
5297, 5303, 5309, 5323, 5333, 5347, 5351,\
5381, 5387, 5393, 5399, 5407, 5413, 5417,\
5419, 5431, 5437, 5441, 5443, 5449, 5471,\
5477, 5479, 5483, 5501, 5503, 5507, 5519,\
5521, 5527, 5531, 5557, 5563, 5569, 5573,\
5581, 5591, 5623, 5639, 5641, 5647, 5651,\
5653, 5657, 5659, 5669, 5683, 5689, 5693,\
5701, 5711, 5717, 5737, 5741, 5743, 5749,\
5779, 5783, 5791, 5801, 5807, 5813, 5821,\
5827, 5839, 5843, 5849, 5851, 5857, 5861,\
5867, 5869, 5879, 5881, 5897, 5903, 5923,\
5927, 5939, 5953, 5981, 5987, 6007, 6011,\
6029, 6037, 6043, 6047, 6053, 6067, 6073,\
6079, 6089, 6091, 6101, 6113, 6121, 6131,\
6133, 6143, 6151, 6163, 6173, 6197, 6199,\
6203, 6211, 6217, 6221, 6229, 6247, 6257,\
6263, 6269, 6271, 6277, 6287, 6299, 6301,\
6311, 6317, 6323, 6329, 6337, 6343, 6353,\
6359, 6361, 6367, 6373, 6379, 6389, 6397,\
6421, 6427, 6449, 6451, 6469, 6473, 6481,\
6491, 6521, 6529, 6547, 6551, 6553, 6563,\
6569, 6571, 6577, 6581, 6599, 6607, 6619,\
6637, 6653, 6659, 6661, 6673, 6679, 6689,\
6691, 6701, 6703, 6709, 6719, 6733, 6737,\
6761, 6763, 6779, 6781, 6791, 6793, 6803,\
6823, 6827, 6829, 6833, 6841, 6857, 6863,\
6869, 6871, 6883, 6899, 6907, 6911, 6917,\
6947, 6949, 6959, 6961, 6967, 6971, 6977,\
6983, 6991, 6997, 7001, 7013, 7019, 7027,\
7039, 7043, 7057, 7069, 7079, 7103, 7109,\
7121, 7127, 7129, 7151, 7159, 7177, 7187,\
7193, 7207, 7211, 7213, 7219, 7229, 7237,\
7243, 7247, 7253, 7283, 7297, 7307, 7309,\
7321, 7331, 7333, 7349, 7351, 7369, 7393,\
7411, 7417, 7433, 7451, 7457, 7459, 7477,\
7481, 7487, 7489, 7499, 7507, 7517, 7523,\
7529, 7537, 7541, 7547, 7549, 7559, 7561,\
7573, 7577, 7583, 7589, 7591, 7603, 7607,\
7621, 7639, 7643, 7649, 7669, 7673, 7681,\
7687, 7691, 7699, 7703, 7717, 7723, 7727,\
7741, 7753, 7757, 7759, 7789, 7793, 7817,\
7823, 7829, 7841, 7853, 7867, 7873, 7877,\
7879, 7883, 7901, 7907, 7919, 7927, 7933,\
7937, 7949, 7951, 7963, 7993, 8009, 8011,\
8017, 8039, 8053, 8059, 8069, 8081, 8087,\
8089, 8093, 8101, 8111, 8117, 8123, 8147,\
8161, 8167, 8171, 8179, 8191, 8209, 8219,\
8221, 8231, 8233, 8237, 8243, 8263, 8269,\
8273, 8287, 8291, 8293, 8297, 8311, 8317,\
8329, 8353, 8363, 8369, 8377, 8387, 8389,\
8419, 8423, 8429, 8431, 8443, 8447, 8461,\
8467, 8501, 8513, 8521, 8527, 8537, 8539,\
8543, 8563, 8573, 8581, 8597, 8599, 8609,\
8623, 8627, 8629, 8641, 8647, 8663, 8669,\
8677, 8681, 8689, 8693, 8699, 8707, 8713,\
8719, 8731, 8737, 8741, 8747, 8753, 8761,\
8779, 8783, 8803, 8807, 8819, 8821, 8831,\
8837, 8839, 8849, 8861, 8863, 8867, 8887,\
8893, 8923, 8929, 8933, 8941, 8951, 8963,\
8969, 8971, 8999, 9001, 9007, 9011, 9013,\
9029, 9041, 9043, 9049, 9059, 9067, 9091,\
9103, 9109, 9127, 9133, 9137, 9151, 9157,\
9161, 9173, 9181, 9187, 9199, 9203, 9209,\
9221, 9227, 9239, 9241, 9257, 9277, 9281,\
9283, 9293, 9311, 9319, 9323, 9337, 9341,\
9343, 9349, 9371, 9377, 9391, 9397, 9403,\
9413, 9419, 9421, 9431, 9433, 9437, 9439,\
9461, 9463, 9467, 9473, 9479, 9491, 9497,\
9511, 9521, 9533, 9539, 9547, 9551, 9587,\
9601, 9613, 9619, 9623, 9629, 9631, 9643,\
9649, 9661, 9677, 9679, 9689, 9697, 9719,\
9721, 9733, 9739, 9743, 9749, 9767, 9769,\
9781, 9787, 9791, 9803, 9811, 9817, 9829,\
9833, 9839, 9851, 9857, 9859, 9871, 9883,\
9887, 9901, 9907, 9923, 9929, 9931, 9941,\
9949, 9967, 9973]);
# There are 1229 primes on the List
# The next prime is 10007. This List can be
# used to prove primality of any number
# smaller than 10007^2, or 100140049.
if (p in P) then # GAP does a fast binary search
~ return([true, true]); # (P) List held (p)
fi;
# Variable (a) is a "scratch use" variable.
a:=p mod 6; # All primes > 3 equal (6)(x)±1
if ((a<>1) and (a<>5)) then
~ return([false, true]); # (p) can't be prime
fi; # Only odd values of (p) pass this point
r:=RootInt(p); # Need square root of (p)
for a in P do
~ if ((p mod a)=0) then
~ ~ return([false, true]); # (p) was divisible
~ fi;
~ if (a>=r) then # (p) is a prime between
~ ~ return([true, true]); # 10007 and <100140049
~ fi;
od;
# The last simple thing is to check for whether
# or not (p) is a power of some smaller number.
# Thorough testing for this doesn't take very
# long, and various other composite numbers can
# be identified, as explained below.
a:=2; # 2 is for square root --already in (r).
repeat
~ if (IsEvenInt(r)) then # Even composites are
~ ~ r:=r-1; # already filtered out, so try an
~ fi; # odd number here (we might get lucky).
~ if ((p mod r)=0) then # Perfect powers and other
~ ~ return([false, true]); # composites are found.
~ fi;
# For example, if (p) is any number from 49 to
# 63, the integer part of its square root is 7.
# Its square is 49, but there are two other
# numbers that are divisible by 7, within the
# specified range: 56 and 63. For the integer
# parts of roots other than square roots, there
# are vastly more other composite numbers than
# pure powers that can be similarly found here.
# Consider the cubes of 7 and 8: 343 and 512
# respectively. So, any number from 343 to 511
# will have 7 as the integer part of its cube
# root, and every 7th number between (and
# including) 343 and 511 is discoverably
# divisible by 7, using that modulus test. So
# we might get lucky, in testing this sequence
# of roots, and not need the main algorithm to
# determine that (p) is composite.
~ a:=a+1; # Increment for computing next root
~ r:=RootInt(p,a);
until (r<10007); # DID smaller divisors; stop.
# Main algorithm, Part One, begins
# Variable (B) is for a List of binary data (p-1)
# Variable (t) is for powers of 2
# Variable (i) is a List index
# Variables (q) and (n) will be related to (p)
t:=2; B:=[0]; i:=2; q:=p-1; n:=q;
while(t<n) do # seek a power of 2 > (p-1)
~ B[i]:=0; t:=t*2; i:=i+1;
od;
# (i) is now an appropriate index value
# Next, replace some zeros in the (B) List
# with a Binary Representation of (q=p-1).
# Variable (k) is another List index --we
# retain the value in (i) for later use.
k:=i;
while(k>0) do
~ if (n>=t) then
~ ~ B[k]:=1; n:=n-t;
~ fi;
~ k:=k-1; # Associate next index with
~ t:=t/2; # a smaller power of 2
od; # This loop ends with (n) equal to Zero
# (q) still equals (p-1) for all comments below.
# This particular Binary Representation,
# while normal in the sense that it consists
# of Zeros and Ones, is BACKWARD. The One
# that references the most significant power
# of 2 is in the LAST List-element, not the 1st.
# Variable (m) is for the modulus we accumulate
# during the next loop
k:=1; # Reset List index to first element
t:=2; # In Base 2 the 1st-Position modulus is 2
m:=1; # Initialize Zeroth-Position modulus
# Variable (s) is for powers of 3; the reason
s:=3; # for doing Base 3 is explained later
a:=1; # using (a) for Base 3 modulus-accumulator
while(k<i) do
~ if (B[k]>0) then # Only use (t) here when
# it is relevant to our backward Binary
# Representation of (q).
~ ~ m:=((m*t) mod p); # Multiply moduli to
~ ~ a:=((a*s) mod p); # obtain the Modulus
~ fi; # at the "sum" Position.
~ t:=((t^2) mod p); # Square this "power of 2"
# to double Position from Zeroth, and get the
# particular Modulus at that Position.
~ s:=((s^2) mod p); # Square this power of 3
~ k:=k+1;
od;
if ((m<>1)or(a<>1)) then # Most composite
~ return([false, true]); # numbers are now
fi; # filtered out.
# The reason for doing Base 3 simultaneously
# with Base 2 has to do with the fact that
# certain non-primes, closely associated with
# powers of 2, can pass the test in Base 2,
# but fail in Base 3 (because they cannot be
# simultaneously as-closely-related to a power
# of 3). They are NOT the sort of pseudoprimes
# that can pass the test in EVERY Base.
# Main algorithm, Part Two, begins
# We will be trying a number of different Bases
# to test the Modulus at Position (q=p-1), and
# to test the Modulus at Position (q/2), and at
# Position (q/4), and at (q/8), etc. If any of
# them are not equal to One, then it MUST equal
# (q), because of the split-Modulus-Sequence-
# and-add thing that was described earlier. We
# will also test up to 100 other Modulus sums,
# just to be sure that all of them equal (p).
# Variables (r) and (s) are reassigned as
# indices for the (P) List of primes
for r in [0..1228] do
~ for s in [(r+1)..1229] do
~ ~ n:=1; # Initialize for finding modulus
# at Position (q), (q/2), (q/4)...
~ ~ if (r=0) then
~ ~ ~ t:=P[s]; # Get a prime Base from (P) List
~ ~ ~ if (t<4) then
~ ~ ~ ~ n:=2; # Already did Position (q) in
# Bases 2 & 3; start with Position (q/2)
~ ~ ~ fi;
~ ~ else
~ ~ ~ t:=P[r]*P[s]; # Make a composite Base
# from the (P) List of primes. The reason
# is explained by example: 1/41 in Base 2
# has period-length 20, in Base 3 it has
# period-length 8, but in Base 6 it has
# period-length 40. This phenomenon only
# seems to be true when the composite Base
# has only 2 factors. A Base like 30 has
# factors of 2, 3, 5, 6, 10, and 15, and
# if a reciprocal's period-length is not
# (p-1) in one of those Bases, it also will
# not have that period-length in Base 30.
# There is an additional peculiarity, in
# that if the Base is a perfect square
# number, NO reciprocal's period-length is
# equal to (p-1). So, no perfect-square
# Bases are computed here.
~ ~ fi;
~ ~ a:=t; # Copy/save the Base for later
~ ~ while ((n=1)or(B[n-1]=0)) do
# OK to figure modulus at current Position?
~ ~ ~ k:=n; # Set Index to "to use first"
# element of (q)'s Binary Representation
~ ~ ~ m:=1; # Zeroth-position Modulus
~ ~ ~ while(k<i) do
~ ~ ~ ~ if (B[k]>0) then
~ ~ ~ ~ ~ m:=((m*t) mod p);
~ ~ ~ ~ fi;
~ ~ ~ ~ t:=((t^2) mod p);
~ ~ ~ ~ k:=k+1;
~ ~ ~ od;
# Now have Modulus at current Position
~ ~ ~ if (m=1) then # If Modulus is 1,
~ ~ ~ ~ n:=n+1; # prepare to find Modulus
# half-way to the current Position
~ ~ ~ ~ t:=a; # Reset (t) to current Base
~ ~ ~ ~ continue; # do "while" test for
# is-it-OK? (can't halve an odd Position).
~ ~ ~ elif (n=1) then # Modulus wasn't 1
# at Position (q), using current Base?
~ ~ ~ ~ return([false, true]); # Found composite
# that passed Bases 2 and 3 in Part One
~ ~ ~ elif (m<>q) then # If Modulus not 1
# at half-way mark, then must equal (q)
~ ~ ~ ~ return([false, true]); # Not prime
~ ~ ~ else # Did! So test 100 more sums
~ ~ ~ ~ t:=1; # Reassign as Zeroth Modulus
~ ~ ~ ~ for j in [1..100] do
~ ~ ~ ~ ~ t:=((t*a) mod p); # next Modulus
~ ~ ~ ~ ~ m:=((m*a) mod p); # next Modulus
~ ~ ~ ~ ~ if ((t+m)<>p) then # The Moduli
# at start plus Moduli in the middle of
# the Modulus Series must sum to equal (p)
~ ~ ~ ~ ~ ~ return([false, true]); # Failed
~ ~ ~ ~ ~ fi;
~ ~ ~ ~ od;
~ ~ ~ ~ return([true, false]); # likely prime
~ ~ ~ fi;
~ ~ od; # All possible Position halvings,
# using current Base, were tried
~ od; # If loop(s) continues get next prime(s)
od; # from (P) List for next Base
return([false, false]); # (p) declared to
# be composite, because Modulus 1 was found
# at EVERY Position tested, in all those
# different Bases. However there is a
# small chance (p) is actually prime, as
# long as some things described herein
# remain to be Mathematically Proved.
end;
# End of IsAPrime() function