leave different remainders which must be all relatively prime to . Thus, by pigeonhole all must be distinct for otherwise two of them will leave the same remainder mod m. Thus, can be rearranged so that it is the sum of the first integers relatively prime to . Say are the first integers relatively prime to , then are still relatively prime to . Thus, , this means the sum of the first relatively prime integers is . Since is even we can write which leaves remainder 0 upon division by m.