Basic inequalities and Diophantine equations for junior section

Posted on May 15, 2012 by khorshijie

Here are the notes for the above two topics for junior section.

Inequalities and Diophantine Equations

Will upload the solutions to the questions later. Meanwhile I have to finish my geometry notes asap…

Cheers,

ksj

Techniques in solving Diophantine equations (Part 1)

Posted on April 5, 2012 by khorshijie

(IMO 2006 P4) Determine all pairs of integers $(x,y)$ of integers such that $1+2^x+2^{2x+1}=y^2$ .

A diophantine equation is a equation or a system of equations with multiple variables subjected to the condition that the variables are integers. It contributes to a large bulk of number theory questions in MO competitions. The techniques involved in solving diophantine equations are fairly standard. However, diophantine equation questions can be very creative and students usually have to exhibit creativity to solve these questions. I have listed several techniques that I know of in solving diophantine equations. The list is non-exhaustive and I certainly welcome more recommendations in the comments section 🙂

The techniques presented below assumes basic knowledge of modular arithmetic as well as important theorems like the FLT and Euler Theorem.

1. Considering residues

This is one of the most common technique and should be the first technique that students should use to examine a diophantine equation problem. By checking certain common modulos on each term of the equation, one can either arrive at a contradiction to prove that there’s no solution, or to find the unique solutions that satisfy the equation. Here’s a list of common modulos to take and the possible residues in each scenario:

$x^2 \equiv 1 \pmod{4}$ when $x$ is odd and $x^2\equiv 0 \pmod{4}$ when $x$ is even.
$x^2 \equiv 0, 1, 4 \pmod{8}$
$x^2 \equiv 0, 1, 4, 9 \pmod{16}$
$x^2 \equiv 0, 1 \pmod{3}$
$x^2 \equiv 0, 1, 4 \pmod{5}$
$x^2 \equiv 0, 1, 2, 4 \pmod{7}$

The above residues fall under the topic of quadratic residues. If $x^2 \equiv a \pmod{p}$ , then $a$ is known as a quadratic residue mod $p$ . To determine whether a number is a quadratic residue mod $p$ , one can use the Euler’s criterion which states that $a^{\frac{p-1}{2}} \equiv 1 \pmod{p}$ is $a$ is a quadratic residue. The proof for Euler’s criterion is a useful technique in number theory and I highly recommend students to research on the proof.

We also have the following common modulo relationships:

$x^3 \equiv 0, \pm 1 \pmod{7}$
$x^3 \equiv 0, \pm 1 \pmod{9}$
$x^4 \equiv 0, 1 \pmod{5}$
$x^4 \equiv 0,1 \pmod{16}$
$p \equiv \pm 1 \pmod {6}$ for prime $p>3$ .

Here’s an application of this technique on a past year SMO problem:

(SMO(O) 1998 Round 2 P3) Do there exist integers $x$ and $y$ such that $19^{19} =x^3+y^4$ ? Justify your answer.

The key to solving this problem is to identify that you have to take mod 13 on each term of the equation. Yea you gotta be slightly inspired to see that mod 13 is the key to this problem. By taking mod 13, we have $19^{19}\equiv 7 \pmod{13}, x^3\equiv 1, 5, 8, 12 \pmod{13},$ $y^4\equiv 1, 3, 9 \pmod{13}$ . You realise that you cannot obtain 7 no matter how you add the residues for $x^3$ and $y^4$ . Hence there can be no solutions to this diophantine equation.

As you can see from the solution above, one must be quite patient when employing the above technique… Just like the Fibonacci number example which Jun Wei used in a previous post, choosing the right modulo can take quite some time.

2. Factorisation

This is another common technique especially when exponential terms such as $a^x$ are given. We place the exponential term on one side of the equation and factorise the other terms on the other side of the equations. Then we write the exponential term $a^x$ as $a^{m+n}$ where $s>t$ . Upon splitting the exponents, we compare it with the factors on the other side of the equation.

Here’s a problem to illustrate this strategy:

Find all non-negative integer solutions to the equation $3^x-y^3=1$ .

We rewrite the equation as $1+y^3=3^x$ and factorise the left hand side of the equation into $(1+y)(1-y+y^2)=3^x$ . We can set up the following system of equations:

