Integers and Congruences - Part II

3. Divisibility

Earlier, we have talked about even numbers and that we can write them as 2k where k is an integer. Here, we look into the question of divisibility and factors some more.

Definition of divisor, factor (delare, faktor)

Let a,b be integers. Then b is a divisor (factor, delare, faktor) of a if a=bs for some integer s. Write b | a. We also say that a is divisible (delbart) by b. If a is not divisible by b, we write b a.

It is important to notice that the expression 'a är delbart med b' means that there is no remainder when 'a delas med b' - we do not need to add the word 'jämnt.'

What results do we know about divisibility? The following theorem summarizes some of them.

Theorem: Divisibility Rules

Let a,b,c be integers

1. if a | b and b | c then a | c.
2. if a | b and a | c then a | (b+c).
3. if a | b then a | bx for all integers x.
4. if c | a and c | b then c | (ax+by) for all integers x, y.

While we are considering divisibility, we need to consider prime numbers, but what exactly is a prime number?

Definition: Prime number, composite number

A positive integer p > 1 which has only the divisors 1 and itself is called a prime number or simply a prime (primtal). A positive integer n 2 which is not a prime is called a composite number (sammansatt tal).

What results do we know about primes? When we try to factorize a number into primes, can we always do it? (We consider 5 to already be the product of primes, although it is just the product of one prime, 5 itself!.) In how many different ways can we do it? If we factorize 6 we get 32 or 23 which are the same if we ignore the order of the prime factors. Is this always the case? The follow theorem says that it is.

Theorem: Fundamental Theorem of Arithmetic

Every integer n 2 can be written as the product of primes. There is exactly one way to do this upto the order of the factors.

We omit the proof of this result for the moment.

How many primes are there? Is there always 'one more' to be found, or do they run out at some point? The following result says that there are infinitely many primes. This is an important proof, which you should know.

Theorem: Infinitely Many Primes

There are infinitely many primes.

Proof (Euclid)

Comments

Suppose there is a finite number of primes. Then we can list all of them as p1, p2, ..., pk. Consider n=p1p2...pk+1. Every integer greater than 1 can be written as the unique product of primes upto the order of the primes, (Fundamental Theorem of Arithmetic) so n has prime factors. Now n is not divisible by pi for 1 i k, so n has a prime factor q (which may be n itself) which is not pi for any i, 1 i k. Hence q is not in the list, so the list is incomplete, which is a contradiction. Therefore there is an infinite number of primes.

We use contradiction here. We know that if we have a finite set, then we can make a complete (finite) list of all the elements. We will find a prime which is not in our list - which gives us a contradiction.

Is it a Prime?

Now we know that there are infinitely many primes numbers, how do we find them? Basically, we pick a number and then test it to see if it has any divisors. Do we have to test all integers from 2 upto the number we are testing? No. It is enough to test upto its square root.

Result: Testing for Primes

Let n 2 be an integer. If there is no prime factor k of n where 1 k n, then n is a prime.

Proof	Comments
Suppose n 2 is an integer which is not a prime, and there is no prime factor k of n where 1 k n, then n is a prime. We will obtain a contradiction.	What we are trying to prove is a bit confusing, isn't it? Maybe trying an example to see what it means might help us to start with. We know what a prime is. Now for an example. Let's take n=61. Then n is a bit under 8 which means we need to test all primes which are smaller than 8, that is, we test k=2,3,5,7. None of these are factors of 61, so 61 is a prime. We're going to try to prove this using contradiction so we have to decide what we are going to assume. Ok, so we assume the part between "if" and "then": n has no factor k where 1 k n and "not" the bit after the "then": and n is not prime.
As p is not prime, it has postive factors a,b such that n=ab and 1 < a b < n.	Now we have to do something, but what? If n is not prime, what is it then? It's an integer which has positive factors which aren't 1 or n, so we can write n=ab for some integers a and b, and just to make life easier, let's take a b.
Suppose a > n. Then n= ab > n n = n, which is a contradiction so a n.	What do we know about the size of a? Well, if it is bigger than n we are in trouble as then a and b are both big and their product ab is the greater than n. This means that a must be at most n. Ah, so we have a factor a of n which is at most n.
By the Fundamental Theorem of Arithmetic, a has a prime factorization. Suppose p is a prime factor of a. Then 1 < p a n. Now p|a and a|n so p|n, which is a contradiction as we assumed that n has no such prime factors. This completes the proof.	Now, if we find a prime factor of n which isn't too big, we have a contradiction. Hopefully, we can use a to find this factor - it could even be a! We know that every integer greater than 1 can be expressed at the product of primes, so a has a prime factor p, which is thus also a factor of n and p is at most as big as a and a is at most n. This is a contradiction as we said n has no prime factor which is at most n, so our assumption that n is not prime is false and n is prime.

Example

Is 437 a prime?
We test all primes upto 437 which is around 22. The primes upto 22 are: 2, 3, 5, 7, 11, 13, 17, 19. We find that 19 is a factor of 437 so it is not a prime.

Exercises

1. Decide which of the following are primes.
   1. 321
   2. 207
   3. 2047
2. Is the set of all primes countable or uncountable?
3. Prove each of the following for integers a,b,c.
   1. if a | b and a | c then a | (b+c).
   2. if a | b then a | bx for all integers x.
   3. if c | a and c | b then c | (ax+by) for all integers x, y.
4. Prove that there are an infinite number of primes of the form 6n+5, where n is a positive integer.(Hint: replace the +1 in Euclid's proof by -1.)
5. Prove that 5 is irrational. (Hint: Compare with the proof that 2 is irrational on page 17 in Chetwynd and Diggle.)