Monthly Archives: September 2014

Reciprocal equation for IITJEE and RMO/INMO

In this set of little exercises, you will get a grip on reciprocal equations. 

reciprocal polynomial has the form

ax^{n}+bx^{n-1}+cx^{n-2}+...+cx^{2}+bx+a

in which a \neq 0 and the coefficients are symmetric about the middle one. A reciprocal equation is of the form p(t)=0 with p(t) a reciprocal polynomial.

1(a) Verify that each of the following polynomials is a reciprocal polynomial:

x^{3}+4x^{2}+4x+1

3x^{6}-7x^{5}+5x^{4}+2x^{3}+5x^{2}-7x+3

1(b) Show that 0 is not a zero of any reciprocal polynomial.

1(c) Show that -1 is a zero of any reciprocal polynomial of odd degree, and deduce that any reciprocal polynomial of odd degree can be written in the form (x+1)q(x), with q(x) a reciprocal polynomial of even degree.

1(d) Show that, if r is a root of a reciprocal equation, then so also is 1/r.

2(a) Let ax^{2k}+bx^{2k-1}+...+rx^{k}+...+bx+a be a reciprocal equation of even degree 2k. Show that this equation can be rewritten as

a(x^{k}+x^{-k})+b(x^{k-1}+x^{-k+1})+...+r=0

2(b) Let t=x+x^{-1}. Verify that x^{2}+x^{-2}=t^{2}-2 and that x^{3}+x^{-3}=t^{3}-3t. Prove that, in general, x^{m}+x^{-m} is a polynomial of degree m in t.

2(c) Use the substitution in 2b to show that the reciprocal equation in 2a can be rewritten as an equation of degree k in the variable t. Deduce that the solution of a reciprocal equation of degree 2k can in general be reduced to solving one polynomial equation of degree k as well as at most k quadratic equations.

3(a) Show that a product of reciprocal polynomials is a reciprocal polynomial.

3(b) Show that, if f, g,  h are polynomials with f=gh and f and h are both reciprocal polynomials, then g is also a reciprocal polynomial.

Please do post your comments, solutions…you can take a snapshot in your smartphone, and just post it 🙂

More later…

Nalin Pithwa

 

Pythagorean Triples and the Unit Circle — for RMO

In the previous blog, we described all solutions to a^{2}+b^{2}=c^{2} in whole numbers a, b and c. If we divide this equation by c^{2}. we obtain

(a/c)^{2}+(b/c)^{2}=1

So, the pair of natural numbers (a/c,b/c) is a solution to the equation

x^{2}+y^{2}=1.

