So, where are we? Recall that we are assuming (in order to get a contradiction) that is not prime, and we picked a smallish divisor (“smallish” meaning ). We then defined the set as
that is, combinations of and where the coefficients are between and . We defined a binary operation on which works by multiplying and then reducing the coefficients . This is not a group, since for example doesn’t have an inverse. But in the last post we saw that we can make a group simply by including only the elements from that do have inverses.
Recall that is in (as long as is not —which it can’t be, since is odd), and we know that , so has an inverse and we conclude .
You might enjoy figuring out what looks like in the case . Tomorrow, we’ll start thinking about the implications of our assumption that is divisible by , and in particular what it means about the order of in .