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.
Continue reading “Number Theory in Math Olympiad – Beginner’s Toolbox”
In math olympiads around the world, number theory problems have many recurring themes. One such theme is the ‘LTE’ or lifting the exponent.
Continue reading “Lifting the exponent and math olympiad number theory”
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.
Suppose f be a continuous function from X to Y (where X and Y are domain and range). If Y is a closed set (closed interval if we working in \(R^1 \) ) then can we say that the domain is also closed?
There is a simple counter example. Suppose X = \(( -3pi,pi)\). Then Y (the range) is [-1, 1]. Surely the range is closed and domain is open. When can we say that if the range is closed, domain is also closed? Only when the function is one-one and onto.
Continuous functions generally give a good picture of the domain set if we know the nature of range set in some detail. For example inverse image of open sets in Y (range) is always open in X (domain). This is easy to prove from the definition of continuity. After all continuity means that for every \(epsilon \) neighborhood V of f(c) we get will get a \(delta \) neighborhood U of c (c being a point in domain) such that when we pick a x from U, f(x) will lie in V. Now let V be a open set containing f(c) (that is it is some neighborhood of f(c) and V is the subset of range set Y). Then \(f^{-1} (V) \) consists of all the points in X (domain set) that maps into V. Let \(x_1 in f^{-1} (V) \). Thus \(f(x_1) in V \). Since V is open we will get an \(epsilon\) neighborhood M of \(f(x_1) \) which is entirely inside M and such that there exists a \(delta \) neighborhood N of \(x_1 \) such that all points in N maps to M. In other word N is in \(f^{-1} (V) \). Thus \(f^{-1} (V) \) is open (we have found a open set N containing \(x_1 \) which is entire inside \(f^{-1} (V) \) ).
As we have seen, a continuous function does not necessarily map open sets to open sets (the sin function that we discussed earlier) but preimage of open sets are open. Preimage of closed sets are however not necessarily closed (we have the previous example again to our rescue). However if the continuous function is monotone (that is it is either increasing or decreasing) a lot more can be said about the domain set by looking at the range set and vice versa (you may put some of your observations in the comment section about monotone continuous functions).
(This is a series of discussions on Homothety. It is largely derived from the Math Olympiad Classroom Discussion in Cheenta – www.cheenta.com)
Homothety is a geometric transformation. It has a couple of synonyms: dilation and central similarity.
A geometric transformation is a function. It can be thought of as a machine which takes in a point as input and gives out a point as output.
In algebra or calculus we encounter simple functions in school. One example is \(f(x) = x^2 \) . The rule of processing in this function is “square the input”. That is if the input is 3, output will be 9. Geometric Transformations are similar things. It’s set of input (often termed as “domain of the function”) are however points instead of real numbers. Algebraically the points are doublets of numbers like (1,2) representing the coordinate of the point. Of course a point can also be represented by triplet of numbers (say (3, 5, -7) ) if we do geometry in three dimension (and similarly by a n-tuple \((a_1 , a_2 , … , a_n ) \) of numbers if we work in n-dimension) . Presently we shall confine our discussion in the plane or two dimension.
To define homothety we need to specify two things: center of homothety and ratio of homothety. Center of homothety is a point on the plane. It can be any point. When we treat homothety algebraically, this point is regarded as the origin (0, 0) of the coordinate axis (assuming we are working in cartesian coordinate system). Ratio of homothety can be any real number positive, negative or zero.
Suppose O is the center of homothety and r is the ratio of homothety. If a point A on the plane is the input we can find the output point A’ in the following manner: join OA, extend OA both sides and find a point A’ on this line such that \(frac{OA’}{OA} \) = r .
In other words, the segment OA is stretched (or contracted) r times and the direction of this stretching or contraction is decided by the sign of r. Suppose r = 2, then OA will be stretched two times in the direction OA. However if r = -2, A’ is on AO (on the other side of A about O) and length of OA’ is twice of OA.
In the next installment of this series of articles we will continue with the applications of homothety.
(This is a series of discussions on Homothety. It is largely derived from the Math Olympiad Classroom Discussion in Cheenta – www.cheenta.com)
The Problem
Suppose ABC is any triangle. D, E, F are points on BC, CA, AB respectively such that \((frac{BD}{DC} = frac{CE}{EA} = frac{AF}{FB})\). Prove that the centroids of triangles ABC and DEF coincide.
A little Complex Number
Let A, B, C be points on the Complex plane with complex coordinates a, b, c.
The origin of the plane is made to coincide with the centroid of triangle ABC (the complex coordinates of the vertices adjusted accordingly).
Hence the complex coordinate of the centroid G is 0.
\((G = frac{a+b+c}{3} = 0)\) implying a+b+c= 0.
Next we find the complex coordinates of D, E, F in terms of a, b, c and the given ratio \((frac{BD}{DC} = frac{CE}{EA} = frac{AF}{FB} = k)\) (say)
Using the section formula we find that
\((d = frac{ck+b}{k+1})\)
\((e = frac{ak+c}{k+1})\)
\((f = frac{bk+a}{k+1})\)
where d, e, f are the complex coordinates of D, E, F respectively.
Hence the centroid of triangle DEF is given by \((frac{d+e+f}{3} = frac{frac{ck+b}{k+1} + frac{ak+c}{k+1} + frac{bk+a}{k+1} } {3} = 0)\) using (a+b+c) = 0.
Thus the centroid of triangle ABC and DEF are same.
A little Projective Geometry
We project triangle ABC into a plane T such that the projection is an equilateral triangle.
(to be continued)
353 is a prime number. So is 7919 (in fact it is the 1000th prime). There are 25 primes between 1 and 100. From 1 to 1000 there are 168 of them.
It is difficult to check whether a number is prime or not. One simple method is to try and divide the number with smaller numbers. For example to find out whether 351 is a prime or not, you start checking by dividing the number by small numbers such as 2. Of course, it is an odd number so we immediately know that it is not divisible by 2. Next we try by 3 and it works! Indeed 117 times 3 is 351.
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.
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.
