Four eight seven

Comments on the 487 problem

Steve Jacobs

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

baseradix - 5pseudoprimenote
2252^4 == 1 (mod 5)
7125^27^4 == 1 (mod 5^2)
572125^357^4 == 1 (mod 5^3)
18212125^4182^4 == 1 (mod 5^4)
2057312125^52057^4 == 1 (mod 5^5)

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.