# Applications of division algorithm

Prove that the expression $a(a^{2}+2)/3$ is an integer for all $a \geq 1$. According to the Division algorithm:

Given integers a and b, with $b>0$ there exist unique integers q and r such that

$a=qb+r$ where $0 \leq r < b$

The  integers q and r are respectively, the quotient and remainder in the division of a by b.

Proof:

The advantage of the Division Algorithm is that it allows us to prove assertions about all the integers by considering only a finite number of cases.

In this example, the division algorithm tells us that every integer a is of the form $3q$, $3q+1$ or $3q+2$. Assume the first of these cases. Then,

$\frac{a(a^{2}+2)}{3}=q(9q^{2}+2)$ which clearly is an integer. Similarly, if $a=3q+1$, then

$\frac{(3q+1)(3q+1)^{2}+2}{3}=(3q+1)(3q^{2}+2q+1)$

and the given expression is an integer in this instance also.

Finally, for $a=3q+2$, we obtain $\frac{(3q+2)((3q+2)^{2}+2)}{3}=(3q+2)(3q^{2}+4q+2)$ which is an integer once more. Consequently, our result is established in all cases.

Some more applications.

We wish to focus our attention on the applications of the Division Algorithm, and not so much on the algorithm itself. As another illustration, note that with $b=2$, the possible remainder are $r=0$ and $r=1$. When $r=0$, the integer a has the form $a=2q$ and is called even; when $r=1$, the integer a has the form and is called odd. Now, $a^{2}$ is either of the form $(2q)^{2}=4k$ or $(2q+1)^{2}=4k+1$. The point to made is that the square of an integer leaves the remainder 0 or 1 upon division by 4.

We also can show the following: The square of any odd integer is of the form $8k+1$. For, by the Division Algorithm, any  integer is representable as one of the four forms $4q$, $4q+1$, $4q+2$ and $4q+3$. In this classification, only those integers of the forms $4q+1$ and $4q+3$ are odd. When the latter are squared, w find that

$(4k+1)^{2}=8(2q^{2}+q)+1=8k+1$

and similarly,

$(4q=3)^{3}=8(2q^{2}+3q+1)=8k+1$.

As examples, the square of the odd integer 7 is $7^{2}=49= 8 \times 6 +1$, and the square of 13 is $13^{2}=169=8 \times 21 +1$.

So, once again, to recur an important point: the division algorithm allows us to prove assertions about all the integers by considering only a finite number of cases! 🙂 That’s a vast simplification/improvement !!

More later,

Nalin Pithwa

# The Division Algorithm

One theorem, the Division Algorithm, acts as the foundation stone upon which our whole development of Number Theory rests. The result is familiar to most of us; roughly, it asserts that an integer a can be “divided” by a positive integer b in such a way that the remainder is smaller than b. The exact statement is given below:

Division Algorithm.

Given integers a and b, with $b>0$, there exist unique integers q and r satisfying

$a=qb+r$, $0 \leq r < b$.

The integers q and r, are called, respectively, the quotient and remainder in the division of a by b.

Example.

We propose to show that the expression $a(a^{2}+2)/3$ is an integer for all $a \geq 1$. According to the Division Algorithm, every a is of the form 3q, $3q+1$, or $3q+2$. Assume the first of these cases. Then,

$\frac{a(a^{2}+2)}{3}=q(9q^{2}+2)$, which clearly is an integer. Similarly, if $a=3q+1$, then

$\frac{(3q+1)((3q+1)^{2}+2)}{3}=(3q+1)(3q^{2}+2q+1)$

and $a(a^{2}+2)/3$ is an integer in this instance also. Finally, for $a=3q+2$, we obtain

$\frac{(3q+2)((3q+2)^{2}+2)}{3}=(3q+2)(3q^{2}+4q+2)$

an integer once more. Consequently, our result is established in all cases.

More later,

Nalin Pithwa