The Division Algorithm

Posted by Nalin Pithwa

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

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Google+ account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: