Modular Arithmetic: Rule of 3

Did you know that if a number is divisible by 3 then the sum of its digits are also divisible by 3? Have you ever wondered why? The answer to this problem lies within the field of modular arithmetic.

To begin we need to very precisely decide what our question really is. We start by defining some integer, n, with digits a_ra_r-1...a₁a₀. This then means that: n = a₀ + 10a₁ + ... + 10^r-1a_r-1 + 10^ra_r.

In order to proceed with our proof we must first prove a simpler fact, that aⁿ - bⁿ is always divisible by a - b. We will use induction to prove this lemma.



What this lemma means is that if a ≡ b mod m that aⁿ ≡ bⁿ mod m, for any integer n, too. With this fact ready we can now proceed with our proof.

It is clear that 10 ≡ 1 mod 3 (10 - 1 can be perfectly divided by 3), utilising our lemma it is clear that 10^k ≡ 1 mod 3. If a ≡ b mod m and c ≡ d mod m then ac ≡ bd mod m (the multiplicative law) and that (a + c) ≡ (b + d) mod m (the additive law), read the proofs here.

0 is obviously divisible by 3, hence a_k - a_k (the k^kt n minus the same digit) is divisible by 3 too - this means that a_k ≡ a_k mod 3. Utilising the rules of modular arithmetic we have that 10^ka_k ≡ a_k mod 3. It then follows from the additive law that n ≡ (a_r + a_r-1 + ... + a₁ + a₀) mod 3.

Therefore if 3|n then (a_r + a_r-1 + ... + a₁ + a₀) ≡ 0 mod 3, or in English, the sum of the digits of a number that is divisible by 3 will also be divisible by 3. The rule of 3 is proven.

There are also similar laws for division by 9 and 11 but I will leave these proofs up to the reader of this post, you use the exact same techniques and facts as I have used here. Leave any comments on any problems (or successes!) you have with this.

Creating a Prime Checker

For this post I will be utilising Fermat's Little Theorem to check for primes from a certain number to another number, of course you can make it check just one number if you so wish. If you do not want to program it yourself you can feel free to just download my .exe prime checker, download my source code or you may want to download my list of the first 7,000,000 prime numbers created with this prime checker.

I will be using Python to create this for a few reasons but the most important of these is that Python is very useful in the sense that it does not cap the size of a number you wish to store - which is vitally important for this program as the numbers will get very, very large. Before I start you may want to read some of my posts on basic programming in Python:

Introduction to Python

Python: Mathematical Terminology

Python: Interaction and Variables

Fermat's little theorem is that a^p-1/p always has a remainder of 1 for a prime p that is co-prime to a. And utilising this fact is how we check for a number being prime or not. One problem with Fermat's little theorem is that it can also occasionally work for when p is not actually prime (this is called a Poulet number), these are rare but to minimise the probability that the number isn't actually prime is to check the number with a different value of a multiple times.

Before we begin we need to be able to check what the highest common factor of two numbers actually is (in this case it will be a and p). To do this we will use the Euclidean algorithm, if you read that post it will tell you how to create that function and also what each part means. For the purposes of this program I will simply give you the code needed.

def gcd(a,b):
        while b != 0:
                a, b = b, a%b
        return a

Now we get down to the good bit and properly begin programming the prime checker!

def primecheck(num):
         count = 0
         a = 2
         prime = True

We begin by creating a new user-defined function called 'primecheck', it will require one variable, which we will call 'num'. Python uses indentation to distinguish between different code segments and functions, so everything contained within the function will be indented. Three local variables will be required for the function, one to be used as a counter for when repeating Fermat's prime check to reduce the chance that the number is a Poulet number, one to be used as the 'a' in Fermat's little theorem and one to return whether the number is prime or not.

if (num - 1)/6 == int((num-1)/6) and (num - 5)/6 == int(num - 5)/6):
       {Fermat's prime check}
else:
        prime = False
return prime 

Now that we have the local variables for the function we can begin writing the code needed to check if a number is prime or not. The algorithm itself takes a fairly long time, so we want to begin by trying to get rid of numbers that are obviously not prime without needing to do very much to the number. All prime numbers (other than 2 and 3) can be written in the form 6n + 1 or 6n + 5 (why?), so we can check that our number satisfies this before we proceed with the more processor heavy check.

If the number cannot be expressed in the form 6n + 1 with n as an integer then the check is stopped there and the number is returned as not being prime, if it does meet that criteria then the Fermat primality check is performed. After the prime check is performed the outcome is returned (whether prime is True or False).

while (count < 10):
         count = count + 1
        while gcd(a, num) != 1:                a = a + 1        if pow(a, num - 1, num) != 1:                count = 10                prime = False        a = a + 1

The check is performed 10 times with a different value of a to ensure that the number is not a Poulet prime, that is why there is a loop while count is less than 10. The loop starts by making a note that the check has been performed by increasing count by 1, a check is then performed to ensure that a and num are coprime, if they are not a is changed and the check is reperformed. Once a and num are coprime we utilise the pow function, pow(a,b,c) returns the remainder of a^b/c; so in this code we are utilising this function to utilise Fermat's little theorem to check that num is prime by finding the remainder of a^{num - 1}/num and if this is not 1 then the test has failed and num is immediately returned as false. If all the checks come back with no problems then num is returned as prime.

This is it for the coding of the actual prime checker, the rest of the programming is to give the program structure, variables and how to save the outcome of each check.

num = input("First prime to check ")
lastnum = input("Last prime to check ")
while num <= lastnum:
        prime = primecheck(num)
        if prime == True:
                FILE = open("primes.txt", "a")
                FILE.write(str(num))
                FILE.write(", ")
                FILE.close()
                print num," is prime."
        else:
                print num, " is not prime."
        num = num + 2

To begin two variables are created for the first prime number to check and the last prime number to check in order to give the program an end point. While the number to be checked is less than the last number a check will be performed. A boolean variable prime is assigned to the output of the primecheck when performed on num. If prime is true then a text document called primes is opened to append and the number is added to it, read more on editing files from within Python. A message is displayed to the user to state whether the number is or is not prime. 2 is added to the previous number to ensure that the next number is odd, this relies on the fact that the first number entered was also odd, if it was not then you would be checking whether or not only even numbers are prime which obviously they will not be (except 2).

And that is it for the whole program! Hopefully yours is now working correctly, if you have any problems please leave a comment and I will help you as soon as I can. If you haven't already you may wish to download my .exe prime checker, download my source code or you may want to download my list of the first 7,000,000 prime numbers created with this prime checker.

Highest Common Factor: Proving Euclid's Algorithm

The Euclidean algorithm will find the highest common factor of two numbers (the largest number that will divide both numbers). It is a rather simple algorithm to understand and implement having been discovered by the great mathematician Euclid of Alexandria 300 BC making it one of the oldest algorithms still applicable and in use in modern times.

Overview of Euclidean Algorithm

1.) Begin by inputting two numbers m and n
2.) If m < n then swap m and n (the larger number should be set to m)
3.) Divide m by n then get the remainder from this, r. If r = 0 then return n as the highest common factor and stop the algorithm.
4.) Let m = n and n = r. Repeat step 3.

