This article is aimed at entry level Math Olympiad (AMC and AIME in U.S. , SMO Junior in Singapore, RMO in India). We have complied some of the most useful results and tricks in elementary number theory that helps in problem solving at this level. Note that only with a lot of practice and conceptual discussions, you may make practical use of these ideas.
Author: Ashani Dasgupta
-
Lifting the exponent and math olympiad number theory
In math olympiads around the world, number theory problems have many recurring themes. One such theme is the ‘LTE’ or lifting the exponent.
-
Arithmetic of Remainders
Consider the two number: 37 and 52
What is the remainder when we divide 37 by 7? 2 of course. And 52 produces remainder 3 when divided by 7. Suppose we want to know the remainder when the product of 37 and 52 is divided by 7.
-
The Dreams of Pythagoras
Pythagoras is famous. Even those who do not like mathematics, have heard of Pythagoras’ Theorem (regarding right angled triangles). He lived about 2500 years ago and did about 2500 wonderful things (well may be a little less) but all that is not the subject matter of this note. We want to talk about the shattered dreams of this famous mathematician and how the pieces of those fragmented dreams created modern mathematics. Pythagoras
Pythagoras believed numbers are omnipotent. The world that we see, the sound that we hear and even the thoughts and emotions that stir our mind are nothing but different numerical expressions of varying complexity. He even produced a theory that ‘numerified’ the world of music.
Every number, for Pythagoras, originates from 1. 1 was the all powerful number for him. You want to make a 10? Put ten 1’s together and you have it. You want to make 3.2? First put three 1’s together; that makes a 3. Then break another ‘one’ into ten equal pieces (each is then of the value 1/10 or 0.1) Put two of those pieces together with the 3 that you made earlier and behold … you have 3.2.
In this way, claimed Pythagoras, you can make ANY number under heaven.
How can you make 1/3 = 0.3333333333 (and it goes on)? That is easy! Break the piece of ‘1’ into three equal pieces and take one of them. In this way you can make 3.24, 1000, 35.123, 0.6666666 (2/3 – put the length of two 1’s side by side, break the length into three equal parts, and you have it!)
The underlying idea of Pythagoras was this: any number is a ratio of two whole numbers (whole numbers being some multiple of 1). Such was the happy world of Pythagoras where every number was invariably extractable from 1.
Then came the NEMESIS… A right angled triangle whose two sides are of one unit length and the third side….. well Pythagoras started to measure it:
He put a ‘1’ unit length on the third side of the triangle. But the side was not fully covered. ‘it is greater than 1 unit’ he thought, ‘but two sticks of 1 unit length would be a little too longer’. So he broke another ‘1’ unit long stick into into 10 equal pieces and found, to his dismay, that four pieces would be a little too short and 5 would be a little to long than the remaining portion.
The third side is then a little greater than
1+ 4* (1/10) (=1.4)Pythagoras again took a piece of 1/10 unit length and broke it into 10 parts. Each part is now of 1/100 length. If one of those ten small sticks are added to the remaining part of the third side, a little section still remains uncovered. However if he put two of the small sticks, it would again be a little too longer.
So the third side of the triangle is a little greater than
1+ 4*(1/10) + 1*(1/100) (=1.41)
In this way he tried for some time but it was always either a little more or a little less than the length of the third side. When this practical experiment failed, he tried a mathematical trick. He assumed the third side to be m/n (where m and n are positive integers). After all possible cancellations of common factors amongst numerator and denominator let the final ratio be a/b.
Now the famous Pythagoras’ theorem says that the square of the third side is equal to the sum of the squares of other two sides. As the ‘other two sides’ of our satanic triangle are each one unit long, sum of their squares is 2 (square of 1 is 1 and add to that another square of 1 which is also 1). Hence the square of (a/b) must be 2. Hence after cross multiplication we have
a^2 = 2*b^2
Thus a^2 must be even (since 2*b^2 is a multiple of 2 hence it is even).
Then ‘a’ must be even. (If a is odd, a*a = a^2 would be odd since odd times odd is odd)
Since ‘a’ is even, a = 2*t (since 2 is factor of a)
Hence a^2 = (2*t)^2 = 4*(t^2)
Thus 4*(t^2) = 2*(b^2) or b^2 = 2*(t^2)
But then b^2 is even and hence b is even.
But this makes both a and b even which is outrageous because initially we had no common factors amongst a and b (realize that all common factors of m and n are cancelled out to make a/b).
Pythagoras was doubly puzzled. He could not accept the fact that there is no ratio whose square is 2. He could not accept this because then his theory of number would become incomplete and hence no more omnipotent. His belief, his dream about the ‘numerified’ world would be shattered. When one of his students suggested that such a ratio (whose square is 2) does not exist, he became so angry that he drowned him in the ocean.
However ideas can never be drowned. In modern mathematics, we know that a ratio whose square is 2, does not exist. In fact the number whose square is 2, can never be ‘exactly’ determined in terms of decimal expression. It is approximately 1.41421356237309504880168872420969807856967187537694807317667973799… (up till 65 digits). But it is a never ending decimal.
-
Chinese Remainder Theorem
I want to discuss the ‘ideai behind the famous Chinese Remainder Theorem. Let us leave the jargon and start our exploration by a problem.
Find a number that leaves remainder 1, when divided by 5, 7 and 13.Clearly such a number can be found by trial. A stupid method is to check out all the numbers (at least some them) which leaves 1 as remainder when divided by 5 (we choose 5 because it is the smallest).
6, 11, 16, 21, 26, 31, 36, 41,…
The above sequence of numbers leave 1 as a remainder when divided by 5. Now the second condition is that, our required number must generate 1 as a remainder when divided by 7. Clearly that number is one of the numbers of the above sequence. We check out the remainders when divided by 7.
Number Remainder when divided by 7 6 6 11 4 16 2 21 0 26 5 31 3 36 1 (WHOA!) So 36 is the first number that fulfills the second condition. It leaves remainder 1 when divided by 5 as well as 13. Note that 36 is the first number with such a character. 71, 106 etc. are other numbers with such characteristic.
Anyways, we move to the third condition now. The number must leave a remainder 1 when divided by 13. A little introspection will bring the idea of product + 1 to the forefront. Note that 36 = 5*7 + 1; 70=5*7(*2)+1; 106 = 5*7(*3)+1; i.e. each of the numbers which leaves remainder 1 when divided by 5 and 7, contains 5 and 7 (as prime factors) and 1 more (rightly so!).
Therefore our required number is 13*5*7*(any number from 1 toward infinity) +1. In short we write 455k + 1 where k is any natural number.
Now we move forward with the second problem.
Find all integers that leave a remainder of 3 when divided by 5, a remainder of 5 when divided by 7, and a remainder of 7 when divided by 11.A brain-breaker idea will be to check out all the numbers that produce a remainder 3 when divided by 5. The following is the least of such numbers.
3, 8, 13, 18, 23, 28, 33, 38,
Then we shoot the numbers of the above sequence by 7 and find that 33 is a number that produces remainder 5 when divided by 7 (33=4*7 + 5). Can we guess a second number that produces remainder 5 when divided by 7? Clearly 68 is a second number with the same feature. Lets try 1 more (and while we do this lets us ask our brain the method it is using to compute the number). 103! Yes, we add 35 to the preceeding number (we still need to REASON why this works). But before that let us assure ourselves that 103 = 5*20 + 3 and 103 = 7*14 + 5. Also we need to be convinced that when we jumped 35 we did not miss any number with 3 and 5 as remainders when divided by 5 and 7 respectively.
Number Remainder when divided by 7 3 3 8 1 13 6 18 4 23 2 28 0 33 5 38 3 43 1 48 6 53 4 58 2 63 0 68 5 73 3 78 1 83 6 88 4 93 2 98 0 103 5 So we did not miss any one number.Hmm, that is good.And one more observation. The remainders are repeating (3164205 3164205 … so on). We will learn later that is a beautiful (and logical) consequence of the concept of divison.
So far so good. Our brain tells us: Find the first number with the character (remainder 3, 5, 7 when divided by 5, 7, 11) and add 5*7*11 to that to find all such numbers. The challenge is however to find that FIRST NUMBER.