Elementary number theory is largely about the ring of integers, denoted by the symbol . The integers are an example of an algebraic structure called an integral domain. This means that satisfies the following axioms:
(a) has operations + (addition) and (multiplication). It is closed under these operations, in that if , then and .
(b) Addition is associative: If , then
(c) There is an additive identity : For all ,
(d) Every element has an additive inverse: If , there is an element such that
(e) Addition is commutative: If , then
(f) Multiplication is associative: If , then
(g) There is an multiplicative identity : For all ,
(h) Multiplication is commutative: If , then
(i) The Distributive Laws hold: If , then
(j) There are no zero divisors: If and , then either or .
Remarks.
(a) As usual, I'll often abbreviate to .
(b) The last axiom is equivalent to the Cancellation Property: If , , and , then .
Example. If , prove that .
Adding to both sides, I get
By associativity for addition,
Then using the fact that and are additive inverses,
Finally, 0 is the additive identity, so
Example. If , prove that .
In words, the equation says that the additive inverse of n (namely ) is equal to . What is the additive inverse of n? It is the number which gives 0 when added to n.
Therefore, I should add and see if I get 0:
By the discussion above, this proves that .
The integers are ordered --- there is a notion of greater than (or less than). Specifically, for , is defined to mean that is a positive integer --- and element of the set .
Of course, is defined to mean . and have the obvious meanings.
There are two order axioms:
(k) The positive integers are closed under addition and multiplication.
(l) ( Trichotomy) If , either , , or .
Example. Prove that if and , then .
Since , is a positive integer. means is a positive integer, so by closure is a positive integer.
By a property of integers (which you should try proving from the axioms), . Thus, is a positive integer. So is a positive integer, which means that .
The Well-Ordering Property of the integers sounds simple: Every nonempty subset of the positive integers has a smallest element. Your long experience with the integers makes this principle sound obvious. In fact, it is one of the deeper axioms for ; for example, it can be used to proved the principle of mathematical induction, which I'll discuss later.
Example. Prove that is not a rational number.
The proof will use the Well-Ordering Property.
I'll give a proof by contradiction. Suppose that is a rational number. In that case, I can write , where a and b are positive integers.
Now
(To complete the proof, I'm going to use some divisibility properties of the integers that I haven't proven yet. They're easy to understand and pretty plausible, so this shouldn't be a problem.)
The last equation shows that 2 divides . This is only possible if 2 divides a, so , for some positive integer c. Plugging this into , I get
Since 2 divides , it follows that 2 divides . As before, this is only possible if 2 divides b, so for some positive integer d. Plugging this into , I get
This equation has the same form as the equation , so it's clear that I can continue this procedure indefinitely to get e such that , f such that , and so on.
However, since , it follows that ; since , I have , so . Thus, the numbers a, c, e, ... comprise a set of positive integers with no smallest element, since a given number in the list is always smaller than the one before it. This contradicts Well-Ordering.
Therefore, my assumption that is a rational number is wrong, and hence is not rational.
Finally, I want to mention a function that comes up often in number theory.
Definition. If x is a real number, then denotes the greatest integer function of x. It is the largest integer less than or equal to x.
Lemma. If x is a real number, then
Proof. By definition, . To show that , I'll give a proof by contradiction.
Suppose on the contrary that . Then is an integer less than or equal to x, but --- which contradicts the fact that is the largest integer less than or equal to x. This contradiction implies that .
Lemma. If and , then .
Proof. Suppose . I want to show that .
Assume on the contrary that . Since is the {\it greatest} integer which is less than or equal to x, and since is an integer which is greater than , it follows that can't be less than or equal to x. Thus, . But , so , which is a contradiction.
Therefore, .
Example.
(Notice that is not equal to -1.)
Example. Let x be a real number and let n be an integer. Prove that .
First, , so . Now is an integer less than or equal to , so it must be less than or equal to the greatest integer less than or equal to --- which is :
Next, , so . is an integer less than or equal to x. Therefore, it must be less than or equal to the greatest integer less than or equal to x --- which is :
Adding n to both sides gives
Since and , it follows that .
Copyright 2007 by Bruce Ikenaga