Divisibility

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

and the natural numbers are

The rational numbers will be denoted by . They are the number which can be written as fractions:

The real numbers will be denoted by and the complex numbers will be denoted by .

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

If does not divide then we write

We call an expression ( integers) a factorization of .

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

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

Example 1.2.3   , , , , the positive factors of are .

Lemma 1.2.4   If and then , for any integers and .

proof: implies that and implies that . Therefore:

i.e. .

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 ? This question may seem simple but if 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 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 has a factorization ( integers) then either or .

proof: Suppose that this statement were false, so and . Then . This is a contradiction, so either or .

The result above implies that,

• if is composite then the smallest non-trivial factor of must satisfy ,
• if has no factor where then must be a prime.

Example 1.2.6   Let . By the above fact, to find a positive factor of , we need only check if the integers divide since . Moreover, any such divisor must be odd is is odd. Our first try, turns out to be an integer and we get .

What about the factors of ? By the above fact, to find a positive factor of , we need only check if the integers divide since . Again, it must be odd and our first try, turns out to be an integer and we get .

To factor we check if divide since . Trying all the odd numbers , we see that none of them are divisors of .

The complete factorization is .

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

The set of all multiples of is denoted

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

 (1.1)

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

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

 (1.2)

Subsections

David Joyner 2007-09-03