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 .
(a) As usual, I'll often abbreviate to .
(b) The last axiom is equivalent to the Cancellation Property: If , , and , then .
Here's the proof:
Since there are no zero divisors, either or . Since by assumption, I must have , so .
Notice that I didn't divide both sides of the equation by a --- I cancelled a from both sides. This shows that division and cancellation aren't "the same thing".
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 .
Example. Give an example of a set of objects with a "multiplication" which is not commutative.
If you have had linear algebra, you know that matrix multiplication is not commutative in general. For instance, considering real matrices,
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: an element of the set .
Of course, is defined to mean . and have the obvious meanings.
There are several order axioms:
(k) The positive integers are closed under addition and multiplication.
(l) ( Trichotomy) If , either , , or .
Example. Prove that if and , then .
, so 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 .
Well-Ordering Axiom. 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 . Some consequences include the Division Algorithm and the principle of mathematical induction.
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.
(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.
Bruce Ikenaga's Home Page
Copyright 2017 by Bruce Ikenaga