VizualBusiness: A look at a few Tripos questions VIII

A look at a few Tripos questions VIII:
Now for a question on modular arithmetic. As with countability, there is a very high chance of a question on this topic. [Added after the post was written: as usual I wrote down my thoughts about this question as I had them, and I didn't spot the best approach to part (ii) of the question until after I had come up with some less good approaches. So my recommendations evolve through the post, with some of the later ones superseding some of the earlier ones.]
6C. (i) Prove Wilson’s theorem: if $p$ is prime then $(p-1)!\equiv -1$ (mod $p$ ).
Deduce that if $p\equiv 1$ (mod 4) then
$\displaystyle \Bigl(\bigl(\frac{p-1}2\bigr)!\Bigr)^2\equiv -1$ (mod $p$ ).
(ii) Suppose that $p$ is a prime of the form $4k+3$ . Show that if $x^4\equiv 1$ (mod $p$ ) then $x^2\equiv 1$ (mod $p$ ).
(iii) Deduce that if $p$ is an odd prime, then the congruence
$\displaystyle x^2\equiv -1$ (mod $p$ )
has exactly two solutions (modulo $p$ ) if $p\equiv 1$ (mod 4), and none otherwise.

The first part is pure bookwork, so I’m just going to write out the answer fairly concisely. I’ll add a couple of small comments in square brackets.
Every number between 1 and $p-1$ has a unique multiplicative inverse mod $p$ . [Legitimate just to state this because it is from an earlier part of the course.] Therefore we can partition the integers $1,2,\dots,p-1$ into sets of the form $\{a,a^{-1}\}$ . [I didn't spell out that the inverse of $a^{-1}$ is $a$ , since that is so obvious that I cannot imagine losing marks for not stating it explicitly.] Each such set consists of two elements unless $a=a^{-1}$ , or equivalently $a^2\equiv 1$ (mod $p$ ). But $x^2\equiv 1$ if and only if $(x+1)(x-1)\equiv 0$ if and only if $x\equiv\pm 1$ (mod $p$ ). [I could have said slightly more or slightly less, but this seems about right: it shows that I understand what is going on but doesn't spell out everything. For example, I clearly used the fact that there are no non-trivial zero divisors mod $p$ , but that's easily seen to be equivalent to the existence of multiplicative inverses, so I felt that in a sense I had already implicitly stated it.] If $a\ne a^{-1}$ then $aa^{-1}\equiv 1$ and the product of the remaining numbers, 1 and -1, is -1. The result follows.
If you want to see how long that was without the additional comments, then here it is. It’s a sort of model answer, but it shouldn’t be thought of as in any sense unique, since I made a number of small judgments that others might have made differently. But the basic principle is important: you should leave a sceptical examiner in no (reasonable) doubt that you understand the material.
Every number between 1 and $p-1$ has a unique multiplicative inverse mod $p$ . Therefore we can partition the integers $1,2,\dots,p-1$ into sets of the form $\{a,a^{-1}\}$ . Each such set consists of two elements unless $a=a^{-1}$ , or equivalently $a^2\equiv 1$ (mod $p$ ). But $x^2\equiv 1$ if and only if $(x+1)(x-1)\equiv 0$ if and only if $x\equiv\pm 1$ (mod $p$ ). If $a\ne a^{-1}$ then $aa^{-1}\equiv 1$ and the product of the remaining numbers, 1 and -1, is -1. The result follows.
Now for the second part of (i). This is often set as an exercise, so perhaps it was in the year in question. But even if not, the “deduce that” makes it by no means an impossible question (though one that could be difficult if your brain is freezing up in the middle of an exam). How can we relate the new equation to the equation $(p-1)!\equiv -1$ ? Well, they both say that something equals -1 (mod $p$ ). In both cases that thing is a product of numbers. In fact, in both cases it’s a product of $p-1$ numbers.
The products are not actually equal, though that is not too surprising, since otherwise we wouldn’t need the condition that $p\equiv 1$ (mod 4). (It is extremely unlikely that an examiner would be as cruel as to state an irrelevant condition.)
Another observation is that both products involve the first $(p-1)/2$ numbers. The difference between them (in the sense of thing that distinguishes them) is that the remaining numbers are in one case the last $(p-1)/2$ numbers and in the other case the first $(p-1)/2$ numbers again. So those two need to have equal products. Ah, but the last $(p-1)/2$ numbers are just minus the first $(p-1)/2$ numbers. So the product of the last numbers is $(-1)^{(p-1)/2}$ times the product of the first numbers. So they’re equal as long as $(p-1)/2$ is even, and that’s where the condition comes in that $p$ should be congruent to 1 mod 4.
The write-up:
The product $1.2\dots (p-1)/2$ is congruent to $(-1)^{(p-1)/2}$ times the product $(p+1)/2\dots(p-1)$ . Since $p\equiv 1$ mod 4, this means that the two products are equal. The result now follows from Wilson’s theorem, since we can replace the second product in $(p-1)!$ by the first to obtain $\Bigl(\bigl(\frac{p-1}2\bigr)!\Bigr)^2$ .
What I wrote there was not what I would write if I were writing a textbook, where the aim is to explain a result to somebody who hasn’t seen it before. Here, the aim is to demonstrate that I know what is going on to someone who has definitely seen it before. That isn’t a licence to be sloppy, but it does allow one to be reasonably concise when it’s clear how to fill in the details. Here, for instance, I couldn’t quite face explaining formally why the two products were the same, so I was slightly informal — using phrases like “we can replace” as part of a brief demonstration that I knew how to justify the claim I had made in the previous sentence.
Now for part (ii). Let me first say how I think about all questions like this. This is a slight digression, because it’s not telling you how to answer the question. However, it is something that’s helpful to bear in mind.
I can sum it up in one short sentence: the multiplicative group mod $p$ is cyclic. (Here $p$ must be a prime.) The proof of this fact is rather lovely, because it works despite the fact that there isn’t an easy way of finding a generator. However, it’s too long to write out while solving this question, and it isn’t a fact that you can just quote, since it is more advanced than what you are being asked to prove.
Why does it imply the result asked for here? Well, if $p=4k+3$ , then we have some number $u$ such that the powers $1,u,u^2,\dots,u^{4k+2}$ run through all the non-zero integers mod $p$ . Therefore, if we are given an integer $x$ we can “take logs to base $u$ ” and write it as $u^r$ . Then $x^4\equiv 1$ mod $p$ if and only if $4r\equiv 0$ mod $4k+2$ . Now $r\leq 4k+2$ , so the only multiples of $4k+2$ that $4r$ can be are $4k+2$ , $8k+4$ , $12k+6$ and $16k+8$ . Of these, $4k+2$ and $12k+6$ are not multiples of 4, so those are ruled out too. But if $4r=8k+4$ or $16k+8$ , then $2r=4k+2$ or $8k+4$ , so $x^2=u^{2r}\equiv 1$ (mod $p$ ).
See here for more examples of results that follow easily from the fact that the multiplicative group mod $p$ is cyclic, but now let me think about what the examiner intended for this question.
We’re given that $p=4k+3$ and that $x^4\equiv 1$ (mod $p$ ). We want to prove that $x^2\equiv 1$ (mod $p$ ). We can’t see instantly why that should be, so let us begin by writing down what we do know about $x^2$ , which is that it must be $\pm 1$ . (The justification for this is that $x^4-1=(x^2+1)(x^2-1)$ , so if $x^4-1\equiv 0$ , then one of $x^2\pm 1$ must also be 0. In other words, is essentially the same as it would be if we were talking about real numbers.)
That reduces our task to that of showing that $x^2$ cannot be congruent to $-1$ . Now let’s think about why that is the case, using the fact that the multiplicative group is cyclic, but later we shall attempt to prove all the facts we actually use in more elementary ways. So let $u$ be our generator again. To show that $x^2$ cannot be $-1$ , we should think about what $x^2$ is as a power of $u$ and what $-1$ is as a power of $u$ . Well, we assume that $x=u^r$ , so that tells us that $x^2=u^{2r}$ . So basically all we know is that $x^2$ is an even power of $u$ (which makes sense because the order of $u$ in the multiplicative group is even). What about $-1$ ? Well, $u^{4k+2}\equiv 1$ and $-1$ is a square root of $1$ , so there’s not much choice for the power: it has to be $u^{2k+1}$ . But that’s an odd power, so $x^2$ and $-1$ cannot be the same.
Can we do anything like this without assuming the existence of a generator $u$ ? Did we need $u$ to be a generator? Let’s see what we can do with $x$ . We don’t know that $x$ is a generator, but one crucial fact we used about $u$ — that $u^{4k+2}\equiv 1$ , applies just as well to $x$ , by Fermat’s little theorem. So we know that $x^{4k+2}\equiv 1$ . What does that tell us about $x^2$ ? That $(x^2)^{2k+1}\equiv 1$ . That is, 1 is an odd power of $x^2$ . But that rules out $x^2$ equalling $-1$ , since all odd powers of $-1$ are $-1$ .
On reflection, I’m not sure that it helped all that much to know that the multiplicative group is cyclic, though it does for some quite similar questions and is in general a good fact to know. Perhaps a more useful principle for questions like this would be to use Fermat’s little theorem and elementary facts about divisibility. Here is what I’d actually write.
If $x^4\equiv 1$ then $(x^2+1)(x^2-1)\equiv 0$ , so $x^2\equiv\pm 1$ . But if $x^2\equiv -1$ , then $x^{4k+2}\equiv(-1)^{2k+1}=-1$ , which contradicts Fermat’s little theorem. Therefore, $x^2\equiv 1$ .
(iii) The “deduce that” here speaks for itself. It’s also clear that we are going to use (i) to prove the $p\equiv 1$ case and (ii) to prove the $p\equiv 3$ case. Let’s do the $p\equiv 1$ case first.
We certainly know from the first part that there is at least one solution. We also know that there are at most two solutions, by the fact that a polynomial of degree $d$ has at most $d$ solutions, a result that is valid for any field, with essentially the same proof as the one that works for the reals. (If you’ve got a root $a$ then you have a factor $x-a$ . Dividing by that factor you have a polynomial of degree one less.) Finally, we know that if $x$ is a solution, then so is $-x$ , which is different from $x$ because $x\ne 0$ and $p$ is odd. Here’s what I’d write.
By part (i) we have at least one solution when $p=4k+1$ . This solution $x$ is clearly not zero, so it is distinct from $-x$ , which is also a solution. And a quadratic equation mod $p$ has at most two solutions. So we are done in this case.
What about when $p=4k+3$ ? I see now that I must have done something that the examiner didn’t intend, because I proved that $x^2\equiv -1$ had no solutions as part of the proof of part (ii). The answer the examiner is clearly looking for is this.
Now let $p=4k+3$ . If $x^2\equiv -1$ , then $x^4\equiv 1$ , so by part (ii) $x^2\equiv 1$ , which is a contradiction.
So how do we prove part (ii) without mentioning that $x^2$ cannot be -1? Let’s try applying Fermat’s little theorem straight off. Probably I should have done that earlier. We know that $x^{4k+2}\equiv 1$ (mod $p$ ). If $x^4\equiv 1$ , that tells us that $x^{4k}\equiv 1$ , so it follows straight away that $x^2\equiv 1$ .
That is a shorter and neater argument than the one I came up with (not that mine was hugely long). Where I slipped up was in not following my own advice, which was partly because I hadn’t formulated it. But here it is again, slightly reformulated. For this kind of question, apply Fermat’s little theorem before you even think. Then see whether what you are being asked to prove follows easily from what you have just written down together with a few simple observations about divisibility.