# The Ring of Integers

• The integers satisfy the axioms for an algebraic structure called an integral domain.
• The integers have an order relation ; they also satisfy the Well-Ordering Axiom, which is the basis for induction and the Division Algorithm.
• denotes the greatest integer less than or equal to x. The greatest integer function is an important function in number theory.

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

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 .