A1.1 Arithmetic of Integers

The Division Algorithm (often called the Euclidean Algorithm in this context) is the mathematical backbone of our everyday decimal system. It essentially tells us that any number can be “packaged” into groups of a certain size, with a little bit left over.
For example, the number 432 is:
1. \(432=(43 \times 10)+2\) (The remainder 2 is the ones place).
2. \(43=(4 \times 10)+3\) (The remainder 3 is the tens place).
3. \(4=(0 \times 10)+4\) (The remainder 4 is the hundreds place).

The place value system is better understood with the help of :

Division Algorithm (Euclidean Algorithm) Given a natural number \(p>1\), every integer can be expressed uniquely in the form.
\(
s=q p+r, 0 \leq r<p, q \in \mathbf{Z} .
\)
Using the above result which has been stated without proof, we can prove tha following theorem.

Understanding the Components:

In the formula \(s=q p+r\) :
\(s\) is the Dividend (the number you are dividing).
\(p\) is the Divisor (the size of the groups).
\(q\) is the Quotient (how many full groups you have).
\(r\) is the Remainder (the “leftovers,” which must be smaller than the group size).

Example 1: Standard Positive Division
Let’s divide \(s=17\) by \(p=5\).
How many times does 5 fit into 17 ? It fits 3 times (\(3 \times 5=15\)).
What is left over? \(17-15=2\).
Result: \(17=(3 \times 5)+2\).
Here, \(q=3\) and \(r=2\). Note that \(0 \leq 2<5\), so the condition holds.

Example 2: Dividing a Negative Integer
This is where the uniqueness of the algorithm is most important. Let’s divide \(s=-17\) by \(p=5\).
We must ensure \(0 \leq r<5\).
If we chose \(q=-3\), then \(-17=(-3 \times 5)+(-2)\). This is incorrect because \(r\) cannot be negative.
We must go “past” the number to \(q=-4\).
Result: \(-17=(-4 \times 5)+3\).
Here, \(q=-4\) and \(r=3\). Now the condition \(0 \leq 3<5\) is satisfied.

Theorem 1: Given a natural number \(p>1\), every natural number can be written with the base \(p\).

Proof: Suppose X is a natural number. Using division algorithm write
\(
\begin{aligned}
& \mathrm{X}=x_0+q_1 p, 0 \leq x_0<p, q_1<\mathrm{X} \dots(1) \\
& q_1=x_1+q_2 p, 0 \leq x_1<p, q_2<q_1 \dots(2) \\
& q_2=x_2+q_3 p, 0 \leq x_2<p, q_3<q_2 \dots(3) \\
& q_{n-1}=x_{n-1}+q_n p, 0 \leq x_{n-1}<p, q_n<q_{n-1} \dots(4)
\end{aligned}
\)
Discontinue the process as soon as \(q_n<p\) and write \(q_n=x_n\). Substitute the value of \(q_1\) of (2) in (1), then the value of \(q_2\) of (3) in (1) and so on. These gradual substitutions give
\(
\mathrm{X}=x_0+q_1 p=x_0+p\left(x_1+q_2 p\right)=x_0+x_1 p+q_2 p^2
\)
\(
=x_0+x_1 p+p^2\left(x_2+q_y p\right)=x_0+x_y p+x_2 p^2+q_3 p^3
\)
\(
=\ldots \ldots \ldots=x_0+x_1 p+x_2 p^2+\ldots \ldots+x_n p^{{n}}
\)
We have proved that \(X\) can be written with the base \(p\), Written symbolically
\(
\mathrm{X}=\left\langle x_n, x_{n-1}, \ldots \ldots, x_1, x_0\right\rangle p
\)
Moreover, in the division algorithm, \(x_0 \ldots . . x_{\mathrm{n}}\) are unique. Therefore, the expansion of \(x\) in base \(p\) is unique.

Example 1: Express \(<2721>{ }_{10}\) in the base 11.

Solution:
\(
\begin{array}{ll}
2721=247 \times 11+4, & x_0=4 \\
247=22 \times 11+5, & x_1=5
\end{array}
\)
\(
22=2.11+0
\)
The algorithm stops since \(2<11\), So \(\langle 2721\rangle_{10}=\langle 2054\rangle_{11}\)

Example 2: Determine the number of digits of \(\langle 21210\rangle\), when expressed in base 10 .

Solution: \(\langle 21210\rangle_3=0+1.3+2.3^2+1.3^3+2.3^4=\langle 210\rangle_{10}\)
It is a three digit number.