Divisibility

We will use the following notation throughout this book. The integers are

$\displaystyle \mathbb{Z}=\{...,-2,-1,0,1,2,...\} $

and the natural numbers are

$\displaystyle \mathbb{N}=\{1,2,...\}. $

The rational numbers will be denoted by $ \mathbb{Q}$. They are the number which can be written as fractions:

$\displaystyle \mathbb{Q}=\{\frac{a}{b}\ \vert\ a,b\in \mathbb{Z}, b\not=0\}. $

The real numbers will be denoted by $ \mathbb{R}$ and the complex numbers will be denoted by $ \mathbb{C}$.

Definition 1.2.1   Given integers $ a$ and $ b$ we say $ a$ divides $ b$ (or $ a$ is a factor of $ b$, or $ a$ is a divisor of $ b$, or $ b$ is a multiple of $ a$) if there is an integer $ k$ such that $ b=ak$. In this case, we write

$\displaystyle a\vert b\ \ \ \ {\rm or}\ \ \ \ b\equiv 0 ({\rm mod}\ a). $

If $ a$ does not divide $ b$ then we write

$\displaystyle a\not\vert b\ \ \ \ {\rm or}\ \ \ \ b\not\equiv 0 ({\rm mod}\ a). $

We call an expression $ a=bd$ ($ a,b,d$ integers) a factorization of $ a$.

Since $ 1$ divides all integers, we sometimes call $ 1$ a ``trival factor'' and the factors greater than $ 1$ the ``non-trivial factors''.

Definition 1.2.2   An integer $ n>1$ which has no positive factors other than itself and $ 1$ is called prime. A number $ n>1$ which is not prime is called a composite.

Example 1.2.3   $ 12\equiv 0 ({\rm mod}\ 3)$, $ -18\vert$, $ 1\vert 7$, $ 3\not\vert 5$, the positive factors of $ 12$ are $ 1,2,3,4,6,12$.

Lemma 1.2.4   If $ d \mid a$ and $ d \mid b $ then $ d \mid (ax +by)$, for any integers $ x$ and $ y$.

proof: $ d \mid a$ implies that $ a=dc$ and $ d \mid b $ implies that $ b=df$. Therefore:

$\displaystyle ax+by=dcx+dfy=d(cx+fy) $

i.e. $ d \vert( ax+by)$. $ \Box$

A problem on cryptography which we will encounter later in this chapter involves factoring large numbers. In particular, consider the following question: What is the fastest general procedure to find the smallest non-trivial positive factor of an integer $ n>0$? This question may seem simple but if $ n$ is very large the answer is far from obvious. For example, consider the following 309-digit number

13506641086599522334960321627880596993888147560566702752448514385152
65106048595338339402871505719094417982072821644715513736804197039641
91743046496589274256239341020864383202110372958725762358509643110564
07350150818751067659462920556368552947521350085287941637732853390610
9750544334999811150056977236890927563
This number is called RSA-1024, since it has 1024 binary digits. The sum of its digits is 1369. If you can factor this number then RSA Security Inc will give you one hundred thousand dollars! See 
http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html
for more details.

However, if $ n$ is relatively small then there are some easy strategies to follow to factor it.

Lemma 1.2.5 (Basic factoring strategy)   If a positive integer $ n$ has a factorization $ n=ab$ ($ a,b$ integers) then either $ a\leq \sqrt{n}$ or $ b\leq \sqrt{n}$.

proof: Suppose that this statement were false, so $ a>\sqrt{n}$ and $ b>\sqrt{n}$. Then $ n=ab>\sqrt{n}\sqrt{n}=n$. This is a contradiction, so either $ a\leq \sqrt{n}$ or $ b\leq \sqrt{n}$. $ \Box$

The result above implies that,

Example 1.2.6   Let $ n=1233$. By the above fact, to find a positive factor of $ 1233$, we need only check if the integers $ 1,2,3,...,35$ divide $ n$ since $ \sqrt{1233}=35.11...$. Moreover, any such divisor must be odd is $ 1233$ is odd. Our first try, $ 1233/3$ turns out to be an integer and we get $ 1233=3\cdot 411$.

What about the factors of $ 411$? By the above fact, to find a positive factor of $ 411$, we need only check if the integers $ 1,2,3,...,20$ divide $ 441$ since $ \sqrt{411}=20.273...$. Again, it must be odd and our first try, $ 411/3$ turns out to be an integer and we get $ 411=3\cdot 137$.

To factor $ 137$ we check if $ 1,2,3,...,11$ divide $ 137$ since $ \sqrt{137}<12$. Trying all the odd numbers $ 3,5,7,9,11$, we see that none of them are divisors of $ 137$.

The complete factorization is $ 1233=3\cdot 3\cdot 137$.

The following notation is quite useful, as we will see in the next section.

The set of all multiples of $ b$ is denoted

$\displaystyle b\mathbb{Z}=\{...,-2b,-b,0,b,2b,...\} =\{m\in \mathbb{Z}\ \vert\ m=bk,\ {\rm for\ some\ integer}\ k\}. $

This may be visualized as the first column of the array which you get by listing all the integers in strings of $ b$-at-a-time,

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert} \vdots ... ... \hline b & b+1 & ... &2b-2& 2b-1 \\ \hline \vdots & & & & \vdots \end{tabular}$ (1.1)

or as a real number line with a ``notch'' every $ b$ units.

$\displaystyle {\rm The\ multiples\ of} \ 5 $

\begin{displaymath} \begin{array}{ccccccccccccccc} ...& \circ & \bullet & \circ&... ...-3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & ... \par \end{array}\end{displaymath}

which we may also visualize as the first column of the array

$\displaystyle \begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert} \vdots ... ...&3 & 4\\ \hline 5 & 6 & 7 & 8 & 9 \\ \hline \vdots & & & & \vdots \end{tabular}$ (1.2)


Subsections
David Joyner 2007-09-03