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.

Another special number(s): Wilson primes and playful programming!

Problem:

A prime number p is called a Wilson prime if $(p-1)! \equiv -1 \pmod {p^{2}}$. Using a computer and some programming language like C, C++, or Python find the three smallest Wilson primes.

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:

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.

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.