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.

Introduction to Modular Arithmetic and Congruence

Modular arithmetic is an arithmetic system for the integers where the numbers wrap around, like on a clock for example. The numbers start at one, they go round to twelve and then start again at one, this would be an example of modulo 12. However generally in modular arithmetic we start at 0 and go to 11, before starting at 0 again. This means that 7 o'clock would be 6 mod 12 (mod is often used to shorten modulo). In fact because the number line "wraps around" it means that 19 o'clock = 7 o'clock (as you will know if you have used a 24 hour clock), this means that 18 mod 12 = 6 mod 12; because of this a mod m is wrote where a < m.

However it does not have to be just modulo 12, it can be modulo anything (as long at is a positive integer), so let us jump straight into the definition. So that you are aware of the notation I will use a|b means b divides a (this means that b/a is an integer). Let m be a positive integer and let a, b both be integers if m|a-b then a is congruent to b modulo m, wrote mathematically this is: a ≡ b mod m. Make sure you do not think "≡" means equivalent in this case, because it does not!

You can add in modular arithmetic (provided they have the same modulo). Let m be a positive integer and let a, b,c and d be integers if a ≡ b mod m and c ≡ d mod m then a + c ≡ (b+d) mod m. So basically you add the parts preceding the modulo together and then find modulo m of that.
You may also notice that a/m has a remainder of b, this is how we can quickly work out that 19 o'clock is the same as 7 o'clock, or the same as 103 o'clock. You simple divide the number by the modulo and work out the remainder.

An example of why we would use this using our clock as an example is if it is 4 o'clock now, what will the time be in 157 hours? So what we have is 3 mod 12 and 157 mod 12, adding these together we get 160 mod 12, 160/12 = 13 remainder 4. This means that 160 mod 12 = 4 mod 12, so it will be 5 o'clock 157 hours from 4 o'clock.

This should give you an idea of how to do basic addition with congruences, if you do not understand fully read what I have wrote again and then if you still do not understand, post a comment. Now we have the basic principles in place we can begin to go further. Now we will prove that a mod m + b mod m = (a+b) mod m and also how multiplication works in modular arithmetic.

Multiplication between two congruences is just as easy as addition with congruences, I will first provide a definition to you, before proving it. Let m be a positive integer and let a, b,c and d be integers if a ≡ b mod m and c ≡ d mod m then ac ≡ (bd) mod m; this is the same sort of principle as addition. Now to prove them.

First to prove addition:

Now to prove multiplication:

These are the very basics of congruences, but the are integral to modular arithmetic (I mean, think how important addition and multiplication is normally), they are very, very powerful and I will begin to explore them more and more in my upcoming posts. I will prove just one more result as it is pretty easy and uses multiplication.

The proposition is that aⁿ ≡ bⁿ mod m is also true provided  a ≡ b mod m and n is a positive integer. We will prove this by induction. Let P(n) be be the statement of the proposition, then P(1) is obviously true as we already know that a ≡ b mod m. So let us assume that P(n) is true, then we have that aⁿ ≡ bⁿ mod m and that a ≡ b mod m, multiplying the two of them together (using our proved method) we get a × aⁿ ≡ b × bⁿ mod m, this then simplifies to: aⁿ⁺¹ ≡ bⁿ⁺¹ mod m, which is P(n+1). Hence P(n) is true for all values of n!

I hope that you like this post and that is helps you. If you did like it then please also like us on Facebook.

Proof by Induction: Sum of Odd Numbers

I will introduce an integral part of mathematics in this blog post, proof by induction. It is fundamental to many proofs and is a pretty simple concept to grasp, I will demonstrate how this proof works with a simple example.

The first basis of proving by induction requires some intelligent intuition to our problem. This means that we look at the pattern of what is happening and try to prove this for all values. For the sum of square numbers this goes:

1 = 1
1+3 = 4
1+3+5 = 9
1+3+5+7 = 16

You may have noticed from this that the sum the answers is always a square number. The sum of the first n odd numbers appears to always equal n², but it just appears that way for the examples that we have given, we do not know that is true for all values, yet.

So our assumption is the sum of the first n odd numbers equals to n²:
1+3+5+...+(2n-1) = n<sup>2

This is our assumption, but if we can prove that n+1 odd numbers equals to (n+1)2 then that means it will hold true for the sums of any number of odd numbers. To begin to check this we add n+1th odd number onto both sides of our assumption.</sup>

1+3+5+...+(2n-1)+(2n+1) = n²+2n+1

As you can see the right side does factorise to give:

1+3+5+...+(2n-1)+(2n+1) = (n+1)²

Which means that our original assumption was correct! Ergo the sum of the first n odd numbers does equal to n² formally in mathematical notation this is:

And that is it for an example of how you use the proof by induction, now it just needs to be put in terms that are applicable for all problems.

Principle of Mathematical Induction
If for each positive integer n we have a statement P(n). If we prove the following two things then the statement is true:
a.) P(1) is true.
b.) For all n, if P(n) is true then P(n+1) is also true. This then means that P(n) is true for all positive integers n.

If that is pretty hard to compute look back to our example, our assumed statement is that P(n) = n² our assumption is true for P(1), 1 = 1² and we then proved that assuming P(n) is true that P(n+1) is also true. Therefore if P(1) is true, then P(2) is true too, etc.

Stay tuned for my future blog posts where I will utilise mathematical induction to find general formulas or proofs to many things.