Suppose first that is composite. Then has a factor that is less than or equal to . Then divides , so does not divide . Therefore does not divide .
Suppose is a prime. Then each of the integers has an inverse modulo . (Indeed, if one such integer does not have an inverse, then for some distinct and modulo , , so that is a multiple of , when does not divide or —a contradiction.) This inverse is unique, and each number is the inverse of its inverse. If one integer is its own inverse, then so that or . Thus we can partition the set into pairs such that . It follows that is the product of these pairs times . Since the product of each pair is congruent to , we have as desired.
Let be a prime. Consider the field of integers modulo . By Fermat's Little Theorem, every nonzero element of this field is a root of the polynomial Since this field has only nonzero elements, it follows that Now, either , in which case for any integer , or is even. In either case, , so that If we set equal to 0, the theorem follows.
- (Source: ARML 2002) Let be an integer such that . Find the remainder when is divided by .
Multiplying both sides by yields Note that for all . Thus we are left with
- If is a prime greater than 2, define . Prove that is divisible by . Solution.
- Let be a prime number such that dividing by 4 leaves the remainder 1. Show that there is an integer such that is divisible by .