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
Math Forum Home || Math Library || Quick Reference || Math Forum Search