Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/