$\begin{cases}y+1=3^m\\ y^2-y+1=3^n\end{cases}$

where $m+n=x$ and $n\ge m$ .

It does not seem like we can proceed further. If we take a step back, we might notice that $y$ cannot be divisible by 3. At this point, we need to introduce another common technique which complements the factorisation technique: Euclidean algorithm. Finding the greatest common divisor of the two factors is of tremendous help because the greatest common divisor must be $3^m$ . We have:

$\text{gcd}(y+1, y^2-y+1)\\ =\text{gcd}(y^2+2y+1, y^2-y+1)\\ =\text{gcd}(3y, y^2-y+1)$

which suggests that $3^m | 3y$ . Based on our previous observation that $y$ is not divisible by 3, we can conclude that either $m=0$ or $m=1$ . When $m=0$ , we obtain the solution $(x,y)=(0,0)$ and when $m=1$ , we obtain the solution $(x, y)=(2, 2)$ . These are the only 2 solutions.

This technique is commonly applied in SMO 2nd round problems. Try to solve this problem from the SMO 4 years ago:

(SMO2008(J) 2nd Round) Determine all primes such that $5^p+4p^4$ is a perfect square.

Readers can refer to my notes on algebra for the solution to the above problem.

3. Discriminant of quadratic equation

If the diophantine equation given is a quadratic equation with 2 variables, the discriminant can come in handy to determine the bounds of the variables. If the variables are stated to be positive integer, it suggests that the discriminant must be a perfect square (or in rare cases, the square of a rational number). Here’s an old problem from Putnam, an undergraduate competition for students in American universities:

(Putnam 1954) Prove that there are no integers $x$ and $y$ such that $x^2+3xy-2y^2=122$ .

We have to arrange the equation to appear as a quadratic equation in terms of $x$ . Upon rearrangement we have $x^2+3xy-2y^2-122=0$ . By taking discriminant, we obtain $\triangle =17y^2+488$ . Now that you have been drilled with the idea of taking modulo, it should appear intuitive to take modulo 17 and check if it is possible to be a perfect square. It turns out that $17y^2+488 \equiv 12 \pmod{17}$ . However, 12 is not a quadratic residue of 17 (can be determined either by Euler’s criterion or listing). Hence the discriminant can never be a perfect square and there will be no integer solutions for $(x,y)$ .

This method turns out to be useful in solving the following SMO problem (which is duplicated from an olympiad in Moscow… lol)

(SMO(J)2006 2nd Round) Find all integer solutions of $x+y=x^2-xy+y^2$ .

That’s all I have to offer today. Will be taking a break tomorrow since tomorrow is Good Friday holiday. Next week I will be discussing more techniques including the squeeze principle, method of infinite descent and specific types of diophantine equations.

Cheers,

ksj

Sophie Germain’s Identity and factorisation using complex numbers

Posted on March 21, 2012 by khorshijie

There are a couple of factorisation formulas that students have to grasp which are widely publicised by Math Olympiad materials. However, the Sophie Germain’s Identity is often undiscussed even though it can be derived using simple manipulations. The identity states that:

$a^4+4b^4=(a^2+2ab+2b^2)(a^2-2ab+2b^2)$

This factorisation can be easily obtained through completing the square by adding and subtracting a $4a^2b^2$ term. Interestingly, this identity is more commonly applied in number theory questions than in pure algebra problems. For example, to prove that $4^{545}+545^4$ is a composite number, we can use Sophie Germain’s identity to factorise the expression into $(545^2+2\cdot 545\cdot 4^{136}+2 \cdot 4^{272})(545^2-2\cdot 545\cdot 4^{136}+2 \cdot 4^{272})$ to show that it is composite.

There are several IMO questions in the first few editions which are pretty manageable even for students in Junior section. Here’s a problem from IMO which can be easily cracked using Sophie Germain’s identity.

(IMO 1969 P1) Prove that there are infinitely many natural numbers $a$ with the following property: the number $z=n^4+a$ is not a prime number for any natural numbers $n.$

To solve this problem, we just have to show that $n^4+4k^4$ is always a composite number. Upon factorisation, we have $n^4+4k^4=(n^2+2nk+2k^2)(n^2-2nk+2k^2)$ and so it suffices to prove that $n^2-2nk+2k^2>1$ , which is obvious since $(n-k)^2+k^2-1>0$. Hence, we can choose $a=4k^n$ to form a composite number and since there is an infinite amount of choice for $k$ , the claim is proven.