Everyone knows what the equation x^{2}+y^{2}=1 looks like: It is a circle C of radius 1 with centre at (0,0). We are going to use the geometry of the circle C to find all the points on C whose xy-coordinates are rational numbers. Notice that the circle has four obvious points with rational coordinates, (\pm 1, 0) and (0,\pm 1. Suppose that we take any rational number m and look at the line L going through the point (-1,0) and having slope m, (Draw this line!) The line L is given by the equation
L: y=m(x+1) (point-slope  formula)

It is clear from the picture you have drawn that the intersection C \bigcap L consists of exactly two points, and one of those points is (-1,0). We want to find the other one:

To find the intersection of C and L, we need to solve the equations:

x^{2}+y^{2}=1 and y=m(x+1) for x and y. Substituting the second equation into the first and simplifying, we need to solve

x^{2}+(m(x+1))^{2}=1

x^{2}+m^{2}(x^{2}+2x+1)=1

(m^{2}+1)x^{2}+2m^{2}x+(m^{2}-1)=0

This is just a quadratic equation, so we could use the quadratic formula to solve for x. But, there is a much easier way to find the solution. We know that x=-1 must be a solution, since the point (-1,0) is on both C and L. This means that we can divide the polynomial by x+1 to find the other root:

So, on dividing (m^{2}+1)x^{2}+2m^{2}x+(m^{2}-1) by x+1, the quotient polynomial is (m^{2}+1)x+(m^{2}-1).

So the other root is the solution of the quotient polynomial

(m^{2}+1)x+(m^{2}-1)=0, which means that

x=(1-m^{2})/(1+m^{2}). Then, we substitute this value of x into the equation y=m(x+1) of the line L to find the y-coordinate:

y=m(x+1)=m( ((1-m^{2})/(1+m^{2})+1) ) =(2m)/(1+m^{2}) Thus, for every rational number m we get a solution in rational numbers

((1-m^{2})/(1+m^{2}),(2m)/(1+m^{2})) to the equation

x^{2}+y^{2}=1.

On the other hand, if we have a solution (x_{1},y_{1}) in rational numbers, then the slope of the line through (x_{1},y_{1}) and (-1,0) will be a rational number. So, by taking all possible values for m, the process we have described will yield every solution to x^{2}+y^{2}=1 (except for

(-1,0) which corresponds to the vertical line having slope m=\infty).

How is this formula for rational points on a circle related to our formula for Pythagorean triples (in the previous blog)?

If we write the rational number m as a fraction v/u, then our formula becomes (x,y)=((u^{2}-v^{2})/(u^{2}+v^{2}), (2uv)/(u^{2}+v^{2})) and clearing the denominators gives the Pythagorean triple

(a,b,c)=(u^{2}-v^{2},2uv,u^{2}+v^{2}).

This is another way of describing Pythagorean triples, although to describe only the primitive ones would require some restrictions on u and v. You can relate this description to  the formula in the earlier blog by setting

u=(s+t)/2 and v=(s-t)/2.

More later…

Nalin Pithwa

 

 

Pythagorean Triples

The Pythagorean Theorem, that “beloved” formula of all high school geometry students, says that the sum of the squares of the sides of a right triangle equals the square of the hypotenuse. In symbols,

a^{2}+b^{2}=c^{2} where a and b are the sides and c is the hypotenuse.

Since we are interested in number theory, that is, the theory of the natural numbers, we will ask whether there are any Pythagorean triangles all of whose sides are natural numbers. There are many such triangles. The most famous has side 3,4 and 5. Here are the first few examples:

3^{2}+4^{2}=5^{2}

5^{2}+12^{2}=13^{2}

8^{2}+15^{2}=17^{2}

28^{2}+45^{2}=53^{2}

Our first naive question is whether there are infinitely many Pythagorean triples, that is, triples of natural numbers (a,b,c) satisfying the equation a^{2}+b^{2}=c^{2}

The answer is “YES” for a silly reason. If we take a Pythagorean triple (a,b,c) and multiply it by some other number d, then we obtain a new Pythagorean triple

(ad,bd,cd). This is true because

(da)^{2}+(db)^{2}=d^{2}(a^{2}+b^{2})=d^{2}c^{2}=(dc)^{2}

Clearly, these new Pythagorean triples are not very interesting. So we will concentrate our attention on triples with no common factors. We will even give them a name:

A primitive Pythagorean triple (or PPT for short) is a triple of numbers (a,b,c) so  that a,b, and c have no common factors and satisfy

a^{2}+b^{2}=c^{2}.

To investigate whether are infinitely many PPT’s is the same as asking whether there is a formula to find as many PPT’s as we want — the formula would contain relationship(s) between a, b and c. 

As explained in the previous blog, the first step is to accumulate some data. I used a computer to substitute in values for a and b and checked if a^{2}+b^{2} is a square. Here are some PPT’s that I found:

(3,4,5); (5,12,13); (8,15,17); (7,24,25);

(20,21,29); (9,40,41); (12,35,37); (11,60,6);

(28,45,53); (33,56,65); (16,63,65.

A few conclusions can be easily drawn even from such a short list. For example, it certainly looks like one of a and b is odd and the other is even. It also seems that c is always odd.

It is not hard to prove that these conjectures are correct. First, if a and b are both even, then c would also be even. This  means that a,b and c would have a common factor of 2, so the triple would not be primitive. Next, suppose that a and b are both odd, which means that c would have to be even. This means that there are numbers x,y and z so  that

a=2x+1 and b=2y+1 and c=2z

We can substitute this in the equation a^{2}+b^{2}=c^{2} to get

(2x+1)^{2}+(2y+1)^{2}=(2z)^{2}

Hence, 2x^{2}+2x+2y^{2}+2y+1=2z^{2}

This last equation says that an odd number is equal to an even number, which is impossible, so a and b cannot both be odd. Since, we have just checked that they cannot both be even and cannot both be odd, it must be true that one is even and the other is odd. It’s then obvious from the equation a^{2}+b^{2}=c^{2} that c is also odd. 

We can always switch a and b, so our problem now is to find all solutions in natural numbers to the equation

a^{2}+b^{2}=c^{2} with a odd, b even and a,b,c, having no common factors.

The tools we will use are factorization and divisibility.

Our first observation is that if (a,b,c) is a primitive PPT, then we can factor

a^{2}=c^{2}-b^{2}=(c-b)(c+b)

Here are a few examples from the list given earlier, where note that we always take n to be odd and b to be even:

3^{2}=5^{2}-4^{2}=(5-4)(5+4)=1.9

15^{2}=17^{2}-8^{2}=(17-8)(17+8)=9.25

35^{2}=37^{2}-12^{2}=(37-12)(37+12)=25.49

33^{2}=65^{2}-56^{2}=(65-56)(65+56)=9.121

It looks like c-b and c+b are themselves always squares. We check this observation with a couple more examples:

21^{2}=29^{2}-20^{2}=(29-20)(29+20)=9.49

63^{2}=65^{2}-16^{2}=(65-16)(65+16)=49.81

How can we prove that c-b and c+b are squares? Another observation apparent from our list of examples is that c-b and c+b seem to have no common factors. We can prove this last assertion as follows. Suppose that d is a common factor of c-b and c+b, that is, d divides both c-b and c+b. Then, d also divides

(c+b)+(c-b)=2c and (c+b)-(c-b)=2b

Thus, d divides 2b and 2c. But, b and c have no common factor because we are assuming that (a,b,c) is a primitive Pythagorean triple. So, d must equal 1 or 2. But, d also divides (c-b)(c+b)=a^{2} and a is odd, so d must be 1. In other words, the only number dividing both c-b and

c+b is 1, so c-b and c+b have no common factor.

We now know that c-b and c+b have no common factor, and that their product is a square since (c-b)(c+b)=a^{2}. The only way that this can happen is if c-b and c+b are themselves squares. So, we can write

c+b=s^{2} and c-b=t^{2} where s>t \geq 1 are odd integers with no common factors. Solving these two equations for b and c yields

c=(s^{2}+t^{2})/2 and b=(s^{2}-t^{2})/2 and then

a=\sqrt{(c-b)(c+b)}=st

We have finished our first proof of elementary number theory! The following theorem records our accomplishment:

Theorem (Pythagorean Triple Theorem) You will get every primitive Pythagorean triple (a,b,c) with a odd and b even by using the formulas

a=st and b=(s^{2}-t^{2})/2 and c=(s^{2}+t^{2})/2 where

s>t \geq 1 are chosen to be any odd integers with no common factors.

More later…

Nalin Pithwa

A very very light introduction to Number Theory

This little article is a very very light introduction to Number Theory for those motivated to attempt RMO/INMO. On the other hand, it is a light introduction for anyone interested in beginning Number Theory. 

Number Theory is the study of the set of positive whole numbers 1,2,3,4,5,6,7…

which are often called the set of natural numbers. We will especially want to study the relationships between the different sorts of numbers. Since ancient times, people have separated the natural numbers into a variety of different types. Here are some familiar and not so familiar examples:

odd numbers {1,3,5,7,9,11…}

even numbers {2,4,6,8,10,…}

square numbers {1,4,9,16,25,36,…}

cube numbers {1,8,27,64,125,…}

prime numbers {2,3,5,7,11,13,17,19,23,29,31…}

composite numbers {4,6,8,9,10,12,14,15,16…}

1 (modulo 4) {1,5,9,13,17,21,25…}

3 (modulo 4) {3,7,11,15,19,23,27…}

triangular numbers {1,3,6,10,15,21…}

perfect numbers {6,28,496,,,,}

Fibonacci numbers {1,1,2,3,5,8,13,21…}

Many of these types of numbers are undoubtedly already known to you. Others, such as the “modulo 4” numbers, may not be familiar. A number is said to congruent to 1(modulo 4) if it leaves a remainder of 1 when divided by 4, and similar for the 3(modulo 4) numbers. A number is called triangular if that number of pebbles can be arranged in a triangle, with one pebble at the top, two pebbles in the next row, and so on. The Fibonacci numbers are created by starting with 1 and 1. Then, to get the next number in the list, just add the previous two. Finally, a number is perfect if the sum of all its divisors, other than itself, adds back up to the original number. Thus, the numbers dividing 6 are 1,2 and 3, and 1+2+3=6. Similarly, the divisors of 28 are 1,2,4,7 and 14, and

1+2+4+7+14=28.

We will encounter all these types of numbers, and many others, in our excursion through the Theory of Numbers.

Some Typical Number Theoretic Questions.

The main goal of number theory is to discover interesting and unexpected relationships  between different sorts of numbers and to prove that these relationships are true. In this section, we will describe a few typical number theoretic problems, some of which we will eventually solve, some of which have known solutions too difficult for us to include, and some of which remain unsolved to this day.

Sum of SquaresI. Can the sum of two squares be a square? The answer is clearly “YES”; for example, 3^{2}+4^{2}=5^{2} and

5^{2}+12^{2}=13^{2} These are examples of Pythagorean triples. We will describe all Pythagorean triples in a later blog.

Sums of Higher Powers. Can the sum of two cubes be a cube? Can the sum of two fourth powers be a fourth power? In general, can the sum of two nth powers be an nth power? The answer is NO. This famous problem, called Fermat’s Last Theorem, was first posed by Pierre de Fermat in the seventeenth century, but was not completely solved until 1994 by Andrew Wiles. Wiles’s proof uses sophisticated mathematical techniques that we will not be able to describe in detail. But, we can show (in some later blog) that no fourth power is a sum of two fourth powers.

Infinitude of Primes. A prime number is a number p whose only factors are 1 and p.

  • Are there infinitely many prime numbers?
  • Are there infinitely many primes that are 1 modulo 4 numbers?
  • Are there infinitely many primes that are 3 modulo 4 numbers?

The answer to all these questions is “YES”. We will prove these facts later in some blog.

Sum of Squares II. Which numbers are sums of two squares? It often turns out that questions of this sort are easier to answer first for primes, so we ask which (odd) prime numbers are a sum of two squares. For example,

3=NO;

5=1^{2}+2^{2}

7=NO

11=NO

13=2^{2}+3^{2}

17=1^{2}+4^{2}

19=NO

23=NO

29=2^{2}+5^{2}

31=NO

37=1^{2}+6^{2}

Do you see a pattern? Possibly not, since this is only a short list, but a longer list leads to the conjecture that p is a sum of two squares if it is congruent to 1(modulo 4). In other words, p is a sum of two squares, if it leaves a remainder of 1 when divided by 4, and it is not a sum of two squares if it leaves a remainder of 3.

Number Shapes. The square numbers are the numbers 1,4,9,16, …that can be arranged in the shape of a square. The triangular numbers are the numbers 1,3,6,10,… that can be arranged in the shape of a triangle.

A natural question to ask is whether there are any triangular numbers that are also square numbers (other than 1). The answer is YES; the smallest example being

36=6^{2}=1+2+3+4+5+6+7+8

So, we might ask whether there are more examples and, if som are there infinitely many ? To search for examples, the following formula is helpful:

1+2+3+4+...+(n-1)+n=n(n+1)/2

Twin Primes. In the list of primes, it is sometimes true that consecutive odd numbers are both prime. We have written the twin prime pairs less than 100:

(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61), (71,73)

Are there infinitely many twin primes? That is, are there infinitely many prime numbers p such that p+2 and  is also a prime? At present, no one knows the answer to this question.

Primes of the Form N^{2}+1

If we list the numbers of the form N^{2}+1 taking N=1,2,3,…we find that some of them are prime. Of course, if N is odd, then N^{2}+1 even, so it won’t be prime unless N=1. So, it’s really only interesting to take even values of N. We have highlighted the primes in the following list:

2^{2}+1=5

4^{2}+1=17

6^{2}+1=37

8^{2}+1=65=5.13

10^{2}+1=101

12^{2}+1=145=5.29

14^{2}+1=197

16^{2}+1=257

18^{2}+1=325=5^{2}.13

20^{2}+1=401

It looks like there are quite a few prime values, but if you take larger values of N you will find that they  become much rarer. So, we ask whether there are infinitely many primes of the form N^{2}+1. Again, no one presently knows the answer to this question.

We have now seem some of the types of questions that are studied in the Theory of Numbers. How does one attempt to answer these questions? The answer is that Number Theory is partly experimental and partly theoretical. The experimental part normally comes first; it leads to questions and suggests ways to answer them. The theoretical part follows; in this part, one tries to devise an argument that gives a conclusive answer to the questions. In summary, here are the steps to follow:

1) Accumulate data, usually numerical, but sometimes more abstract in nature.

2) Examine the data and try to find patterns and relationships.

