We say that a nonzero b divides a if a = mb for some m, where a, b, and m are integers. That is, b divides a if there is no remainder on division.

**DIVISIBILITY
AND THE DIVISION ALGORITHM**

Divisibility

We say that a nonzero *b ***divides ***a *if
*a *= *mb *for some *m*, where
*a*,
*b*,
and *m *are integers. That is, *b *divides
*a *if there is no remainder on division. The notation *b *| *a *is commonly used to mean *b *divides *a*. Also, if *b *| *a*, we say that *b *is a **divisor **of *a*.

Subsequently, we will need some simple
properties of divisibility for integers, which are as follows:

The Division
Algorithm

Given any positive integer
*n
*and any nonnegative integer *a*, if we divide *a *by
*n*, we get an integer quotient *q
*and an integer remainder *r *that
obey the following relationship:

where |*x** *| is the largest
integer less than
or equal to *x*. Equation (4.1)
is referred to as the division algorithm.

Figure 4.1a demonstrates that, given *a *and positive
*n*, it is always possible to find *q *and *r *that satisfy the preceding relationship. Represent the integers on the number line; *a *will
fall somewhere on that
line (positive *a *is shown, a similar
demonstration can be made for negative
*a*). Starting at 0, proceed to *n*, 2*n*, up to *qn*, such that *qn* <=*a *and(*q *+ 1)*n *>
*a*. The distance
from *qn *to *a *is *r*, and we have
found the unique values of *q *and *r*. The remainder *r *is often
referred to as a **residue**.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Basic Concepts in Number Theory and Finite Fields : Divisibility and the Division Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.