View Single Post
 2006-07-21, 20:17 #14 konrad127123     Jun 2005 3·11 Posts 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