3) Formulate conjectures (that is, guesses) that explain the patterns and relationships. These are frequently given by formulae.

4) Test your conjectures by collecting additional data and checking whether the new information fits your conjectures.

5) Devise an argument (that is, a proof) that your conjectures are correct.

All five steps are important in number theory and in mathematics. More generally, the scientific method always involves at least the first four steps. Be wary of any purported “scientist” who claims to have “proved” something using only the first three. Given any collection of data, it’s generally not too difficult to devise numerous explanations. The true test of a scientific theory is its ability to predict the outcome of experiments that have not yet taken place. In other words, a scientific theory only becomes plausible when it has been tested against new data. This is true of all real science. In mathematics, one requires the further step of a proof, that is, a logical sequence of assertions, starting from known facts and ending at the desired statement.

More later…

Nalin Pithwa

 

a non-trivial limit problem — calculus IIT JEE

Here is a what I call, a non-trivial problem of  evaluation of a limit. (Hey, I call it non-trivial because I could  only find a longish, brute-force solution as given below. If you have a clever, elegant solution, I would like to learn from you. Just write it down, take a snapshot in your smartphone camera, and post it in comments :-)).

Evaluate \lim_{x \rightarrow 0} {((a^{x}+b^{x}+c^{3})/3)}^{2/x}

