Recall that we are trying to prove that if is divisible by , then is prime. So let’s suppose is divisible by . We’ll prove this by contradiction, so suppose is not prime: if we can derive a contradiction, then this assumption must have been incorrect.

If is not prime then it must have some nontrivial divisors. Note that divisors of any number always come in pairs that multiply to the given number, . If is a perfect square then the two divisors might be equal, but in general one divisor will be smaller than and one will be bigger. In any case, we know we can pick some divisor of , call it , such that .¹

Now define the set as follows:

.

That is, is the set of all things of the form where and are both integers between 0 (inclusive) and (exclusive). So (assuming is big enough) contains things like and and (just set ) and (set ). And, yes, you guessed it, also contains . It doesn’t seem to contain , but we’ll see in a minute that it actually sorta kinda does.

We now introduce a binary operation on elements of , which we want to be like multiplication. But if we just multiply two elements of in the obvious way we won’t necessarily end up with something in : the resulting coefficients and might be too big. So the operation we actually introduce is this: multiply in the usual way, and then at the end reduce the coefficients and . For example, if then

.

That is, we distribute out the product and collect up like terms, resulting in , and then take the remainder of both and when divided by .

Since we are considering coefficients equivalent , we can say that does contain in a sense, since . Indeed, we can check that

.

So this representation of still interacts with in the right way.

So, is a group? I’ll let you think about it until tomorrow!

References