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 is prime then (mod ).

Deduce that if (mod 4) then

(mod ).

(ii) Suppose that is a prime of the form . Show that if (mod ) then (mod ).

(iii) Deduce that if is an odd prime, then the congruence

(mod )

has exactly two solutions (modulo ) if (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 has a unique multiplicative inverse mod . [Legitimate just to state this because it is from an earlier part of the course.] Therefore we can partition the integers into sets of the form . [I didn’t spell out that the inverse of is , since that is so obvious that I cannot imagine losing marks for not stating it explicitly.] Each such set consists of two elements unless , or equivalently (mod ). But if and only if if and only if (mod ). [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 , 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 then 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 has a unique multiplicative inverse mod . Therefore we can partition the integers into sets of the form . Each such set consists of two elements unless , or equivalently (mod ). But if and only if if and only if (mod ). If then 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 ? Well, they both say that something equals -1 (mod ). In both cases that thing is a product of numbers. In fact, in both cases it’s a product of numbers.

The products are not actually *equal*, though that is not too surprising, since otherwise we wouldn’t need the condition that (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 numbers. The difference between them (in the sense of thing that distinguishes them) is that the remaining numbers are in one case the last numbers and in the other case the first numbers again. So those two need to have equal products. Ah, but the last numbers are just *minus* the first numbers. So the product of the last numbers is times the product of the first numbers. So they’re equal as long as is even, and that’s where the condition comes in that should be congruent to 1 mod 4.

The write-up:

The product is congruent to times the product . Since 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 by the first to obtain .

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 is cyclic. (Here 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 , then we have some number such that the powers run through all the non-zero integers mod . Therefore, if we are given an integer we can “take logs to base ” and write it as . Then mod if and only if mod . Now , so the only multiples of that can be are , , and . Of these, and are not multiples of 4, so those are ruled out too. But if or , then or , so (mod ).

See here for more examples of results that follow easily from the fact that the multiplicative group mod is cyclic, but now let me think about what the examiner intended for this question.

We’re given that and that (mod ). We want to prove that (mod ). We can’t see instantly why that should be, so let us begin by writing down what we do know about , which is that it must be . (The justification for this is that , so if , then one of 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 cannot be congruent to . 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 be our generator again. To show that cannot be , we should think about what is as a power of and what is as a power of . Well, we assume that , so that tells us that . So basically all we know is that is an even power of (which makes sense because the order of in the multiplicative group is even). What about ? Well, and is a square root of , so there’s not much choice for the power: it has to be . But that’s an odd power, so and cannot be the same.

Can we do anything like this without assuming the existence of a generator ? Did we need to be a generator? Let’s see what we can do with . We don’t know that is a generator, but one crucial fact we used about — that , applies just as well to , by Fermat’s little theorem. So we know that . What does that tell us about ? That . That is, 1 is an odd power of . But that rules out equalling , since all odd powers of are .

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 then , so . But if , then , which contradicts Fermat’s little theorem. Therefore, .

(iii) The “deduce that” here speaks for itself. It’s also clear that we are going to use (i) to prove the case and (ii) to prove the case. Let’s do the 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 has at most 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 then you have a factor . Dividing by that factor you have a polynomial of degree one less.) Finally, we know that if is a solution, then so is , which is different from because and is odd. Here’s what I’d write.

By part (i) we have at least one solution when . This solution is clearly not zero, so it is distinct from , which is also a solution. And a quadratic equation mod has at most two solutions. So we are done in this case.

What about when ? I see now that I must have done something that the examiner didn’t intend, because I proved that had no solutions as part of the proof of part (ii). The answer the examiner is clearly looking for is this.

Now let . If , then , so by part (ii) , which is a contradiction.

So how do we prove part (ii) without mentioning that cannot be -1? Let’s try applying Fermat’s little theorem straight off. Probably I should have done that earlier. We know that (mod ). If , that tells us that , so it follows straight away that .

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.

May 25, 2012 at 3:24 pm |

[…] For the numbers fans out there. […]

May 25, 2012 at 3:24 pm |

[…] For the numbers fans out there. […]

June 5, 2012 at 10:30 pm |

In response to your solution to part (ii).

I believe the knowledge that Z_p\{0} is a group under multiplication modulo p is enough:

|Z_p\{0}| = p-1 = 2 (mod 4) thanks to the condition: p = 3 (mod 4).

By Lagrange’s theorem the order of each element of a group must divide the order of the group, therefore Z_p\{0} does not contain an element of order 4. As such, if x^4=1, we must have either x^2=1 or x=1, in both cases the result follows.

July 9, 2012 at 4:33 am |

Interesting ideas here. I am still trying to figure some parts out though.