Hi I am Bishal Deb.: 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.

$\Rightarrow$ 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 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)

Hi I am Bishal Deb.

Wednesday, 6 June 2012

A Simple Olympiad Problem

1 comment:

Gonit Sora