Theorem of the week

Waring’s Problem: Lecture 2

April 30, 2012

In which we start in earnest.

Posted in Cambridge Maths Tripos, III Waring's Problem, Lecture | 3 Comments »

Waring’s Problem: Lecture 1

April 27, 2012

In which we introduce Waring‘s problem and have an overview of how to apply the Hardy-Littlewood circle method to solve it.

Read the rest of this entry »

Posted in Cambridge Maths Tripos, III Waring's Problem, Lecture | Leave a Comment »

Theorem 40: Sperner’s lemma about coloured triangles

February 25, 2012

I have a difficulty with this post, namely that I’ve previously written about a result called Sperner’s lemma, and this is a different one! I hope this won’t cause any confusion.

As the title suggests, this post is about coloured triangles. That’s not quite accurate, actually, but it was the best I could do in a short title. Now that I have more space, let me be a bit more precise.

Draw a triangle. Any triangle.

Subdivide it into little triangles, in any way you like.

Like this: or like this: for example.

Now you need three coloured pens. I’m going to assume that they are blue, red and green.

Colour one vertex of your triangle blue, one red, and one green.

OK so far?

Now you’re going to colour the vertices of all the little triangles. There are just two rules.

If a vertex is on the edge with red at one end and blue at the other, then you can colour it either red or blue but not green. And similarly for the other edges: you can use either of the colours at the end of the edge, but not the third.

And you can colour the vertices inside the triangle in any way you choose. Here’s my example.

All done?

Now I predict that … actually, I’ll wait to make my prediction. Why don’t you see whether you can guess what my prediction is, and then you can check over the fold.

You might also like to try the Triangle Game on NRICH.

Read the rest of this entry »

Posted in Cambridge Maths Tripos, II Topics in Analysis, Theorem | Leave a Comment »

Theorem 39: Euler’s criterion

February 4, 2012

I’ve previously written about Fermat’s Little Theorem, which tells us that if $p$ is a prime and $a$ is not divisible by $p$ , then $a^{p-1} \equiv 1 \pmod{p}$ . That’s not terribly exciting when $p = 2$ , so let’s concentrate on odd primes $p$ in this post. Then $\frac{p-1}{2}$ is a whole number, so it makes sense (in the modular arithmetic world) to let $x = a^{\frac{p-1}{2}}$ . Then Fermat‘s Little Theorem tells us that $x^2 \equiv 1 \pmod{p}$ .

How many possibilities for $x$ are there (modulo $p$ , of course), if we know that $x^2 \equiv 1 \pmod{p}$ ?

Well, that congruence tells us that $(x - 1)(x + 1) \equiv 0 \pmod{p}$ . But, in the jargon, “there are no zero-divisors modulo a prime”. That is, if $mn \equiv 0 \pmod{p}$ , then $m \equiv 0 \pmod{p}$ or $n \equiv 0 \pmod{p}$ . (Note that we really do need $p$ to be prime here — try some examples!)

So if $x$ is such that $x^2 \equiv 1 \pmod{p}$ , then $x \equiv \pm 1 \pmod{p}$ . Which is pretty nice. (Again, we really needed $p$ to be prime here. Try working modulo 8 instead, and see what happens there!)

Back to where we started. We said that if $a$ is not divisible by the odd prime $p$ , then $(a^{\frac{p-1}{2}})^2 \equiv 1 \pmod{p}$ , so we know know that $a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}$ .

That narrows down the possibilities a lot. It’s no good trying to tell me that $19^{50} \equiv 7 \pmod{101}$ — I simply shan’t believe you (even without doing any calculations). But tell me that $19^{50} \equiv 1 \pmod{101}$ , or that $19^{50} \equiv -1 \pmod{101}$ , and I have a problem — how do I know which is correct? Read the rest of this entry »