In July of 1991 the readers of 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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4