## Archive for the ‘IA Numbers & Sets’ Category

### Theorem 42: Fermat’s Last Theorem

October 25, 2012

I’ve previously written about Fermat’s Little Theorem, but today it’s time for his (perhaps more famous) Last Theorem.  Today’s blog post comes in audio form, with help from Melvyn Bragg, Marcus du Sautoy and Samir Siksek.

### Theorem 36: the Cantor set is an uncountable set with zero measure

September 30, 2010

This week’s post is by Laura Irvine, who is just about to start her second year reading Mathematics at Murray Edwards College, Cambridge.  Thanks very much, Laura!

First of all, what is the Cantor set?

To form the Cantor set, start with the closed interval $[0,1]$ (this means $0$ and $1$ are included in the interval) and remove the middle open third of the interval (i.e. remove ( $\frac{1}{3}$, $\frac{2}{3}$) where the curved brackets mean the interval is open, so $\frac{1}{3}$ and $\frac{2}{3}$ are not themselves in the interval).  You should be left with two disjoint closed intervals: $[0, \frac{1}{3}]$ and $[\frac{2}{3}, 1]$.  I’m going to call this step the first iteration.

Then do the same thing to each of these intervals: remove the middle third of each to get the new intervals as $[0, \frac{1}{9}]$, $[\frac{2}{9}, \frac{1}{3}]$, $[\frac{2}{3}, \frac{7}{9}]$, $[\frac{8}{9}, 1]$.  Then remove the middle third of each of these intervals.  Keep repeating this process and the Cantor set is the set of all the points in the interval $[0,1]$ that are never removed.  So the first few steps of the process look like this: Do you understand how this set is formed?  Can you think of some points that are in the Cantor set?

Well, $0$ will never be removed: the first closed interval after the $n^{\textrm{th}}$ iteration would be $[0, \frac{1}{3^n}]$ so $0$ will be in the infinite intersection of the first interval of each step.  The other interval endpoints are points in the set too.  It turns out that there are also points that are in the set that aren’t interval endpoints.

An interesting and, in my opinion, rather surprising property of the Cantor set is that it has measure $0$, despite being an uncountable set!  The fact it is uncountable means there is no way of writing all the numbers in the Cantor set in a list.

So, intuitively, this is saying that if all the points in the Cantor set were lined up next to each other, the line would have length $0$ and yet there are infinitely many points in the set.  How weird is that?!

### Theorem 31: the non-zero integers (mod p) form a group under multiplication

July 12, 2010

I did a couple of sessions with groups of 15 and 16 year olds last week.  I wanted to work with them on ideas involving squares (quadratic residues) in modular arithmetic, but that meant understanding what modular arithmetic was about, so I started by introducing that idea.  I’d like to write about part of what I did in the sessions, because I felt it was quite a successful activity and I hope you might find it interesting too.  I encourage you to try these things for yourself, rather than just reading!

So, modular arithmetic.  We started by noticing that 3248 cannot be a square, because no square ends in an 8.  What was important to us was just the last digit, and we can record that using the notation of modular arithmetic.  Here are four equivalent statements:

• 3248 leaves remainder 8 when divided by 10;
• $3248 \equiv 8$ (mod 10);
• 3248 and 8 leave the same remainder when divided by 10; and
• 10 divides 3248 – 8.

They are all useful ways of thinking about the same idea.

We moved on to see how addition works: we saw that $3248 + 73 \equiv 8 + 3 \equiv 11 \equiv 1$ (mod 10).  We can simply focus on the last digits, because that’s all that’s important in the mod 10 world.

Then we drew up multiplication tables in the mod 5 world, the mod 3 world and the mod 7 world, and looked for interesting patterns that we might be able to explain.  Here’s the grid for the mod 5 version; the completed tables are over the break (but I encourage you to draw them up for yourself!).  I’ve filled in the diagonal, so that you can check you’ve got the right idea.

x (mod 5) 0 1 2 3 4
0 0
1 1
2 4
3 4
4 1

### Theorem 28: there are infinitely many Carmichael numbers

June 3, 2010

This week’s theorem follows from my previous posts on Fermat’s little theorem and (to a lesser extent) Wilson’s theorem.

We saw that Fermat’s little theorem tells us that if $p$ is prime and $a$ is not divisible by $p$ then $a^{p-1} \equiv 1 \mod{p}$.  Could we use this as a test for primality?  Wilson’s theorem gave us a criterion for a number to be prime ( $n$ is prime if and only if $(n-1)! \equiv -1 \mod{n}$), although it doesn’t give us a practical way to test whether a number is prime.  Could we get something similar from Fermat’s little theorem?

Well, how might this work?  Let’s stick to odd values of $n$ (since it’s pretty easy to check whether an even number is prime!).  We might hope that if there’s a number $b$ (not 1) so that $b^{n-1}\equiv 1 \mod{n}$ then $n$ must be prime.  If there is such a number $b$, we say that $n$ is a pseudoprime to the base $b$.  But does the existence of a base to which $n$ is a pseudoprime mean that $n$ must be prime?

No.  Simple example: $4^{14} \equiv (4^2)^7 \equiv 1 \mod{15}$, so 15 is a pseudoprime to the base 4 (but certainly isn’t prime).

OK, so that didn’t work.  But if $p$ is prime then we know that $a^{p-1} \equiv 1 \mod{p}$ for all numbers $a$ coprime to $p$.  Suppose we know that $n$ is a pseudoprime to all bases $b$ with $b$ coprime to $n$.  Does that mean that $n$ is prime?

### Theorem 27: Wilson’s theorem

May 28, 2010

Quite a quick theorem this week, I think.

