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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s