No subject
John Conway
conway at Math.Princeton.EDU
Tue Sep 2 18:37:57 CEST 2003
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
More information about the SeqFan
mailing list