Monday, March 20, 2006

Unprimely Speaking. Topic: Number Theory. Level: Olympiad.

Problem: (1969 IMO - #1) Prove that there are infinitely many positive integers $m$, such that $n^4+m$ is not prime for any positive integer $n$.

Solution: Well, that $ n^4 $ sure reminds us of our good old factoring trick... setting $ m = 4k^4 $ for a positive integer $ k > 1 $, we have

$ n^4+4k^4 = (n^2-2kn+2k^2)(n^2+2kn+2k^2) $.

If this is ever prime, then $ n^2-2kn+2k^2 = 1 $ (since it's the smaller factor), but we have

$ n^2-2kn+2k^2 = (n-k)^2+k^2 \ge k^2 > 1 $,

so our number is always composite. Since there are infinitely many possible values for $ k $, there are infinitely many possible values of $ m $, as desired. QED.

--------------------

Comment: This problem is nearly trivialized if you know that factoring trick, and it's an IMO problem (an old one, but that's ok). This is definitely one of the tricks you should memorize (or know how to derive instantly) because it comes in handy a lot.

--------------------

Practice Problem: (Problem-Solving Through Problems) Show that $ n^4-20n^2+4 $ is composite when $ n $ is any integer.

3 comments:

  1. Sophie Germaine's Identity is rather nice, I like it :)

    n^4 - 20n^2 + 4 = (n^2 - 2)^2 - 16n^2 = (n^2 + 4n - 2)(n^2 - 4n - 2). Rational Root Theorem tells us neither of these factors can be equal to 1, hence the expression is composite.

    ReplyDelete
  2. Sophie Germaine's also comes up alot with inequalities...usually they stick n^4+4 on the bottom, and then it usually decomposes by partial fractions and you can get the answer. For an example, see HMMT 2006 Algebra 9.

    ReplyDelete
  3. My bad, I meant infinite sums, not inequalities.

    ReplyDelete