Solution. The above limit can be recast as follows:

\lim_{x \rightarrow 0}{((a^{x}-1+b^{x}-1+c^{x}-1+3)/3)}^{2/x}

=\lim_{x \rightarrow 0}{((a^{x}-1)/3+(b^{x}-1)/3+(c^{x}-1)/3+1)}^{2/x}

Now, observe as x \rightarrow 0, (a^{x}-1)/3+(b^{x}-1)/3+(c^{x}-1)/3 also tends to zero.

So, let X=((a^{x}-1)/3+(b^{x}-1)/3+(c^{x}-1)/3). Hence, the required limit is equal to

\lim_{X \rightarrow 0}{(1+X)}^{(2/X)(X/x)}

=\lim_{X \rightarrow 0}{{((1+X)}^{(1/X)})}^{2X/x} call this A but we know that

lim_{X \rightarrow 0} {(1+X)}^{1/X}=e

Hence, the above expression becomes e^{(2/3)(( \lim_{x \rightarrow 0}(a^{x}-1)/x)+(\lim_{x \rightarrow 0}(b^{x}-1)/x)+(\lim_{x \rightarrow 0}(c^{x}-1)/x))}

=e^{(2/3)((\ln a)+(\ln b)+(\ln c))}

=e^{(2/3)(\ln (abc))}

={(abc)}^{2/3}.

So, what do you think — is there an alternate elegant solution to  my brute force solution above? if you have, please share it with me also.

More later…

Nalin Pithwa