# Proving $n^4 + 4 n^2 + 11$ is $16k$

if $n$ is an integer , prove that $n^4 + 4 n^2 + 11$ is of the form $16 k$.

And I went something like:

\begin{align*} n^4 +4 n^2 +11 &= n^4 + 4 n^2 + 16 -5 \\ &= ( n^4 +4 n^2 -5) + 16 \\ &= ( n^2 +5 ) ( n^2-1) +16 \end{align*}

So, now we have to prove that the product of $( n^2 +5 )$ and $( n^2-1)$ is a multiple of 16.

But, how can we do this? If anybody has any idea of how I can improve my solution, please share it here.

-
This assertion is true if and only if $n$ is an odd integer. That is, for even $n$ the assertion fails to hold. For example, for $n = 2$, we have $n^4+4n^2+11 = 43$, which is odd. For odd $n$, you can try $n = 2q+1$. – Sangchul Lee Aug 26 '12 at 9:27
sos440's comment is better justified by noticing that if $n$ is even, then so is $n^4+4n^2$. Hence $n^4+4n^2+11$ has to be odd (since $11$ is an odd number). – funktor Aug 26 '12 at 13:24

• $n=2k$:

$$n^4+4n^2+11\\=(n^2-1)(n^2+5)+16\\=(4k^2-1)(4k^2+5)+16\\=16k'^4+16k''^2+11\\=16k+11$$

Which is not $16k$.

• $n=2k+1$:

$$n^4+4n^2+11\\=(n^2-1)(n^2+5)+16\\=(4k^2+4k)(4k^2+4k+6)+16\\=8\underbrace{k(k+1)} _{2k}(2k^2+2k+3)+16$$

Which is $16k$.

-
The above is incorrect as in your last line you forgot to add the $\,16\,$ at the end: $$n^4+4n^2+11=8k(k+1)(2k^2+2k+3)+16$$ Now we just have to check that $\,k(k+1)(2k^2+2k+3)\,$ is always even, getting the multiple of 16 that we were missing. – DonAntonio Aug 26 '12 at 9:58
@DonAntonio: Edited, thanks. – Gigili Aug 26 '12 at 9:59
$(4k^2+4k+6)$ is a multiple of 2 while $(4k^2+4k)$ is a multiple of 8. So for odd $n$ this is a multiple of 16. – Henry Aug 26 '12 at 10:01
@Henry: The first is a multiple of $2$ and the second $4$. – Gigili Aug 26 '12 at 10:02
$4k^2+4k=4k(k+1)$ is a multiple of 8 whether $k$ is even or odd – Henry Aug 26 '12 at 10:03

The claim is false, for example $$n=2\Longrightarrow n^4+4n^2+11=16+16+11=43$$ which is not a multiple of 16. Check your expression.

Now, if $\,n=2k+1\,$ is odd, then the claim is true, since then $$n^4+4n^2+11=8k(k+1)(2k^2+2k+3)+16$$ and since $\,8k(k+1)=0\pmod {16}\,$ no matter what parity $\,k\,$ has, we're done.

-
Thanks, this question is from burton . and as much as I remember it was given that n is an integer ( not mentioned whether it was even or odd) but I will check it . – shrey Aug 26 '12 at 9:40
this question was from david burton's book. and as much as I remember it was mentioned that n is an integer ONLY. But I will again check to make sure otherwise there was a misprint. and I didn't check that. – shrey Aug 26 '12 at 9:49
I checked: it is problem 11 in section 2.2, page 19 (6th edition), and it is given that n is an odd integer. – DonAntonio Aug 26 '12 at 9:54
If $x = 3 \mod 4$, it doesn't necessarily follow that $x^2 = 9 \mod 16$. Take $x=7$, for example. – TonyK Aug 26 '12 at 11:57
True, but it does in this case. Anyway, corrected. Thanks. – DonAntonio Aug 26 '12 at 12:10

If $2|k=>16|n^4$ and $4|n^2=>16|(n^4+4n^2)=>n^4+4n^2+11≡11\pmod{16}$

Else

$n$ is odd$=2k+1$(say), $n^2=(2k+1)^2=8\cdot\frac{k(k+1)}{2}+1≡1\pmod{8}=>8|(n^2-1)$

(i)So, $n^4+4n^2+11=(n^2-1)^2+6(n^2-1)+16≡0\pmod{16}$ if $n$ is odd.

(ii)When $n$ is odd, $2|(n^2+1)$ and $8|(n^2-1)$(already proved) $=>2\cdot8|(n^2-1)\cdot(n^2+1)=>16|(n^4-1)$

(iii)When $n$ is odd, $n^2≡1\pmod{8}=1+8m$(say),

So, $n^4=(n^2)^2=(1+8m)^2=1+16m+64m^2≡1\pmod{16}$

So using (ii) or (iii), $n^4≡1\pmod{16}$ and $n^2≡1\pmod{8}=>4n^2≡4\pmod{32}$ if $n$ is odd,

So, $n^4+4n^2+11≡1+4+11\pmod{16}≡0\pmod{16}$ if $n$ is odd.

Alternatively, using Carmichael Function, $\lambda(16)=\frac{\phi(16)}{2}=4$ and $\lambda(8)=\frac{\phi(8)}{2}=2$

So, $n^4≡1\pmod{16}$ and $n^2≡1\pmod{8}=>4n^2≡4\pmod{32}$ if $(16,n)=1$ i.e., $n$ is odd,

So, $n^4+4n^2+11≡0\pmod{16}$ if $n$ is odd(like (ii)).

-
+1 Two solutions are both ingenious! – awllower Aug 26 '12 at 10:56

If $m$ is odd, then $m^2 \equiv 1$ (mod 8), since $(2a+1)^{2} = 4(a^{2}+a) +1$ and $a^2 +a$ is always even when $a$ is an integer. If $h$ is an integer congruent to $3$ (mod 8), then $h^{2}-9 = (h-3)(h+3)$ is divisible by $16$. Now when $n$ is odd, we have $n^{2}+2 \equiv 3$ (mod $8$), so $(n^{2}+2)^{2} \equiv 9$ (mod $16$), so $n^{4} + 4n^{2} + 11 \equiv 9 +7 \equiv 0$ (mod 16).

-
Remark: this method is essentially equivalent to completing the square (as did the OP) $$\rm mod\ 16\!:\,\ n^4\!+4n^2\!+11 \,\equiv\, (n^2\!+2)^2+7\,\equiv\, (n^2\!+2)^2\!-3^2\,\equiv\, (n^2\!-1)(n^2\!+5)$$ then proceeding as in my answer. – Bill Dubuque Aug 26 '12 at 14:45
Yes, I agree there is not much difference, though I had not seen your answer when I wrote mine. – Geoff Robinson Aug 26 '12 at 14:46

Hint $\rm\: n\,$ odd $\rm\,\Rightarrow 2\:|\:n^2\!+\!5,\ 8\:|\:n^2\!-\!1\!\:\Rightarrow\:16\:|\:(n^2\!+\!5)(n^2\!-\!1)\$ by $\rm\:mod\ 8\!:\ odd^2 \equiv \{\pm1,\pm3\}^2\equiv 1$

-