Integers

This section will deal specifically with integers within the context of elementary number theory. I will start with a definition of what are integers.

Definition 1.1: (Integers)

Integers are defined as the set
$$\mathbb{Z} = \{...,-2,-1,0,1,2,...\}$$

Now that we have a definition of what integers are. We can look at some other definitions.

Definition 1.2: (Least-Integer Principle)

A nonempty set of integers that is bounded below contains a smallest element.

An example of such a set is $X \colon= \{x \in \mathbb{Z} \mid x > 1\}$.

Definition 1.3: (Greatest-Integer Principle)

A nonempty set of integers that is bounded above contains a largest element.

An example of such a set is $Y \colon= \{y \in \mathbb{Z} \mid y < 1\}$.

Definition 1.4:

We say that a divides b (written $a \mid b$) if and only if there is an integer
d such that ad = b.

The above definition pertains to a combination of numbers that are divisible. I can also start that is a does not divide b then we can state this as $a \nmid b$.

Now that I have defined some elementary definitions above. We can start by looking at proving the following.

Theorem 1.1:

If $a \mid b$ and $b \mid c$ then $a \mid c$.

Proof:
From the definition we know that there exists a q and r such that aq = b and br = c. Thus we can then state that aqr = br. We can then replace qr with s and br with c. We then have as = c which implies that $a \mid c$.

QED

We can then use the above information to prove the following

Lemma 1.1:

If $d \mid a$ and $d \mid b$, then $d \mid (a + b)$.

Proof:
From the definition, we know that there are integers q and r such that
$$dq = a$$ $$\text{ and }$$ $$dr = b.$$
Thus
$$a + b = d(q + r),$$
so from the definition again, $d \mid (a + b)$.

QED

In the same way, we can prove

Lemma 1.2:

If $d \mid a_1, d \mid a_2, \dots d \mid a_n$, then $d \mid (c_1a_1 + c_2a_2 + \dots + c_na_n)$ for any integers $c_1,c_2, \dots c_n$.

Proof:
From the definition, there are integers $q_1, q_2, \dots, q_n$ such that $a_1 = dq_1, a_2 = dq_2,
\dots, a_n = dq_n$. Thus
$$c_1a_1 + c_2a_2 + \dots + c_nq_n,$$
and from the definition again, $d \mid c_1a_1 + c_2a_2 + \dots + c_na_n$.

QED

Let us look at an example of how we can use the above lemma. Let us then see if it is possible to have 100 coins, made up of c pennies, d dimes and q quaters, be worth $5.00. Thus,

\[c + d + q = 100\] \[\text{and}\] \[c + 10d + 25q = 500\]

We can do the following:

\[c + 10d + 25q - (c + d + q) = 500 - 100\]

which gives

\[9d + 24q = 400\]

Since $3 \mid 9$ and $3 \mid 24$ the above lemma says that $3 \mid 9d + 24q$ which implies that $3 \mid 400$ which is impossible since 3 isn’t a factor of 400.

Lemma 1.3:

If $d \mid a$ then $d \mid ca$ for any integer c.

Proof:
From the definition, there are integers....

QED