Wednesday 6 June 2012

A Simple Olympiad Problem

In this post I am going to post an olympiad problem that one of the earliest problems which I had solved and after solving which I was satisfied with myself. It is a problem based on elementary number theory which is a very interesting part in olympiad mathematics and is the favourite of most of the lot.

The following problem was posed in 1978 Kurschak olympiad and it is said that only a few students were able to solve this problem.
$n>1$ $\Rightarrow$ $n^4+4^n$ is never a prime.
Solution:- 
If n is even then it will be divisible by 4 giving us composite numbers. Hence we need to consider the odd numbered values for n. Since n is odd we can write n = 2x+1 for some natural number x. 
$\therefore n^4+4^n = (n^2)^2+(2^2)^n = (n^2)^2+(2^n)^2$. Seeing this what I tried to do is completing the square(completing the square is a very useful tactic and helps in several problems).
Hence,  $n^4+4^n =(n^2+2^n)^2-2\times n^2\times2^n$ 
$=(n^2+2^n)^2-n^2\times2^{n+1}=(n^2+2^n)^2-n^2\times2^{2x+2}$
 $=(n^2+2^n)^2-(n\times2^{x+1})^2=(n^2+2^n+2^{x+1}n)(n^2+2^n-2^{x+1}n)$
Hence we have shown that $n^4+4^n$ with n odd factors out into two terms. Hence it remains to check whether the smaller is 1 or not. This is quite trivial. Therefore both the terms are strictly greater than 1 and the number is not a prime.
Now let me state the famous identity of Sophie Germain upon which this problem is based.
The Sophie-Germain Identity:- $a^4+4b^4=(a^2+2ab+2b^2)(a^2-2ab+2b^2)$

Exercise for the reader :
(a) Try to get the identity by starting from LHS and ending in RHS.
(b) Show that $3^{2008}+4^{2009}$ can be written as a product of two positive integers each of which is larger than $2009^{182}$. (RMO 2009)
(c)  $n>1$ $\Rightarrow$  $n^5+n^4+1$ is never a prime. (Problem Solving Strategies, Titu Andreescu and Razvan Gelca)
Posted by at 1 comment:
Subscribe to: Posts (Atom)