San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
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
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)).
Proof: Since α²−β²=(α−β)(α+β) if m divides (α−β) then it divides α²−β².
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.
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 Thayer Watkins |