San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

Remainders and Representations:
Simple Applications of Number Theory

The remainder of a number N upon division by a number m is the number r in the set {0, 1, 2, …, (m-1)} which is left over when multiples of m are subtracted from N. The fact that a number N has a remainder of r after division by m is expressed as

N ≡ r (mod m)

Mod is short for modulo. The condition of N having r as a remainder of r upon division by m is equivalent to m evenly dividing (N-r); i.e., (N-r) is an integral multiple of m. Another notation for m evenly dividing (N-r) is (m|(N-r)).

A Simple Theorem

If α≡β (mod m)
then
α²≡β² (mod m)

Proof: Since α²−β²=(α−β)(α+β) if m divides (α−β) then it divides α²−β².

Can a Number Which of the Form 8k+7
be Represented as the Sum of the Squares
of Three Numbers?

The answer is no and the proof of this is as follows.

A number N being of the form 8k+7 is equivalent to the condition N≡7 (mod 8). All numbers are congruent mod 8 to a number in the set {0, 1, 2 …, 7}.

Suppose there were three numbers b, c, d such that b²+c²+d²≡7 (mod 8). The numbers b, c and d would be congruent to some elements of the set {0, 1, 2 …, 7}. The squares of the elements in this set have the following congruencies

0² ≡ 0 (mod 8)
1² ≡ 1 (mod 8)
2² ≡ 4 (mod 8)
3³ ≡ 1 (mod 8)
4² ≡ 0 (mod 8)
5² ≡ 1 (mod 8)
6² ≡ 4 (mod 8)
7² ≡ 1 (mod 8)

Now consider the numbers that can be constructed as the sume of three elements of the set {0, 1, 4}.

These are:

0 + 0 + 0 = 0
0 + 0 + 1 = 4
0 + 0 + 4 = 4
0 + 1 + 0 = 1
0 + 1 + 1 = 2
0 + 1 + 4 = 5
0 + 4 + 0 = 4
0 + 4 + 1 = 5
0 + 4 + 4 = 8 ≡0 (mod 8)
1 + 0 + 0 = 1
1 + 0 + 1 = 2
1 + 0 + 4 = 5
1 + 1 + 0 = 2
1 + 1 + 1 = 3
1 + 1 + 4 = 6
1 + 4 + 0 = 5
1 + 4 + 1 = 6
1 + 4 + 4 = 9≡1 (mod 8)
4 + 0 + 0 = 4
4 + 0 + 1 = 5
4 + 0 + 4 = 8≡0 (mod 8)
4 + 1 + 0 = 5
4 + 1 + 1 = 6
4 + 1 + 4 = 9≡1 (mod 8)
4 + 4 + 0 = 8≡0 (mod 8)
4 + 4 + 1 = 9≡1 (mod 8)
4 + 4 + 4 = 12≡4 (mod 8)

There are numbers congruent to {0, 1, 2, … 6} but none to 7. Therefore there cannot be any numbers b, c and d such that b²+c²+d²≡7 (mod 8). In other words there is no number N congruent to 7 (mod 8) that can be represented as the sum of the squares of three integers.

Can a Number of the Form 9k+4 or 9k+5 be
Represented as the Sum of the Cubes of Three NUmbers?

Again the answer is no.

Since α³−β³ is equal to (α−β)(α²+αβ+β²) if m divides (α−β) then it divides α³−β³.

Any numbers b, c and d such that b³+c³+d³ equal to 9k+4 or 9k+5 would be congruent to some elements of the set {0, 1, 2, …, 7, 8}. Now consider what numbers the cubes of the numbers in the set {0, 1, 2, …, 7, 8} are congruent to.

0³ ≡ 0 (mod 9)
1³ ≡ 1 (mod 9)
2³ ≡ 8 (mod 9)
3³ ≡ 0 (mod 9)
4³ ≡ 1 (mod 9)
5³ ≡ 8 (mod 9)
6³ ≡ 0 (mod 9)
7³ ≡ 1 (mod 9)
8³ ≡ 8 (mod 9)

The numbers which are the sum of three elements from the set {0, 1, 8} are congruent modulo 9 to {0, 1, 2, 3, 6, 7, 8} but none to 4 or 5. Thus there can be no set of numbers b, c and d such that b³+c³+d³≡4 (mod 9) and likewise for b³+c³+d³≡5 (mod 9).


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins