Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
4  
...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
1  
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer

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.

share|improve this answer
1  
you are a genius Noam! –  Learner 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.