# Number Theory Contest Math

Find the smallest positive integer $n$ such that $n^4 + (n + 1)^4$ is composite. Find the sum of the first $5$ positive integers $n$ such that $n^2 - 1$ is the product of 3 distinct primes.

Answer to the first is $5$, and answer to the second is 104. Can anyone show me the solution process?

-
...direct computation? –  user7530 Oct 26 '13 at 17:22
Preferably not, but I can understand if that is the process for the first. –  Yadnarav3 Oct 26 '13 at 17:22
For the second, you must have that one of $n+1$, $n-1$ is an odd prime and the other is the product of two odd primes, which narrows it down. –  user7530 Oct 26 '13 at 17:25
so 14 and 16 are solutions –  Yadnarav3 Oct 26 '13 at 17:27
and 20,22,and 32, cool –  Yadnarav3 Oct 26 '13 at 17:29

For the second one

$$n^2-1=(n-1)(n+1)$$

This is the product of three primes if and only if

• $n-1=1$ and $n+1$= product of three primes. (not possible)
• $n-1$ is prime and $n+1$= is the product of two primes.
• $n+1$ is prime and $n-1$= is the product of two primes.

Thus, for the first few primes, you need to test if $p \pm 2$ is the product of two primes. Note that in this case $n=p \pm 1$ depending on the choice of sign in the first one.

The first five primes for which this happens are $13, 17, 19, 23, 31$. The corresponding $5$ n's are....

-

For the first one, it helps to know that if $a,b$ are relatively prime then any prime factor of $a^4+b^4$ is either $2$ or congruent to $1 \bmod 8$. (This happens to be in my first published paper $-$ admittedly this "publication" was the proceedings of a local high-school Math Fair... $-$ and can proved similarly to one proof of the corresponding $1 \bmod 4$ result for $a^2+b^2$, by finding an $8$th root of unity $a/b \bmod p$.) Since $n$ and $n+1$ are relatively prime and of opposite parity, this means you need only check divisibility by $17$, $41$, $73$, etc. For $n < 5$, the value of $n^4 + (n+1)^4$ is small enough that the only candidate composite number is $17^2 = 289$, which you can exclude by direct computation or otherwise (e.g. Fermat proved that there's no solution of $a^4+b^4=c^2$ in positive integers; or, the only Pythagorean triangle with hypotenuse $17$ has sides $8$ and $15$). So $n=5$ is the first candidate, and the first candidate prime factor actually divides $5^4 + 6^4 = 1921 = 17 \cdot 113$, so we're done.

-
you are a genius Noam! –  ILoveMath Nov 2 '13 at 5:18
(To clarify: I was certainly not the first to obtain the result about $p \mid a^4+b^4$, which must be classical; I just remember it well because I happen to have noticed it independently.) –  Noam D. Elkies Nov 4 '13 at 1:13