Divisors of an n-term Geometric Series

In July of 1991 the readers if American Mathematical Monthly were
challenged to prove that if p is an odd prime and k=1 (mod p), then 
for any positive integer n the highest power of p dividing the finite
geometric series

                1 + k + k^2 + ... + k^(n-1)                       (1)

is equal to the highest power of p dividing n.

PROOF:  Let p be a prime (odd or even) and let n = h p^s where h is 
co-prime to p.  We have

                                        1 - k^(h p^s)
      1 + k + k^2 + ... + k^(n-1)   =   -------------
                                            1 - k

The numerator of the right side factors as

     [1 - k^(p^s)] [1 + k^(p^s) + k^(2p^s) + ... + k^((h-1)p^s)]

Since k=1 (mod p) the right hand factor is clearly congruent to h 
(mod p), and so it is not divisible by p.  Therefore, we need only 
consider the highest power of p dividing

 1 - k^(p^s)     s  /                                       
 ----------- = PROD( 1 + [k^(p^{s-j})] + [k^(p^{s-j})]^2 +..
    1 - k       j=1 \                                       

                                                            \
                                       + [k^(p^{s-j})]^(p-1) )      (2)
                                                            /

Now, if p equals an odd prime and k=1 (mod p), it follows that k^u
(where u = p^{s-j}) is of the form 1+cp for some integer c.  Therefore 
each of the factors of the product (2) has the form

          1 + (1+cp) + (1+cp)^2 + ... + (1+cp)^(p-1)

Expanding the binomial terms and grouping terms by powers of p gives

            /  p  \         /  p  \
       p + (       )(cp) + (       )(cp)^2 + ... + (cp)^(p-1)
            \ p-2 /         \ p-3 /

The coefficient of the second term is p(p-1)/2, which is divisible 
by p for any odd prime p.  It follows that every term after the first 
is divisible by p^2, and so the total sum is divisible by exactly 
one power of p.  Thus, each of the s factors in (1) is divisible by 
exactly one power of p, so the product is divisible by exactly s
powers of p, as is n itself.  This completes the proof.

The challenge problem also asked for a proof of the analogous theorem
for powers of 2.  Specifically, if k=1 (mod 4), the highest power of
2 dividing (1) equals the highest power of 2 dividing n.

PROOF:  Observe that if p=2 then the right hand side of (2) reduces
to
                  s   /               \
                PROD ( 1 + k^[2^{s-j}] )
                 j=1  \               /

Also, if k=1 (mod 4) it follows that k^u = 1 (mod 4) where u=2s-j.  
Thus the above product consists of s factors of the form 4m+2, each 
of which is divisible by exactly one power of 2, so the product is 
divisible by exactly s powers of 2, as is n itself.  This completes 
the proof.

Return to MathPages Main Menu