$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.1 Prime numbers

[ "article:topic", "authorname:thangarajahp", "Prime numbers", "Composite Numbers", "prime factorization tree", "Fundamental Theorem of Arithmetic", "license:ccbyncsa", "showtoc:yes" ]

$$\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

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}$$:

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.

Example $$\PageIndex{3}$$:

Fundamental Theorem of Arithmetic expressed through a prime factorization tree:

272
/    \
2   136
/   \
2    68
/   \
2     34
/   \
2     17

Thus, 272= (24)(17).

Example $$\PageIndex{4}$$: Using prime factorization to determine  GCD and LCM.

Determine the GCD and LCM of 2420 and 230.

Solution:
First determine the prime products of each number individually.
2420
/       \
2      1210
/      \
2      605
/      \
5      121
/     \
11       11
Thus, 2420 = (2²)(5)(11²).

230
/    \
2   115
/     \
5      23
Thus, 230 = (2)(5)(23).

The GCD of 2420 and 230 is (2)(5).  This is because they are the only 2 commonalities between the two numbers.

The LCM of 2420 and 230 is: = ((2²)(5)(11²))((2)(5)(23)) / (2)(5)
= 556,600/10
= 55,660.

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.