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.

Sets: An Introduction to Sets

A set is a very simple idea on the face of it, it is merely a collection or group; that is all. Sets are not objects in the real world; they are created within our minds not by our hands. An example of a set is all even numbers or all of the children in Europe or even the set of green bumblebees. But that is obviously not the sort of set we are interested in, we are only interested in ones that have interesting mathematical properties.

Sets by themselves may seem pretty uninteresting but when used in other areas of mathematics they show how powerful they truly are. They are used as a foundation from which the majority of mathematics can be derived, that is why they're so fundamentally important to mathematicians! Sets have to be defined in such a way that creates some list of numbers.

By convention, sets are denoted by capital letters, elements (read more in the next paragraph) are labelled by lower case letters. Beyond this the notation for sets is basic: you list each element, separated by a comma, and surround this list by curly braces, {}. For example, some set, Q, contains elements {p, q, r}.

There are a range of ways in which a set may be defined, either the items are defined using a semantic description for example: all of the odd integers or all prime numbers divisible by 4. Or you can define a set by listing the elements individually, for example: {2, 4, 8, 16}, with this version an ellipsis may be used to show that the set continues indefinitely in the same manner {3, 9, 27, 81, ...} like so.

A set constitutes of elements, an element is one distinct item that makes up a set. For example 1 is an element of the set of integers, the notation for an element, x, belonging to a set R is: x ∈ R. x ∉ R means x is not an element of R.

A subset is a set that entirely lies within another set, for example all prime numbers are integers. A ⊆ B means every element of A is also an element of B and this is read as "A is a subset of B". An interesting point from this definition is that for any set, S, every element of S is clearly also in S thus S is a subset of S (S ⊆ S). This is a bit strange so we introduce something more thorough than subsets and that is proper subsets: A is a proper subset of B if every element in A is also in B and there is at least one element in B that is not in A; this has the slightly different notation of A ⊂ B.

The next two you may be more familiar with if you have done maths past GCSE level you may have encountered them, they are union and intersection. A union B is essentially A and B, the notation for this is A ∪ B, it is everything that is in A and B. A intersection B is where A and B overlap and the notation for this is A ∩ B.

The union of all of the natural numbers {1, 2, 3, ...} and all of the integers {-2, -1, 0, 1, 2, ...} will result in just the set of integers, the reason for this is that it does not matter if a set contains duplicate identical elements it is the same as long as the same elements are present, not how many. {1, 2, 3} is the same set as {1, 1, 2, 3, 2, 3} as the same elements are present in both. It then follows that A ∪ B = A + B - A ∩ B, which is a vitally important fact for combining sets.

You may also be interested in the size of infinite sets, which investigates that there are some infinities larger than others!

Why Does -1 × -1 = 1?

It may seem obvious that -1 × -1 = 1, but is it really as intuitive as it seems? In fact, really, it isn't nearly as obvious as it may appear and the proof can be nowhere near as rigorous as you would normally require one to be but it has to suffice because of how 'basic' the idea is.

The proof relies on the distributive law of arithmetic, which is that a(b + c) = ab + ac, this is so obvious to most of you that it may seem redundant even to state it but it is from this simple fact that the proof lies.

We will show that -1 × -1 = 1 by contradiction. We can obviously state that -1 × -1 = 1 or -1, then we assume that -1 × -1 = -1 is true. Consider -1(1 - 1) then by the distributive law we have that this equals to: -1 × 1 + -1 × -1 which from our assumption is -1 - 1 = -2. But this would then imply that -1 × 0 = -2 which is contradictory therefore -1 × -1 = 1 (which would make the equation we considered hold true, try it yourself).

This is a rather difficult proof to fully trust because we have made a pretty huge assumption, why must -1 × -1 = 1 or -1? Well, essentially, it doesn't have to but it just seems logical that it would be. As it is such a fundamental part of mathematics it is essentially defined by us in order for fundamental laws to continue to work. So if you find that the 'proof' I have given you is not enough then that's fine, it is true simply because it functions correctly..