Modular arithmetic, number theory and encryption

Here is a message I just sent to my first-year students at Nottingham ….


Hi everyone,

You have now seen a bit of modular arithmetic, which you can also think of as introductory number theory. Prime numbers and modular arithmetic are the key to the “public key” encryption systems used on the internet whenever you visit a secure website (https). You can learn more about all this in later modules.

Today’s classes included some tricky concepts. Many of you will still be wondering about “squares modulo 7”.

Perhaps modulo 10 is a bit easier to think about here? Remember that, for non-negative integers, working modulo 10 is like ignoring everything except the last digit, so all non-negative integers end up being treated as being between 0 and 9, and you have multiplication tables including 9×6=4, 2×5=0, 8×7=6, etc. (mod 10).

So what are “squares modulo 10”? Well, what are the possible last digits of squares of integers?

First note that squares of negative numbers are just the same as squares of positive integers, so there is no need to check those.

Checking the last digits of the squares of 0, 1, 2, 3, … we see the pattern

0, 1, 4, 9,6,5,6,9,4,1,0,1, 4, 9,6,5,6,9,4,1,0,…

and this repeats forever. Note that 4^2 and 6^2 end in 6, 3^2 and 7^2 end in 9, etc. This is not a coincidence, because 6 is congruent to -4 modulo 10, so 6^2 is congruent to (-4)^2=4^2 (mod 10).

The repeating of the pattern with period 10 is also no surprise, because (n+10)^2 is congruent to n^2 (mod 10).

Conclusion: no matter which integer you square, the final digit of the square will be one of 0, 1, 4, 5, 6 or 9. You can’t get anything else.

This is because we are using the decimal system. If you use octal (base 8) instead, the same thing happens when you work modulo 8: for non-negative integers, just look at the last base 8 digit. Modulo 8 you get 3×3=1, 2×4=0, etc.

I hope this helps a bit!

Best wishes,

Dr Feinstein

Banach Algebras 2015

I’m currently at the 23rd international conference on Banach Algebras. This year we are at the Fields Institute in Toronto.

They are recording videos of all of our talks: see

My talk isn’t there yet (at the time of writing), but the talk of Sam Morley (one of my PhD students) is ready.

There have been lots of excellent talks, as you would expect from the list of speakers.

Now I just have to dodge the thunderstorms this evening …

(OT) Nottingham Symphony Orchestra concert, July 11 2015

My wife Uta and I met at the Nottingham Symphony Orchestra (we both play violin). I’m not playing with them at the moment (“I’ll be back!”), but Uta is.

Their next concert is coming up this Saturday 11 July 2015, Albert Hall, Nottingham, 7:30 pm.

Overture Euryanthe
Forest Murmurs
Violin Concerto in D major
Symphony No.1 in C minor
Soloist: Martyn Jackson

It should be great!

Follow the link to the Nottingham Symphony Orchestra web page for more details.

It’s maths, but not as you know it!

At the end of my module G11FPM Foundations of Pure Mathematics this year, one of the anonymous comments I received (on Student Evaluation of Modules) was that there appeared to be almost no maths in the module, only logic.

Of course this was only one comment from a class of over 200 students, but it left me wondering if I could do (even) more at the start of the module to warn them that much of pure mathematics at university is very different in nature to almost anything they will have seen at A level. Of course that is what my first lecture is intended to do, along with my class on “About this module”. But could I do more?

Today I gave my 30-minute “Taster Lecture” on Pure Mathematics as part of our Open Days for prospective applicants. I started the lecture by saying “Pure Maths at University is really very different from anything you will have seen at  A level, because (etc.) … and some of you may not even recognise this as mathematics! But it really, really is …” (or words to that effect).

One of my colleagues tells me that one of the visitors was complaining after the lecture, saying something like “I was expecting a sample maths lecture, but that was really just logic!”

Back to the drawing board ….

Tomorrow I will start the talk by telling them “It’s maths, but not as you know it!”

Learning to use MediaSpace

Aargh! I thought I would use the MediaSpace editing tools to delete the confusing blank few seconds at the start of my recent Cardiff talk, but instead I deleted the rest of the talk from MediaSpace, leaving just a blank 7-second video. (I never did like reading instructions …)

Oh well, I have the original mp4 file, so I’ll just have to upload it again and have another go!

Traditional expression in mathematical proofs

The following comment was recently posted on one of my YouTube videos (a session I ran a few years back on “How do we do proofs?” , available at


“Why do people who write proofs use confusing language like ‘let’, ‘consider’ (instead of ‘if’, ‘look’) etc.? Why do they write their proofs backwards, like they found it from thin air?”

My reply (with a couple of typos corrected!) was:

I think we might disagree about the meanings of “backwards” and “forwards”. Mathematical reasoning often has a specific direction, and not all steps in the proof are reversible. Proofs are often discovered working backwards from the destination (almost like some mazes are easier to solve that way), but the logic of the final argument must point in the correct direction. If you try to prove something by making deductions from the desired conclusion, you won’t have proved that conclusion unless all of your reasoning is reversible. (You can see some sample warnings about “backwards reasoning” in my Foundations of Pure Mathematics classes.) However, it is allowed to say “Y would follow if we could only prove X.” and then prove X, as long as you don’t use Y to prove X. So you can rewrite most proofs to fit more closely with the way they are discovered.

On the other hand, sometimes, perhaps like in a game of chess, there are only a limited number of sensible options for what information or tool you might use next. Here experience and fluency play a role: a strong chess player will usually focus quickly on a relatively small number of likely moves from what could appear to be a bewildering number of options.

Correct use of “let” or “suppose” is a very important (and traditional) tool when you want to prove that something is true for ALL examples of a particular kind. You can think of it as an abbreviation for the following ideas. “We want to show that [an interesting fact] is true for ALL things of type A. So what we need to show is that, if we have something of type A then [an interesting fact] is true for that thing. As long as we only assume the thing is of type A, and nothing else, then our proof will be valid for all things of type A. So, let x be an arbitrary thing of type A. We’ll show that just using the assumption that x is of type A, and no extra assumptions, we can still show that [an interesting fact]  is true for x. Because we made no other assumptions about x, our argument will show that [an interesting fact] is true for all things of type A.”

That is the traditional approach. But you could do a lot with “If”, as in “If x is a thing of type A, then …”. But, at least to me, the important thing is to make sure that you really understand the structure of the proof you need. Using traditional language can help when you are using a traditional proof structure, but is not essential as long as the reasoning is correct.

Lecture Capture in Mathematics: talk available on iTunes, YouTube and MediaSpace

This talk given in Cardiff in April 2015 is now available on iTunes and on YouTube. The YouTube edition is available at
The version on the University of Nottingham’s WirkswirthII server is moving, as support for that server will stop in the near future. We are going to move my media over to MediaSpace. The Cardiff talk is already available there at
[Note original link given was wrong]