9
$\begingroup$

Let $n=r^4+1$ for some $r$. Show that none of $3,5,$ and $7$ can divide $n$.

I am thinking to use a corollary that "each prime divisor p of an integer of the form $(2m)^4+1$ has the form $8k+1$", but I failed. Anyone can give some hint?

$\endgroup$
3
  • 3
    $\begingroup$ One prime at a time. For mod $5$, note that $r$ is congruent to one of $0,1,2,-2,-1$. Take the fourth power and add $1$. We get that the result is congruent to $1,2,2,2,2$, so never $0$. For mod $7$, $r$ is congruent to $0,1,2,3,-3.-2,-1$. In each case take the fourth power and add $1$. The results are congruent to $1,2,3,5,5,3,2$, never $0$. You can take care of the prime $3$. $\endgroup$ Apr 11, 2016 at 4:44
  • $\begingroup$ Presumably r is an integer ... $\endgroup$
    – abligh
    Apr 11, 2016 at 9:39
  • 1
    $\begingroup$ I love the three current answers. This is a good question, but it got three unique, excellent answers. $\endgroup$
    – dotancohen
    Apr 11, 2016 at 13:22

5 Answers 5

25
$\begingroup$

If $p\mid(r^4+1)$ for one of $p=3,5,7$ then $-1$ is a fourth power mod $p$, hence $(\mathbb{Z}/p\mathbb{Z})^{\times}$ has an element of order 8.

But this is impossible because $(\mathbb{Z}/p\mathbb{Z})^{\times}$ has order $p-1\leq 6$.

$\endgroup$
13
$\begingroup$

I'm going to try to make the most elementary possible proof.

$\bmod 3$, $(0, \pm 1)^4 \equiv (0, 1) $ so $(0, \pm 1)^4+1 \equiv (1, 2) $ so $3 \not \mid r^4+1$.

$\bmod 5$, $(0, \pm 1, \pm 2)^4 \equiv (0, 1, 1) $ so $(0, \pm 1, \pm 2)^4+1 \equiv (1, 2, 2) $ so $5 \not \mid r^4+1$.

$\bmod 7$, $(0, \pm 1, \pm 2, \pm 3)^4 \equiv (0, 1, 2, 4) $ so $(0, \pm 1, \pm 2, \pm 3)^4+1 \equiv (1, 2, 3, 5) $ so $7 \not \mid r^4+1$.

$\endgroup$
6
$\begingroup$

Use Fermat little theorem. If $r $ isn't divisible by 3, $r^2 \equiv 1 \mod 3$. If $r$ is divisible by 3 then $r^2 \equiv 0 \mod 3$. So $r^4 \not \equiv -1 \mod 3$ so $r^4 + 1$ is not divisible by 3.

Similarly $r^4 \equiv 1,0 \mod 5$ so $r^4 + 1$ is not divisible by 5.

If $r$ is not divisible by 7 then $r^6 \equiv 1 \mod 7$. So if $r^4 \equiv -1 \mod 7$ then $r^8 \equiv r^2 \equiv 1 \mod 7$. So, contradictory, $r^4 \equiv 1 \mod 7$. So $r^4 \not \equiv -1 \mod 7$. So $r^4 + 1$ is never disible by 7.

$\endgroup$
2
$\begingroup$

Here is a variant of @carmichael561's proof.

As before, we have an element of order $8$. By Lagrange's theorem, $8$ divides $p-1$ and so $p$ is of the form $8k+1$. But $3,5,7$ are not of the form $8k+1$.

This argument then allows us to extend the results to $p=11, 13, 19, 23, 29, \dots$, for which the original argument fails.

$\endgroup$
2
$\begingroup$

Check for $r=3k,3k+1,3k+2$

Then check for $r=5k,5k+1,5k+2,5k+3,5k+4$

Then check for $r=7k,7k+1,7k+2,7k+3,7k+4,7k+5,7k+6$

It is the easiest way but lengthy.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .