We will prove that . Then for all , and thus if , .
We first prove that if is a prime, then .
Consider the set , where is the smallest value such that . (Such a value must exist since the number of possible values for is limited by the numbers less than . Thus at some point two of these powers, say and we must have (I assume ). Thus must be a multiple of p. Since by assumption does not have as a factor, neither does , and thus must have as a factor. This implies that .)
The set of all powers of is a subgroup of the group of all numbers from 1 to under multiplication. We now rely on the theorem of group theory that the size of a subgroup always evenly divides the size of the group itself. That means that r must evenly divide , and thus Note that this theorem is true, even if is greater than . Thus for any , for some integer .
We now show that
Using and using the
binomial theorem, we have