Least Common Multiple
(Gandaan Sepunya TerKecil)
I can't really remember any interesting identities related to LCM, and some of the properties has already been included in the description of GCD.
This is the one thing you would lament nobody has taught you before, if you come out from OMK and somebody tells you the solution of the number theory question which is so easy, using modular arithmetic.
Before I start talking about modular arithmetic, some may complain that "What? The OMK problems require some theorems which are not in secondary school syllabus??? So unfair!!" (Note: Modular arithmetic is found in form 6 further maths syllabus, if im not mistaken) Well, this is not what really happens. The fact is, as you will see below, modular arithmetic is actually something you can figure out by yourself, and it is only a systematic representation of the knowledge. More importantly, I think number theory questions in OMK has so far avoided ones that must require modular arithmetic. Therefore, even if you know nothing about modular arithmetic, you will still be able to solve OMK number theory questions, you will only find it harder.
To begin with the usefulness of modular arithmetic, first try to prove this using your preexisting knowledge. I would recommend spending about 10 minutes on this, and try to appreciate the question's nature.
Originally Posted by One of the past OMK ques
If a and b are odd numbers (nombor ganjil), prove that a^2 + b^2 cannot be a square number.
Eerm, I will come back to that, now we will move on with modular arithmetic. It's quite hard to give a definition for arithmetic modular, but it will be clear using examples. We know when we divide 12 by 5, the remainder (baki) is 2; if we divide 22 by 5, the remainder is 2 as well. So, 12 and 22 share the property that "when divided by 5, remainder is 2". Now, modular arithmetic is a system to make us of this kind of properties (of remainders after division) in order to solve number theory questions.
In notation, the previous example would be expressed as:
12 ≡ 2 (mod 5)
22 ≡ 2 (mod 5)
We can also write like this:
12 ≡ 22 ≡ 2 (mod 5)
(note: mod is the short form of modulo)
In other words, when we are saying that a number is equal to (actual term is congruent to) another number in modulo 5, it just means that when those numbers are divided by 5, they will all end up with the same remainder. So, we have 3 ≡ 8 ≡ 13 ≡ 18 ≡ 23 ≡ 28 (mod 5).
Of course the usage of modulo is not constrained to modulo 5 alone, you can use it for any other natural numbers larger than 1. For example, odd numbers are all 1 (mod 2), even numbers are all 0 (mod 2).
Now, what's the use of all those mod thingy? The use is, we can perform some operation on them!
Firstly, it is important to note that when we know that x ≡ 3 (mod 5), it means that x must be a number which is a multiple of 5, with 3 added on top of it. In algebraic form, x = 5m + 3 where m is a integer.
Secondly, we can perform addition, subtraction and multiplication (but not division) using modular arithmetic. For example, say we have 12 ≡ 2 (mod 5), and 34 ≡ 4 (mod 5). So what is 46 (which is 12 + 34) mod 5? We can simply add up 2 and 4, and we will get 6 (mod 5). Next, what is 408 (which is 12 x 34) mod 5? We can simply multiply 2 and 4, and we will get 8 (mod 5), which is also equal to 3 (mod 5).
Now.... Let's observe some interesting phenomenon: In modulo 4, what can we say about all odd square numbers and all even square numbers? let's see, 1, 9, 25, 49, 81 etc... Tada! They are all 1 (mod 4)! What about 4, 16, 36, 64, 100 etc.. They are all 0 (mod 4)...
The reason of this is that, all odd number can be expressed as (2n + 1) and all even number (2n), where n is an integer. So the square of even number is 4n^2, which is obviously 0 (mod 4); while the square of odd number is 4n^2 + 4n + 1, which is obviously 1 (mod 4)
And so, we have a fast solution to the abovementioned problem! Now that odd square must be 1 (mod 4), and so a^2 + b^2 ≡ 2 (mod 4). And as we have shown above, a number which is 2 (mod 4) can't be a square.
I will try to find some number theory questions which can be solved using modular arithmetic, and you will be amazed by its power.
With regard to the question on the previous post, I would like to show that it's still possible to solve without the usage of modular arithmetic:
Let a = (2n + 1) and b = (2m + 1). where n and m are positive integers.
So a^2 + b^2
= 4 (m^2 + n^2) + 4 (m + n) + 2
= 4K + 2 (where K is a positive integer)
Now, an even square must be a square of an even number. So it must be (2L)^2 = 4L^2.
Therefore, we arrive at a contradiction, which means that it is impossible to satisfy the condition stated in the question.
Originally Posted by colis
Youngyew, i can understand neither of your Maths solutions. Is it university level or i'm too poor(I'm in lowel six)?
I will show a simple example of how modular arithmetic can be useful in a number theory proof.
If we want to see whether a natural number is divisible by 3, just add up its digits. If the sum of the digits is divisible by 3, then the number itself is also divisible by 3. Show why this is true.
I think this is one of the most well-known divisibility checking method out there. For example, if we want to know whether 711 is divisible by 3, just do the summation (7 + 1 + 1 = 9). Since 9 is divisible by 3, then 711 is also divisible by 3.
The proof is as follows:
First of all, notice that 10 (mod 3) = 1, 100 (mod 3) = 1, 1000 (mod 3) = 1 and so on and so forth. In short, 10^n = 1 (mod 3) where n is a non-negative integer.
So, now let represent our number by its digit. If our number is 711, it can be broken up to 700 + 10 + 1. So if our three-digit number is a_0a_1a_2, it can also be broken up as (100 a_0) + (10 a_1) + (a_2). In general form, if a natural number is a_0a_1a_2a_3....a_i, then it can be broken up to (10^i a_0) + (10^(i-1) a_1) + ... + (10^1 a_(i-1)) + (a_i).
Now, we have:
a_0a_1a_2a_3....a_i (our original number)
= (10^i a_0) + (10^(i-1) a_1) + ... + (10^1 a_(i-1)) + (a_i) (mod 3)
= a_0 + a_1 + a_2 + ... + a_i (mod 3)
The final step is true since multiplication and addition is legitimate for modular arithmetic.