# 6.1: Prime numbers

- Page ID
- 7319

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

Definition

**Prime Numbers** - integers greater than 1 with exactly 2 divisors: 1 and itself.

Let n be a positive integer greater than 1. Then n is called prime number if n has exactly two positive divisors, 1 and n.

**Composite Numbers** - integers greater than 1 which are not prime.

Note that: \(1\) is neither prime nor composite.

Theorem 1:

Let \(n\) be a composite number with exactly \(3\) positive divisors. Then there exists a prime (\(p\)) such that n=p^{2 }.

**Proof:**

Let \(n\) be a positive integer with exactly 3 positive divisors. Then two of the positive divisors are 1 and n.

Let \(d \) be the 3rd positive divisor. Then \(1 < d < n \) and the only positive divisors are \(1 \) and \(n.\)

Therefore \(d\) is prime.

Since \(d \mid n\), \(n=md, m \in\mathbb{Z_+}\).

Since \(m \mid n\) and \(1<m<n, m=d\), n=d^{2}.

Thus, \(d \) is prime. \(\Box\)

Theorem 2:

Every composite number n has a prime divisor less than or equal to the \(\sqrt{n}\). If p is a prime number and \(p \mid n\), then \(1<p \leq √n.\)

Note

There are infinitely many primes,proved by Euclid in 100BC.

Example \(\PageIndex{1}\): Method of Sieve of Eratosthenes

Examples of prime numbers are 2 (this is the only even prime number), 3, 5, 7, 9, 11, 13, 17, \(\ldots\)

Method of Sieve of Eratosthenes:

Example \(\PageIndex{2}\):

Is 225 a prime number?

**Solution:**

The prime numbers < √225 are as follows: 2, 3, 5, 7, 11, and 13. Since 17^{2} is >225.

Since 223 is not divisible by any of the prime numbers identified above, 223 is a prime number.

Prime divisibility Theorem

Let \(p\) be a prime number and let \(a, b\) be integers.

If \(p\mid ab\) then \(p\mid a\) or \(p\mid b\).

Theorem

There are infinitely many primes.

**Fundamental Theorem of Arithmetic (FTA)**

Let \(n \in\mathbb{Z_+}\), then n can be expressed as a product of primes in a unique way. This means n= P_{1}^{n1}_{,}P_{2}^{n2}_{, }...._{,} P_{k} ^{nk}_{ }, where \(P_1 <P_2< ... <P_k\) are primes.

Note: Conjectures

Gildbach's Conjecture(1742)

Every even integer \(n >2\) is the sum of two primes.

Goldbach's Ternary Conjecture:

Every odd integer \(n \geq 5 \) is the sum of at most three primes.