# question related to divisibility

how to prove the following:

if $a$ and $b$ are both odd integers, prove:

$$a^4 +b^4 \equiv 2 \pmod{16}$$

If anybody know any other method or solution other than putting $a$ or $b = 2k+1$ or using the fact that square of an odd integer is of the form $8k+1$ then share that solution here.

-
One immediate reduction would seem that your statement is equivalent to $a^4\equiv1\pmod{16}$ for all odd $a$. Why did you add $b$? – Marc van Leeuwen Aug 29 '12 at 9:12

If $c$ is odd=$2k+1$(say),

(i)$c^2=(2k+1)^2=8\frac{k(k+1)}{2}+1=8y+1$ for some integer $y$.

$c^4=(c^2)^2=(8y+1)^2=64y^2+16y+1=1+16(y+4y^2)=1+16z$ for some integer $z$.

(ii) $c^4=(2k+1)^4=(2k)^4+ ^4C_1(2k)^3+ ^4C_2(2k)^2+ ^4C_3(2k)+ 1$

$=16k^4+32k^3+24k^2+8k+1≡8k^2+8k+1\pmod {16}=16\frac{k(k+1)}{2}+1≡1\pmod {16}$

(iii)we have already found $8\mid(c^2-1)$

Now $2\mid(c^2+1)$ as $c$ is odd, so, $8\cdot 2\mid(c^2-1)(c^2+1)=>16\mid(c^4-1)$

(iv) Using this, $\lambda(16)=\frac{\phi(16)}{2}$ as $16$ is a power$(≥3)$ of $2$, so $\lambda(16)=4=>c^4≡ 1\pmod {16}$ if $(c,16)=1$ i.e., if $c$ is odd.

So, in all the 4 ways we have proved, $c^4$ leaves remainder $1$ when divided by $16$ if $c$ is odd.

So, $a^4$, $b^4$ each will leave $1$ as remainder when divided by $16$

-
Minor TeX tip: Use \mid to get a vertical bar acting as a relation (more space around the bar). You get $8\mid(c^2-1)$ instead of $8|(c^2-1)$. – Harald Hanche-Olsen Aug 29 '12 at 7:23
Thanks @HaraldHanche-Olsen, I've rectified & I'll use this in future. – lab bhattacharjee Aug 29 '12 at 7:30

We use induction. Since taking fourth powers does not depend on the sign, assume $a,b$ are non-negative. The statement is obviously true for $a=b=1$. Now, if it is true for $(a,b)$ then we want to show that it is true for $(a+2,b)$.

$$(a+2)^4 + b^4 - 2 = (a^4+b^4-2)+ 8a^3+24a^2+32a+16\\ = (a^4+b^4-2) + 16(2a+1) + 8a^2(a+3)$$

which is divisible by 16 since $a+3$ is even. Similarly if the statement is true for $(a,b)$, it is true for $(a,b+2)$. Hence it is true for all pair of odd integers.

-

One has $a^4-b^4=(a-b)(a+b)(a^2+b^2)$. If $a,b$ are odd, all factors in this product are even, and one of the the first two factors is even divisible by $4$. This shows that in this case $a^4\cong b^4\pmod{16}$, so all odd fourth powers are in the same congruence class modulo $16$, and it doesn't take long to figure out which class that is. In any case twice that class is the class of $2$.

-