Divisibility and Remainders

Date: 8/23/96 at 4:59:13
From: Anonymous
Subject: Divisibility and Remainders

a) Show that every odd square leaves a remainder 1 when divided by 8, 
and that every even square leaves remainder 0 or 4. Deduce that a 
number of the form 8n + 7, where n is an integer, cannot be expressed 
as a sum of three squares.                      
               
b) Prove that n^5 - n is divisible by 30.

c) Suppose m is a positive integer divisible by 11. Prove that the 
integer m obtained by reversing the digits of m may also be divisible 
by 11.

Date: 8/23/96 at 8:20:3
From: Doctor Anthony
Subject: Re: Divisibility and Remainders

>a) Show that every odd square leaves a remainder 1 when divided
>by 8, and that every even square leaves remainder 0 or 4. Deduce
>that a number of the form 8n + 7, where n is an integer, cannot be
>expressed as a sum of three squares.

An odd square is of form 

   (2k+1)^2 = 4k^2+4k+1
            = 4(k^2+k) + 1
            = 4k(k+1) + 1.

Now either k or k+1 is even so this is M(8) + 1 where M(8) means 
multiple of 8.  Hence odd square leaves a remainder 1 when divided 
by 8.

An even square is of the form 

   (2k)^2 = 4k^2.

So if k is even this will be M(8) and remainder is 0.  If k is odd we 
could write k = 2m + 1.  So 

   (2k)^2 = 4k^2 = 4(2m+1)^2 = 4(4m^2+4m+1)
          = 16m^2 + 16m + 4
          = M(8) + 4.

So we get a remainder of 4.

Deduce that a number of the form 8n+7 cannot be expressed as a sum of 
three squares.  If we partition n so that n = a+b+c, then                     

   8n + 7 = 8a + 8b + 8c + 7
          = (8a+1) + (8b+4) + (8c+2).

Now 8a + 1 or 8b + 4 could be squares but 8c + 2 could not be (see 
part(i) of this question).  Indeed there is no way that you could 
split up 7 so as to give the remainders 0, 1, or 4 that are required 
with just three partitions of 7.  We conclude that 8n + 7 could not be 
the sum of three squares.

>b) Prove that n^5 - n is divisble by 30.

We can write this as n(n^4-1) = n(n^2-1)(n^2+1)
                              = n(n-1)(n+1)(n^2+1)
                              = (n-1)n(n+1)(n^2+1).

The product of three consecutive terms, n - 1, n, n + 1 must be 
divisible by 2 and by 3, and so by 6.  We must therefore show that 
n^5 - n is also divisible by 5 to show that it is divisible by 30.   

We can do this by induction. We have for n = 2  

2^5 - 2 = 32 - 2 = 30 = M(5).

Assume it is true for n=k and then consider n = k+1

We have 

   f(k) = k^5 - k = M(5)
   f(k+1) = (k+1)^5 - (k+1)  

   f(k+1) - f(k) = (k+1)^5 - (k+1) - (k^5 - k)
   = k^5 + 5C1k^4 + 5C2k^3 + 5C3k^2 + 5C4k + 1 - k - 1 - k^5 + k
   = 5C1k^4 + 5C2k^3 + 5C3k^2 + 5C4k
   = 5k^4 + 10k^3 + 10k^2 + 5k

So f(k+1) - f(k) = M(5), but f(k) = M(5) and so f(k+1) = M(5).

If f(n) is divisible by 5, then so is f(n+1).  But f(2) is divisible 
by 5, therefore f(3) is also divisible by 5, then f(4), f(5) and so on 
to all positive integral values of n. So the result is true generally.  
We have f(n) divisible by 6 and also by 5 for all n, and so f(n) is 
divisible by 30.

>c) Suppose m is a positive integer divisible by 11. Prove that the
>integer m obtained by reversing the digits of m may also be divisible >by 11.

If a number abcd is divisible by 11 we have:

   1000a + 100b + 10c + d and we write it in the form
   (1001-1)a + (99+1)b + (11-1)c + d
   = 1001a + 99b + 11c - (a+c) + (b+d).

This will be divisible by 11 if -(a+c) + (b+d) is zero or a multiple 
of 11.

If we wrote this expression in reverse order 

   dcba = 1000d+100c+10b+a, 

then this is divisible by 11 if -(d+b)+(c+a) is zero or a multiple 
of 11.  But this is the same condition that we had before, and so 
reversing the digits will not affect divisibility by 11. 

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/