No subject

[John Conway]

On Sun, 31 Aug 2003, benoit quoted:

> > Is the following conjecture true?
> > (1): 3^r  divides  (10^k -1)/9   iff  3^r divides k.
> > (I verified  it to be true for  r = 1,2,3 and  4.)

   and wrote:-
> 
> About this one, seems to me you can state something more general. 


    The situation has been understood for a long time.  Let's ask
for the exact power of some prime  p  that divides  a^K - 1.  Then
the assertion is that if  k  is the smallest positive number for which  
p  itself divides  a^k - 1,  and  a^k - 1  is exactly divisible by
p^i,  then  a^K - 1  will be divisible by  p  precisely when  K  is
a multiple of  k,  and then the exact power of  p  that divides it 
will be  p^(i+j),  where  p^j  is the exact power of  p  that divides
K/k.  

    In other words, the first time you get a multiple of  p  you
can "accidentally" get a higher power than the first,  but from
then on you can only get more p's by putting them into the exponent.

   Examples:  the first time  3^K - 1  is divisible by  11  is at
3^5 - 1, which is divisible precisely by  11^2.  So  3^K - 1  will
be divisible by  11^(2+j)  only when  KI  is divisible by  5 times 11^j.

    Similarly,  2^1092 - 1  happens to be divisible by just 1093^2,
so  2^(1092.1093^j) - 1  will be divisible by just  1093^(2+j).

     John Conway