In the first proof I gave of Fermat’s little theorem, I suggested multiplying together the p-1 numbers a, 2a, …, (p-1)a (where a is coprime to the prime p), to get $(p-1)! a^{p-1}$.  (As usual, I’m writing (p-1)! for p-1 factorial.)  But, as we saw, those p-1 numbers are congruent to 1, 2, …, p-1 (mod p) (in some order), so this product is congruent to (p-1)!.  That is, $(p-1)! a^{p-1} \equiv (p-1)! \mod{p}$.  Then we said that (p-1)! is coprime to p, so we can cancel it to get $a^{p-1} \equiv 1 \mod{p}$, which is Fermat’s little theorem.  But could we have said any more about the quantity (p-1)! (more than that it is coprime to p)?

Let’s try some examples. $(2-1)! = 1 \equiv 1 \mod{2}$ $(3-1)! = 2 \equiv 2 \mod{3}$ $(5-1)! = 24 \equiv 4 \mod{5}$ $(7-1)! = 720 \equiv 6 \mod{7}$

Notice anything interesting?

### Theorem 24: the Chinese remainder theorem

April 18, 2010

I’ve been meaning to write this for ages, since it’s a subject that I discussed with my students a while back and I think it’s a really lovely result.

Here’s a game you can play with a friend.  Ask your friend to think of a number (whole number!) between 1 and 100.  Ask them to divide the number by 11 and tell you the remainder.  (So you’re expecting a number between 0 and 10.)  Then ask your friend to divide the original number by 13, and again tell you the remainder.  Your job is to tell your friend which number they thought of, using just those two pieces of information.  You might like to think about whether you can do that, perhaps by trying some examples.

### Theorem 21: the real numbers are uncountable

March 18, 2010

In my post about the countability of the rational numbers, I said that I’d come back to the topic and prove that the real numbers are uncountable.  That’s the plan for today.  If you’re not familiar with the definition of countability, please read that post first: this really is part two of that post.  I may as well state the theorem immediately, and then we’ll think about what it actually means.

Theorem The real numbers are uncountable.

What does this mean?  It means there’s no way of listing the real numbers (we saw last time that saying that a set is countable is the same as saying that the elements can be written in a list).  So our aim is to prove that it’s impossible to do something (write the real numbers in a list).  How could we possibly do that?

### Theorem 19: there is a transcendental number

March 3, 2010

I went to a very nice talk by a colleague the other day.  I can’t tell you about an hour’s worth of talk in one blog post, but I can tell you about a few of the highlights.

I’ve previously written about the fact that the square root of 2 is irrational.  That is, it can’t be written as the ratio of two whole numbers (as a fraction, if you like).  In some ways, that makes it seem like an unpleasant number: it’s not as `clean’ as something like 1/3 or 17/15.  But it’s not totally disgusting!  We can get some control on it, because we know that it satisfies the equation $x^2 = 2$, or, putting that another way, $x^2 - 2 = 0$.  That’s quite a nice equation, actually.  (Not quite as simple as $3x - 1 = 0$ or $15 x - 17 = 0$, perhaps, but still pretty nice.)  It’s a polynomial equation (it involves powers of $x$), and the coefficients (the numbers in front of the powers of $x$) are integers.  We say that it is an algebraic number: it satisfies a polynomial equation with integer coefficients.  (We could replace “integer coefficients” by “rational coefficients” here without changing anything — you might like to convince yourself of this.)

We could think about some other numbers and ask whether they’re algebraic too.  Is $\sqrt{15}$ algebraic?  Yes, because it satisfies the equation $x^3 - 15 = 0$, and that is a polynomial equation with integer coefficients.  Is the golden ratio, $\frac{1+\sqrt{5}}{2}$, algebraic?  I’ll let you find a polynomial equation that it satisfies.  Is $\pi$ algebraic?  Is $e$ (the base of the natural logarithm) algebraic?  Are there any numbers that aren’t algebraic?

### Theorem 18: the rational numbers are countable

February 24, 2010

One of the intriguing facts about infinity mentioned in that Horizon programme (the one on recently that I disliked) is that there are different sizes of infinity.  I thought that this week I’d start discussing that fact.  (There might be another theorem of the week on this subject!)  Here are two questions for you to consider.  Are there the same number of integers (whole numbers) as natural numbers (positive whole numbers)?  And are there the same number of rational numbers (fractions) as natural numbers?

The idea is that there can be infinite sets that don’t have the same size.  To make sense of that statement, we have to know what it means to say that two sets have the same size (and what an infinite set is).  Let’s try to make sense of this.

I think this really goes back to our earliest ideas of what it means to count the elements of a set.  When I look out of my window to a field of sheep, I count the sheep by matching each sheep to a number: 1, 2, 3, 4, ….  And if I count the books in the bookcase, I do the same thing: I match each book to a number: 1, 2, 3, 4, …. I’d say there are 10 sheep (or books) if I can match each sheep (book) to a number from 1 to 10 in such a way that each number gets used, and no two sheep get the same number.  We say that the set of sheep in this field has the same size as the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, because we can match sheep to numbers.  (We could imagine painting numbers on sheep.  Not sure my artistic skills are up to that.)

### Theorem 16: the inclusion-exclusion principle

February 3, 2010

I’m supervising first-year undergraduates for Probability this term, and found myself discussing the Inclusion-Exclusion Principle with some of them earlier.  It’s a very nice idea.

I grew up in a house with three cats.  At meal times, each had his or her own bowl.  But being cats, they never wanted to eat from their own bowls: the bowl next door always looked nicer (despite the food having come from the same tin).  In how many ways could they all eat from the wrong bowl? (With apologies to the cats, who were all very beautiful tabbies, and not those colours at all.  My skills at drawing pictures on my computer are limited!)