Fundamental theorem of algebra: RMO training

It is quite well-known that any positive integer can be factored into a product of primes in a unique way, up to an order. (And, that 1 is neither prime nor composite) —- we all know this from our high school practice of “tree-method” of prime factorization, and related stuff like Sieve of Eratosthenes. But, it is so obvious, and so why it call it a theorem, that too “fundamental” and yet it seems it does not require a proof. It was none other than the prince of mathematicians of yore, Carl Friedrich Gauss, who had written a proof to it. It DOES require a proof — there are some counter example(s). Below is one, which I culled for my students:

Question:

Let E= \{a+b\sqrt{-5}: a, b \in Z\}

(a) Show that the sum and product of elements of E are in E.

(b) Define the norm of an element z \in E by ||z||=||a+b\sqrt{-5}||=a^{2}+5b^{2}. We say that an element p \in E is prime if it is impossible to write p=n_{1}n_{2} with n_{1}, n_{2} \in E, and ||n_{1}||>1, ||n_{2}||>1; we say that it is composite if it is not prime. Show that in E, 3 is a prime number and 29 is a composite number.

(c) Show that the factorization of 9 in E is not unique.

Cheers,

Nalin Pithwa.

A Special Number

Problem:

Show that for each positive integer n equal to twice a triangular number, the corresponding expression \sqrt{n+\sqrt{n+\sqrt{n+ \sqrt{n+\ldots}}}} represents an integer.

Solution:

Let n be such an integer, then there exists a positive integer m such that n=(m-1)m=m^{2}-m. We then have n+m=m^{2} so that we have successively

\sqrt{n+m}=m; \sqrt{n + \sqrt{n+m}}=m; \sqrt{n+\sqrt{n+\sqrt{n+m}}}=m and so on. It follows that

\sqrt{n+\sqrt{n+\sqrt{n+ \sqrt{n+\ldots}}}}=m, as required.

Comment: you have to be a bit aware of properties of triangular numbers.

Reference:

1001 Problems in Classical Number Theory by Jean-Marie De Koninck and Armel Mercier, AMS (American Mathematical Society), Indian Edition:

Amazon India link:

https://www.amazon.in/1001-Problems-Classical-Number-Theory/dp/0821868888/ref=sr_1_1?s=books&ie=UTF8&qid=1508634309&sr=1-1&keywords=1001+problems+in+classical+number+theory

Cheers,

Nalin Pithwa.

Another cute proof: square root of 2 is irrational.

Reference: Elementary Number Theory, David M. Burton, Sixth Edition, Tata McGraw-Hill.

(We are all aware of the proof we learn in high school that \sqrt{2} is irrational. (due Pythagoras)). But, there is an interesting variation of that proof.

Let \sqrt{2}=\frac{a}{b} with gcd(a,b)=1, there must exist integers r and s such that ar+bs=1. As a result, \sqrt{2}=\sqrt{2}(ar+bs)=(\sqrt{2}a)r+(\sqrt{2}b)s=2br+2bs. This representation leads us to conclude that \sqrt{2} is an integer, an obvious impossibility. QED.

Algebra : max and min: RMO/INMO problem solving practice

Question 1:

If x^{2}+y^{2}=c^{2}, find the least value of \frac{1}{x^{2}} + \frac{1}{y^{2}}.

Solution 1:

