<strong>(a) Prove that, for any odd integer n, when divided by 16 always leaves remainder 1.</strong>

<strong>(b) Hence or otherwise show that we cannot find integers such that .</strong>

Solution: For part (a) we consider n = 2k +1 and expand it’s fourth power binomially to get

Now ; if k is even then 8k is divisible by 16 and if k is odd 3k+1 is even and product of 8k and 3k+1 is divisible by 16. Since is already divisible by 16 we conclude when divided by 16 gives 1 as remainder.

For part (b) we note that 1993 when divided by 16 produces 9 as the remainder. Each of the eight of fourth powers when divided by 16 produces either 0 (when is even) or 1 (when is odd using part (a)) as remainder. Thus they can add up to at most 8 (modulo 16) hence can never be equal to 9 (which 1993 is modulo 16).