The obvious questions here are "why does this work?" and "how do you know that the answer is always correct?". The best way to answer these questions is through an example.

Example: Find the highest common factor of 216 and 38.
From the algorithm we must set m = 216 and n = 38, m/n gives a remainder of 26. We now set m = 38 and n = 26, m/n gives a remainder of 12. Set m = 26 and n = 12, m/n gives a remainder of 2. Set m = 12 and n = 2, m/n gives a remainder of 0 so the highest common factor of 216 and 38 is 2.

It is clear from this algorithm that the important element from one step to the next relies on the fact that hcf(m,n) = hcf(n,r) is true. We will write this as a lemma.

This is how the algorithm works but it is not a proof as to that it will always work on any two integers, m and n. To prove this we will utilise how the algorithm in a more formal sense and then utilise those facts to prove the algorithm is consistent and thus correct.

And that is how and why the Euclidean algorithm works! It is relatively simple to program this algorithm and because of this and that it is very efficient it has many uses in mathematical programs, most importantly (to me!) is for prime checkers.

Fermat's Little Theorem

Before reading through this post it is useful if you have some knowledge of modular arithmetic.

Fermat's little theorem (it's 'little' because of Fermat's comparatively more difficult to prove last theorem, not because it is less useful, in fact it is more useful) is a vital result from the field of number theory as it provides a method of checking (within reason) whether a number is prime or not. Also it is a very interesting result that utilises modular arithmetic.

Fermat's little theorem is that given a prime number, p, and any integer, a, a^p - a will divide by p to give an integer value. Or, more mathematically, p|a^p - a. So from the definitions in modular arithmetic this means that a^p ≡ a (mod p); it can also be wrote as a^p-1 ≡ 1 (mod p) - both are equally valid but the second is used more often mainly because it has a 1 on the right hand side and this is 'neater' and mathematicians love things to be neat!

There is a condition for the integer a and that is that it is coprime to p. Coprime means that the highest common factor between two numbers is 1; so for example 3 and 46 are coprime as the only factor they have in common is 1. The reason for why a must be coprime to p will come later.

When Pierre de Fermat first stated this theorem in a letter to his friend (in 1640) he did not include a proof of why this is the case as it was "too long". To attempt to 'one up' one of the greatest mathematicians in the past 400 years I will include a proof of this fact.

There are three points of contention within this proof that I feel I should justify/explain further. (A) is that these numbers are chosen intelligently in order to prove Fermat's little theorem, this was not the original proof of the theorem as it is difficult to be able to choose these numbers initially but in hindsight it is clear that these work very well.

(B) requires further explanation. The reason that when a, 2a, 3a,..., (p - 1)a are divided by p will give remainders 1, 2, 3,..., (p - 1) in some order is because of Euclid's lemma, if a prime number divides the product of two numbers then the prime number must divide at least one of the factors. Clearly none of the numbers in list A can be divided by p (a is coprime to p), so some integer in the range of list B, n, is coprime to p too - this means that na can not be divided by p so this means that a, 2a, 3a,..., (p - 1)a when divided by p must have remainders in the region of 1, 2, 3,..., (p - 1). Read more on this.

For (C) why can we cancel out (p - 1)! in modular arithmetic? It isn't an equals sign after all. If we consider ax ≡ ay (mod n), this means that ax - ay can be divided by n, factorising this we get a(x - y) can be divided by n implying that either a can be divided by n or x - y can be. In our case a is (p - 1)!, x is a^{p - 1} and y is 1; but (p - 1)! is clearly coprime to p so that means that a^{p - 1} - 1 can be divided by p so we can in fact cancel the (p - 1)!s.

And that is Fermat's little theorem fully proved! You will have almost certainly encountered Fermat's little theorem whether you knew it or not, almost all online security and encryption utilises prime numbers to stop data being intercepted and Fermat's little theorem is used to check the primality of numbers to be used.

If you do not understand anything in this post, feel I have made a mistake or need extra explanation on anything covered here leave a comment and I will get back to you as soon as I can.