## 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.
```