MthT 491 Divisibility and Prime Numbers

Definition. An integer p > 1 is called a prime number, or a prime, if there is no divisor d of p satisfying 1 < d < p. If an integer p > 1 is not a prime, it is called a composite number.

N.B. We don't call 1, 0, or negative integers either prime or composite .

Equivalent definition?

Definition. A positive integer p ≠ 1 is called a prime number, or a prime, if there is no positive divisor d of p satisfying d ≠ 1,p. If a positive integer p ≠ 1 is not a prime, it is called a composite number.

Our first result is the easy version of the Fundamental Theorem of Arithmetic .

Theorem. [N-Z](1.14). Every integer n > 1 can be expressed as a product of primes (with perhaps only one factor).

Proof. Let's try a proof by contradiction. Suppose there is an integer n > 1 which cannot expressed as a product of primes. By the WOP, there is a smallest n, call it n₀ which cannot expressed as a product of primes. We know that n₀ > 1 and that n₀ is not a prime. But then n₀ = n₁ n₂, 1 < n₁, n₂ < n₀. But then both n₁ and n₂ can be expressed as a product of primes. This is a contradiction since we now have both

A ≡ n0 cannot be expressed as a product of primes

¬A ≡ n0 can be expressed as a product of primes

are true.

For integers n > 1, the factorization into primes is unique. This is the Fundamental Theorem of Arithmetic .

Theorem. [N-Z], Theorem 1.15. If p |a b, p being a prime, then p |a or p |b.

Proof. (not intuitive without buildup!) Let k be an integer such that a b = p k. If p does not divide a, then gcd(p,a) = 1. (The gcd must be either p or 1). For some integers x,y, 1 = px + ay and b = pbx + bay = pbx + pky = p( b x + k y). Thus p |b.

Theorem. The factoring of any integer n > 1 into primes is unique apart from the order of the prime factors.

Proof. Another proof by contradiction!. If the Theorem is not true, there is a smallest integer n for which the factorization is not unique. Dividing out any common factors, we have

n = p1 p2 …pr = q1 q2 …qs.

Without loss of generality, p₁ < q₁. Let

N = (q1 − p1) q2 …qr = N − p1 q2 …qs = p1 (p2 …pr − q2 …qs).

But p₁ does not divide (q₁ − p₁) (Why?). We have 0 < N < n, and N has two distinct factorings, on involving p₁, and the other without p₁.

Weird Examples of Non-Unique Prime Factorization

1.

Let E consist of even integers of the form 2 k, k = 0, ±1, ±2, ….

E = { 0, ±2 , ±4, …}.

Usual multiplication and addition is well defined. Working very carefully, the primes are those numbers p = 2·odd > 1 and the composite numbers are n = 2·even > 1 . So

primes = {2, 6, 10, 14, …}, composites = {4, 8, 12, …}.

Prime factoring is not unique since 60 = 2 ·30 = 6 ·10 has (at least) two factorings into primes.

2.

Let W consist of all integers of the form 4 k + 1, k = 0, ±1, ±2, ….

W = { …, −7 , −3, 1, 5, 9, 13, …}.

Usual multiplication works, in the sense that the product of two numbers in W remains in W. Addition does not work within the class. Working very carefully, the primes are those numbers p = 4k + 1 > 1 which have no factors (divisors!) of the form 4 j + 1 except for p and 1. Thus 1, 5, 9, 13, 17, 21, 29, 33, 37, 41, 49 are primes , but 25 = 5 ·5, 45 = 5 ·9 are not a prime in this context. We have two prime factorizations for (21)² = 441;

(21)2 = 21 ·21 = (3 ·7) ·(3 ·7) = (3 ·3)·(7 ·7) = 9 ·49.

Show that 33² has two prime factorizations in this context.

---

File translated from T_EX by T_TH, version 4.06.
On 25 Apr 2015, 18:11.