Theorem 40: Sperner’s lemma about coloured triangles

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.

Theorem 39: Euler’s criterion

I’ve previously written about Fermat’s Little Theorem, which tells us that if is a prime and is not divisible by , then .  That’s not terribly exciting when , so let’s concentrate on odd primes in this post.  Then is a whole number, so it makes sense (in the modular arithmetic world) to let .  Then Fermat‘s Little Theorem tells us that .

How many possibilities for are there (modulo , of course), if we know that ?

Well, that congruence tells us that .  But, in the jargon, “there are no zero-divisors modulo a prime”.  That is, if , then or .  (Note that we really do need to be prime here — try some examples!)

So if is such that , then .  Which is pretty nice.  (Again, we really needed to be prime here.  Try working modulo 8 instead, and see what happens there!)

Back to where we started.  We said that if is not divisible by the odd prime , then , so we know know that .

That narrows down the possibilities a lot.  It’s no good trying to tell me that — I simply shan’t believe you (even without doing any calculations).  But tell me that , or that , and I have a problem — how do I know which is correct?