Let z^{'}=\frac{1}{x^{2}} + \frac{1}{y^{2}} = \frac{y^{2}+x^{2}}{x^{2}y^{2}} = \frac{c^{2}}{x^{2}y^{2}}

z^{'} will be minimum when \frac{x^{2}y^{2}}{c^{2}} will be minimum.

Now, let z=\frac{x^{2}y^{2}}{c^{2}}=\frac{1}{c^{2}}(x^{2})(y^{2})….call this equation I.

Hence, z will be maximum when x^{2}y^{2} is maximum but (x^{2})(y^{2}) is the product of two factors whose sum is x^{2}+y^{2}=c^{2}.

Hence, x^{2}y^{2} will be maximum when both these factors are equal, that is, when

\frac{x^{2}}{1}=\frac{y^{2}}{1}=\frac{x^{2}+y^{2}}{1}=\frac{c^{2}}{1}. From equation I, maximum value of z=\frac{c^{2}}{4}. Hence, the least value of \frac{1}{x^{2}} + \frac{1}{y^{2}}=\frac{4}{c^{2}}.

Some basics related to maximum and minimum:

Basic 1:

Let a and b be two positive quantities, S their sum and P their product; then, from the identity:

4ab=(a+b)^{2}-(a-b)^{2}, we have

4P=S^{2}-(a-b)^{2} and S^{2}=4P+(a-b)^{2}.

Hence, if S is given, P is greatest when a=b; and if P is given, S is least when a=b. That is, if the sum of two positive quantities is given, their product is greatest when they are equal; and, if the product of two positive quantities is given, their sum is least when they are equal.

Basic 2:

To find the greatest value of a product the sum of whose factors is constant.

Solution 2:

Let there be n factors a,b,c,\ldots, k, and suppose that their sum is constant and equal to s.

Consider the product abc\ldots k, and suppose that a and b are any two unequal factors. If we replace the two unequal factors a and b by the two equal factors \frac{a+b}{2}, \frac{a+b}{2}, the product is increased, while the sum remains unaltered; hence, so long as the product contains two unequal factors it can be increased without altering the sum of the factors; therefore, the product is greatest when all the factors are equal. In this case, the value of each of the n factors is \frac{s}{m}, and the greatest value of the product is (\frac{s}{n})^{n}, or (\frac{a+b+c+\ldots+k}{n})^{n}.

Corollary to Basic 2:

If a, b, c, \ldots k are unequal, (\frac{a+b+c+\ldots+k}{n})^{2}>abc\ldots k;

that is, \frac{a+b+c+\ldots +k}{n} > (\frac{a+b+c+\ldots + k}{n})^{\frac{1}{n}}.

By an extension of the meaning of the terms arithmetic mean and geometric mean, this result is usually stated as follows: the arithmetic mean of any number of positive quantities is greater than the geometric mean.

Basic 3:

To find the greatest value of a^{m}b^{n}c^{p}\ldots when a+b+c+\ldots is constant; m,n, p, ….being positive integers.

Solution to Basic 3:

Since m,n,p, …are constants, the expression a^{m}b^{n}c^{p}\ldots will be greatest when (\frac{a}{m})^{m}(\frac{b}{n})^{n}(\frac{c}{p})^{p}\ldots is greatest. But, this last expression is the product of m+n+p+\ldots factors whose sum is m(\frac{a}{m})+n(\frac{b}{n})+p(\frac{c}{p})+\ldots, or a+b+c+\ldots, and therefor constant. Hence, a^{m}b^{n}c^{p}\ldots will be greatest when the factors \frac{a}{m}, \frac{b}{n}, \frac{c}{p}, ldots are all equal, that is, when

\frac{a}{m} = \frac{b}{n} = \frac{c}{p} = \ldots = \frac{a+b+c+\ldots}{m+n+p+\ldots}

Thus, the greatest value is m^{m}n^{n}p^{p}\ldots (\frac{a+b+c+\ldots}{m+n+p+\ldots})^{m+n+p+\ldots}.

Some examples using the above techniques:

Example 1:

Show that (1^{r}+2^{r}+3^{r}+\ldots+n^{r})>n^{n}(n!)^{r} where r is any real number.

Solution 1:

Since \frac{1^{r}+2^{r}+3^{r}+\ldots+n^{r}}{n}>(1^{r}.2^{r}.3^{r}\ldots n^{r})^{\frac{1}{n}}

Hence, (\frac{1^{r}+2^{r}+3^{r}+\ldots+n^{r}}{n})^{n}>1^{r}.2^{r}.3^{r} \ldots n^{r}

that is, >(n!)^{r}, which is the desired result.

Example 2:

Find the greatest value of (a+x)^{3}(a-x)^{4} for any real value of x numerically less than a.

Solution 2:

The given expression is greatest when (\frac{a+x}{3})^{3}(\frac{a-x}{4})^{4} is greatest; but, the sum of the factors of this expression is 3(\frac{a+x}{3})+4(\frac{a-x}{4}), that is, 2a; hence, (a+x)^{3}(a-x)^{4} is greatest when \frac{a+x}{3}=\frac{a-x}{4}, that is, x=-\frac{a}{7}. Thus, the greatest value is \frac{6^{3}8^{4}}{7^{7}}a^{r}.

Some remarks/observations:

The determination of maximum and minimum values may often be more simply effected by the solution of a quadratic equation than by the foregoing methods. For example:

Question:

Divide an odd integer into two integral parts whose product is a maximum.

Answer:

Let an odd integer be represented as 2n+1; the two parts by x and 2n+1-x; and the product by y; then (2n+1)x-x^{2}=y; hence,

2x=(2n+1)\pm \sqrt{(2n+1)^{2}-4y}

but the quantity under the radical sign must be positive, and therefore y cannot be greater than \frac{1}{4}(2n+1)^{2}, or, n^{2}+n+\frac{1}{4}; and since y is integral its greatest value must be n^{2}+n; in which case x=n+1, or n; thus, the two parts are n and n+1.

Sometimes we may use the following method:

Find the minimum value of \frac{(a+x)(b+x)}{c+x}.

Solution:

Put c+x=y; then the expression =\frac{(a-c+y)(b-c+y)}{y}=\frac{(a-c)(b-c)}{y}+y+a-c+b-c

which in turn equals

(\frac{\sqrt{(a-c)(b-c)}}{\sqrt{y}}-\sqrt{y})^{2}+a-c+b-c+2\sqrt{(a-c)(b-c)}.

Hence, the expression is a a minimum when the square term is zero; that is when y=\sqrt{(a-c)(b-c)}.

Thus, the minimum value is a-c+b-c+2\sqrt{(a-c)(b-c)}, and the corresponding value of x is \sqrt{(a-c)(b-c)}-c.

Problems for Practice:

  1. Find the greatest value of x in order that 7x^{2}+11 may be greater than x^{3}+17x.
  2. Find the minimum value of x^{2}-12x+40, and the maximum value of 24x-8-9x^{2}.
  3. Show that (n!)^{2}>n^{n} and 2.4.6.\ldots 2n<(n+1)^{n}.
  4. Find the maximum value of (7-x)^{4}(2+x)^{5} when x lies between 7 and -2.
  5. Find the minimum value of \frac{(5+x)(2+x)}{1+x}.

More later,

Nalin Pithwa.

Algebra question: RMO/INMO problem-solving practice

Question:

If \alpha, \beta, \gamma be the roots of the cubic equation ax^{3}+3bx^{2}+3cx+d=0. Prove that the equation in y whose roots are \frac{\beta\gamma-\alpha^{2}}{\beta+\gamma-2\alpha} + \frac{\gamma\alpha-\beta^{2}}{\gamma+\\alpha-2\beta} + \frac{\alpha\beta-\gamma^{2}}{\alpha+\beta-2\gamma} is obtained by the transformation axy+b(x+y)+c=0. Hence, form the equation with above roots.

Solution:

Given that \alpha, \beta, \gamma are the roots of the equation:

ax^{3}+3bx^{2}+3cx+d=0…call this equation I.

By relationships between roots and co-efficients, (Viete’s relations), we get

\alpha+\beta+\gamma=-\frac{3b}{a} and \alpha\beta+\beta\gamma+\gamma\alpha=\frac{3c}{a}, and \alpha\beta\gamma=-\frac{d}{a}

Now, \gamma=\frac{\beta\gamma-\alpha^{2}}{\beta+\gamma-2\alpha}=\frac{\frac{\alpha\beta\gamma}{\alpha}-\alpha^{2}}{(\alpha+\beta+\gamma)-3\alpha}=\frac{-\frac{d}{a\alpha}-\alpha^{2}}{-\frac{3b}{a}-3\alpha}=\frac{d+a\alpha^{3}}{3\alpha(b+a\alpha)}, that is,

3xy(b+ax)=d+ax^{3}, or ax^{3}-3ayx^{2}-3byx+d=0…call this equation II.

Subtracting Equation II from Equation I, we get

3(b+ay)x^{2}+3(c+by)x=0

(b+ay)x+c+by=0 since x \neq 0

axy+b(x+y)+c=0 which is the required transformation.

Now, (ay+b)x=-(by+c), that is, x=-\frac{by+c}{ay+b}

Putting this value of x in Equation I, we get

-a(\frac{by+c}{ay+b})^{3}+3b(\frac{by+c}{ay+b})^{2}-3c(\frac{by+c}{ay+b})+d=0, that is,

a(by+c)^{3}-3b(by+c)^{2}(ay+b)+3c(by+c)(ay+b)^{2}-d(ay+b)^{3}=0, which is the required equation.

Cheers,

Nalin Pithwa.