prime power Sierpinski numbers

[snorton]

Has anyone considered the problem of determining the smallest prime power (including a prime) which is a Sierpinski number ? As 271129 is a Sierpinski prime it is clearly an upper bound, and if we can eliminate smaller primes there aren't that many other cases to consider.

This problem arises as follows. Let n be a positive integer and define M_n to be the group of integers mod n coprime to n under multiplication. Then the book "Solved and Unsolved Problems in Number Theory" by Daniel Shanks proves the following:

o If n is a prime power then M_n is cyclic of order phi(n), unless n is even and at least 8, in which case M_n is the direct product of cyclic groups of order 2 and phi(n)/2.

o If n is not a prime power then M_n is the direct product of the various M_q where the q's form the unique set of prime powers which are coprime and have n as their product.

o Any finite abelian group G is the subgroup of infinitely many M_n. This uses a weak form of Dirichlet's theorem on the infinitude of primes in arithmetic progressions.

o The cycle graph for M_n is planar if and only if M_n is the direct product of a 2-group G and a cyclic group H (which may be assumed to have odd order). The graph will then consist of |H| lobes having a structure determined by G. (The terminology is taken from the book.)

Using a stronger form of Dirichlet's theorem one can strengthen the third result to say that for any G there are
infinitely many H and n such that M_n is isomorphic to G X H. Furthermore, if G is a 2-group then H can be taken to be cyclic of odd order.

It is then natural to ask the question of whether if G is cyclic of odd order H can be taken to be a 2-group. The answer is no, and it can be shown that the smallest counterexample is the least prime power that's a Sierpinski number and whose prime root is not a Fermat prime.

So the question is whether 271129 is the smallest odd number such that no M_n has that number of lobes.

One can also ask what happens if G is of odd order but not necessarily cyclic. For example one may take G to be elementary abelian of order 3^11 (= 177147, the largest power of 3 less than 271129). In this particular case, noting that 3 is a Fermat prime, one needs to know whether there are at least 10 primes of the form 3*2^k+1 -- if there are, then we can take n to be 9 times the product of these primes and M_n will be the direct product of G with a 2-group.

One further question: if m is taken to be a random integer between 1 and n what's the probability that the cycle graph of M_m is planar ? I think the answer tends to zero as n tends to infinity but very slowly.

[axn]

Originally Posted by snorton

Has anyone considered the problem of determining the smallest prime power (including a prime) which is a Sierpinski number ? As 271129 is a Sierpinski prime it is clearly an upper bound, and if we can eliminate smaller primes there aren't that many other cases to consider.

Between SoB, PSP, and ESP projects, all k's less than 271129 are being tackled. Look at their outstanding k's to see the list of primes (I don't think a prime power is there) yet to be eliminated.