|
|
|
|
I have spent some time studying these numbers, and have found some patterns that you might find interesting. Starting on the "results" page, there is a list with columns "base" and "primes" that associate primes with a particular base. These numbers have the following relationship: if p is from the "prime" column and b is from the "base" column, then p^2 is a strong pseudoprime to base b. Although I don't have a mathematical proof, it appears that whenever any power of a prime is a pseudoprime to some base b, it is also a strong pseudoprime and it satisfies b^(p-1) == 1 (mod p^a).
I've also found that when p^a is a strong pseudoprime to base b, it is possible to generate a strong pseudoprime to base p^(a+1) by using the following formula:
(b^p) == c (mod p^(a+1))
where p^(a+1) is a strong pseudoprime to base c. This formula can be repeated to generate a series of bases for arbitrarily higher powers of prime p. What's more, if these bases are written as "radix p" numbers, then an interesting pattern emerges. For example, using p=5 and starting with base b=2, we get the following sequences of bases and powers of 5
| base | radix - 5 | pseudoprime | note |
|---|---|---|---|
| 2 | 2 | 5 | 2^4 == 1 (mod 5) |
| 7 | 12 | 5^2 | 7^4 == 1 (mod 5^2) |
| 57 | 212 | 5^3 | 57^4 == 1 (mod 5^3) |
| 182 | 1212 | 5^4 | 182^4 == 1 (mod 5^4) |
| 2057 | 31212 | 5^5 | 2057^4 == 1 (mod 5^5) |
| 14557 | 431212 | 5^6 | |
| 45807 | 2431212 | 5^7 |
As you can see, when the bases are written as radix-p numbers, the next base in the list simply adds a new more significant digit to the previous base. This helps to explain why each base tends to have only a small number of prime powers associated with it, since generating the base for a higher power of p can only give a new base that is the same or larger than the previous base.
Here are a few bases for higher powers of 487. I've separated the radix-487 "digits" with a -
| base | radix-487 | pseudoprime |
|---|---|---|
| 10 | 10 | 487 |
| 10 | 0-10 | 487^2 |
| 78028611 | 329-0-10 | 487^3 |
| 53439630597 | 462-329-0-10 | 487^4 |
For any prime p, the number p^a will be a strong pseudoprime to (p-1) incongruent bases. For p^2, these bases can be found by starting with (1, 2, ..., p-1) and computing (b^p % p^2). So, each of the numbers (1, 2, ..., p-1) can be use to start a "chain" of bases for powers p^a. The cases 1 and (p-1) end up being quite trivial, but the other chains are more interesting.
There is one other interesting characteristic -- within any single chain, where bases are derived by adding a new significant digit in front of the previous base, all of the bases that are part of the same chain will have the same multiplicative order modulo p^a. So, for the table above with bases derived by starting with 2 and deriving new bases for powers of 5, all of those bases have multiplicative order 4 when taken modulo their respective powers of 5. So, whenever a power of a prime is a strong pseudoprime to base b, the multiplicative order of b will be a factor of (p-1).
I hope you find this interesting.