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.


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


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


and similarly,


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