4
$\begingroup$

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?

$\endgroup$
5
  • 4
    $\begingroup$ ...direct computation? $\endgroup$ – user7530 Oct 26 '13 at 17:22
  • $\begingroup$ Preferably not, but I can understand if that is the process for the first. $\endgroup$ – user87611 Oct 26 '13 at 17:22
  • 1
    $\begingroup$ 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. $\endgroup$ – user7530 Oct 26 '13 at 17:25
  • $\begingroup$ so 14 and 16 are solutions $\endgroup$ – user87611 Oct 26 '13 at 17:27
  • $\begingroup$ and 20,22,and 32, cool $\endgroup$ – user87611 Oct 26 '13 at 17:29
4
$\begingroup$

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....

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ you are a genius Noam! $\endgroup$ – ILoveMath Nov 2 '13 at 5:18
  • $\begingroup$ (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.) $\endgroup$ – Noam D. Elkies Nov 4 '13 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy