Fundamentals of Integers, Primes, and Factorization

Chapter 1: Fundamentals of Numbers

Numbers and Notation

We begin by talking about numbers. This may seem rather elementary, but it does set the scene and introduce a lot of notation. In addition, much of what follows is important in computing.

1.0.1 Integers: Definition and Properties

We begin by assuming you are familiar with the integers:

Sometimes called the whole numbers, these are just the numbers we use for counting. To these integers we add zero (0), defined as:

Once we have the integers and zero, mathematicians create negative integers by defining (-n) as the number which, when added to n, gives zero. So, n + (-n) = (-n) + n = 0. Eventually, we simplify writing n + (-n) = 0 to n - n = 0. We now have the set of positive and negative integers: {..., -3, -2, -1, 0, 1, 2, 3, 4, ...}. You are probably used to arithmetic with integers, which follows simple rules. To be on the safe side, we itemize them below for integers a and b:

1. a + b = b + a (Commutative property of addition)
2. a × b = b × a or ab = ba (Commutative property of multiplication)
3. -a × b = -ab
4. (-a) × (-b) = ab
5. To save space, we write a^k as a shorthand for a multiplied by itself k times. So, 3⁴ = 3 × 3 × 3 × 3 and 2¹⁰ = 1024. Note that aⁿ × a^m = a^n+m.
6. Do note that n⁰ = 1.

Factors and Prime Numbers

Many integers are products of smaller integers. For example, 2 × 3 × 7 = 42. Here, 2, 3, and 7 are called the factors of 42, and the splitting of 42 into these individual components is known as factorization. This can be a difficult exercise for large integers; indeed, its difficulty is the basis of some methods in cryptography.

Of course, not all integers have factors. Those that do not, such as:

• 3, 5, 7, 11, 13, ...
• 2²¹⁶⁰⁹¹ - 1, ...

...are known as primes. Primes have long fascinated mathematicians and others (see the resource below). There is a considerable industry looking for primes and fast ways of factorizing integers.

http://primes.utm.edu/

Division and Remainders

To get much further, we need to consider division. Division for integers can be tricky since the result may not be an integer. Division often gives rise to a remainder. For example:

9 = 2 × 4 + 1

If we try to divide 9 by 4, we have a remainder of 1.

In general, for any integers a and b:

b = k × a + r

Where r is the remainder. If r is zero, then we say a divides b, written a | b. A single vertical bar is used to denote divisibility. For example, 2 | 128 and 7 | 49. However, 3 does not divide 4 (the original text incorrectly symbolized this as 3 | 4).

Aside: Finding Factors

To find the factors of an integer, we can just attempt division by primes (i.e., 2, 3, 5, 7, 11, 13, ...). If the integer is divisible by k, then k is a factor, and we try again with the resulting quotient.