Try solving this problem from AIME 1987

(AIME 1987 P14) Evaluate $\displaystyle{\dfrac{(10^{4}+324)(22^{4}+324)(34^{4}+324)(46^{4}+324)(58^{4}+324)}{(4^{4}+324)(16^{4}+324)(28^{4}+324)(40^{4}+324)(52^{4}+324)}}.$

There’s a useful factorisation technique which is not often taught in MOP lessons that involves complex numbers. Define a $n$ -th root of unity to be the complex solutions of $x^n=1$ . Let us call it $\omega$ . Through factorisation, we note that $\omega^{n-1}+\omega^{n-2}+\cdots+\omega+1=0.$ By using this fact coupled with factor theorem, we can factorise some challenging single variable expressions.

So suppose we want to factorise $x^{10}+x^5+1$ . A sharp student might identify this as a geometric sequence and compute it’s sum using the formula. Here’s how we proceed:

$\begin{aligned} x^{10}+x^5+1&=\dfrac{x^{15}-1}{x^5-1}\\ &=\dfrac{(x^3-1)(x^{12}+x^9+x^6+x^3+1)}{(x-1)(x^4+x^3+x^2+x+1)}\\ &=\dfrac{(x^2+x+1)(x^{12}+x^9+x^6+x^3+1)}{x^4+x^3+x^2+x+1}\\ &=(x^2+x+1)(x^8-x^7+x^5-x^4+x^3-x+1) \end{aligned}$

However, this approach is not entirely intuitive. It is not very obvious to see that you have to take out the factor $x^3-1$ from the numerator. It is also not very apparent for students to carry out long division for the last step.

A more powerful approach is the use of complex number to identify if $x^n+x^{n-1}+\cdots+x+1$ is a factor of the expression. So let us suppose $\omega_1$ and $\omega_2$ are the two 3rd roots of unity. This would imply that $\omega_1^2+\omega_1+1=0$ and $\omega_2^2+\omega_2+1=0$ . Now back to the original expression, suppose $f(x)=x^{10}+x^5+1$ . We have $f(\omega_1)=\omega_1^{10}+\omega_1^5+1=\omega_1^2+\omega_1+1=0$ since $\omega_1^3=1$ . Similarly $f(\omega_2)=0$ . By factor theorem, $(x-\omega_1)(x-\omega_2)=x^2+x+1$ is a factor of $f(x)$ . Upon long division we obtain the final answer.

As a shortcut, we can just examine the remainder of the powers of each $x$ term when they are divided by 3. If the remainders are 1, 2, and 0 respectively, it is divisible by $x^2+x+1$ . This also applies for other factors in the form of $x^n+x^{n-1}+\cdots+x+1$ .

Now try and show that $f(n)=n^5+n^4+1$ is not prime for integers $n>1$ .

Cheers,

ksj

Solutions to factorisation techniques

Posted on March 19, 2012 by khorshijie

Here are the solutions to the problem set at the end of the chapter. Note that there are typos in question 2(b) and 14. Will discuss miscellaneous problems in algebra next time before moving on to a new topic.

A Potpourri of Algebra

View this document on Scribd

Will be cool if I can publish these documents into a book ^^

Cheers,

ksj

Application of factorisation techniques

Posted on March 16, 2012 by khorshijie

I have updated the previous file again with a new section on factorisation. The emphasis is on the application of factorisation instead of factorisation techniques (I guess other MOP teachers have gone through these techniques before). I have to admit that the problems set is rather challenging…

Here’s a hint for some of the questions. Given $a+b+c=0$ , we have $a^3+b^3+c^3=3abc$ (Why?)

A Potpourri of Algebra

Cheers,

ksj

My Two Cents

HCMOP 2012

Tag Archives: Factorisation

Basic inequalities and Diophantine equations for junior section

Techniques in solving Diophantine equations (Part 1)

Sophie Germain’s Identity and factorisation using complex numbers

Solutions to factorisation techniques

Application of factorisation techniques

Share this:

Share this:

Share this:

Share this:

Share this: