
# 6.1: Prime numbers

$$\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=p2 .

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=d2.
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 172 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= P1n1,P2n2, ...., Pk 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.