View Single Post
Old 2006-07-21, 20:17   #14
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3·11 Posts
Default

We will treat the Riesel and Sierpinski cases separately (the first part applies to both cases).

Suppose for contradiction, that we have a b, with a finite covering set (for n>0) S={p_1, p_2, ..., p_k}. We can assume wlog (without loss of generality) that all the p_i's are prime. If p_i|b for some i then p_i does not divide (b-1)*b^n+-1. So we can assume wlog that p_i does not divide b for any i. Also, for n>0, (b-1)*b^n+/-1 cannot be even so we can assume that 2 is not in S (this avoids S={2}, which would be a special case for the argument below)

For each n (we have assumed that) there exists a p_i in our set S such that p_i|(b-1)*b^n+/-1.

Riesel case:
consider when n=((p_1-1)*(p_2-1)*...*(p_k-1))-1
If there is an i for which p_i|(b-1)*b^n-1 then
1=(b-1)*b^((p_i-1)*c-1) mod p_i (for some positive integer c)
so b=(b-1)*b^((p_i-1)*c) mod p_i
=((b-1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b)
=(b-1) mod p_i
so 0=-1 mod p_i. Contradiction! Therefore such a b cannot exist (for Riesels).

Sierpinski Case:
This is quite similar. In this case we let n=((p_1-1)*(p_2-1)*...*(p_k-1))
If there is an i for which p_i|(b-1)*b^n+1 then
-1=(b-1)*b^((p_i-1)*c) mod p_i (for some positive integer c)
=((b-1)*1^c) mod p_i (by Fermat's little theorem, since p_i does not divide b)
=(b-1) mod p_i
so b=0 mod p_i
So p_i|b. But we assumed that p_i did not divide b. Contradiction!
Therefore such a b cannot exist (for Siepinskis).

Thus we can't have such a b with a finite covering set, so if there exists a b such that (b-1) is Riesel (or Sierpinski) base b, it must have an infinite covering set.

Last fiddled with by konrad127123 on 2006-07-21 at 20:46
konrad127123 is offline   Reply With Quote