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.

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.

share|improve this question
    
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
add comment

3 Answers

up vote 3 down vote accepted

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$

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.