1.4: Primes, Prime factorization, GCD and LCM

Definition:

Prime number: An integer \(p>1\) is prime if its only positive divisors are \(1\) and \(p\).

Composite number: An integer \(n>1\) is composite if there exist integers \(a,b\) such that

\( n=ab,\qquad 1<a<n,\quad1<b<n. \)

The integer \(1\) is neither prime nor composite.

The integer \(2\) is the only even prime number.

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

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

Method of Sieve of Eratosthenes:

 Instructions: cross out multiples of each prime, starting at \(2\),

The following will provide a way to determine whether a given number is prime. 

Theorem \(\PageIndex{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 third positive divisor. Then \(1 < d < n \) and the only positive divisors of \(d\) are \(1 \) and \(d.\)
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 \(\PageIndex{2}\)

Let \(n>1\) be an integer. If \(n\) is composite, then there exists a prime \(p\) such that

\( p\mid n \qquad\text{and}\qquad p\leq\sqrt n. \)

Equivalently, if no prime \(p\leq\sqrt n\) divides \(n\), then \(n\) is prime.

Proof

Let \(n>1\) be an integer.  Suppose \(n \) is composite. Then \( n=ab \) for some integers \(a,b\) with \(1<a<n\) and \(1<b<n\).

At least one of \(a,b\) is at most \(\sqrt n\), because if both exceeded \(\sqrt n\), then

\( ab>\sqrt n\sqrt n=n, \) a contradiction.

Without loss of generality, suppose \(a\leq\sqrt n\).

Since \(a>1\), it has a prime divisor \(p\). Therefore,

\( p\leq a\leq\sqrt n. \)

Since \(p\mid a\) and \(a\mid n\), we have \(p\mid n\).

Example \(\PageIndex{2}\):

Is \(223\) a prime number?

Solution:

The prime numbers \(< \sqrt{223}\) are as follows: \(2, 3, 5, 7, 11,\) and \(13\). Note that \( 17^2 >223.\)

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

Exercise \(\PageIndex{3}\)

Is \(2011\) a prime number?

Answer

The prime numbers \(< \sqrt{2011}\) are as follows: 

\[ 2,3,5,7,11,13,17,19,23,29,31,37,41,43. \]

Since \(\sqrt{2011}<45\) and none divides \(2011\), the number is prime.

Theorem \(\PageIndex{3}\): Prime divisibility theorem (Euclid'd Lemma) 

Let \(p\) be a prime number and let  \(a,b \in \mathbb{Z}\). If \(p \mid ab, \) then \(p\mid a\) or \(p\mid b\).

Proof

Let \(p\) be a prime number and let \(a,b \in \mathbb{Z}\) such that \(p \mid ab\). If \(p\mid a\), we are done. So we suppose that \(p\) does not divide \(a\). Since \(p\) is prime, \(gcd(a,p)=1.\) Thus there exists \(u,v \in \mathbb{Z}\) such that \(1=au+pv\). Hence \(b=abu+pbv\). Since \(p \mid ab\), \(ab=pm, m\in \mathbb{Z}.\) Thus \(b=pmu+pbv=p(mx+by).\) Hence, \(p\mid b.\)

Example \(\PageIndex{4}\)

The following example demonstrates why the hypothesis that \(p\) is prime is essential. For instance,

\( 6\mid(2)(3), \)

but

\( 6\nmid2,\qquad6\nmid3. \)

 

Theorem \(\PageIndex{4}\)

Let \(p\) be a prime number and let  \(a_1, a_2, \cdots, a_k \in \mathbb{Z}\). If \(p\) is prime and

\( p\mid a_1a_2\cdots a_k, \) then \(p\mid a_i\) for at least one index \(i =1, \cdots, n\).

 

Theorem \(\PageIndex{5}\)

There are infinitely many primes.

Proof

Proof by contradiction. 

Suppose the complete list of primes is
\(
p_1,p_2,\ldots,p_n.
\)

Define
\(
Q=p_1p_2\cdots p_n+1.
\)

Since \(Q>1\), it has some prime divisor \(q\).

For every \(i\),
\(
Q\equiv1\pmod{p_i}.
\)

Therefore,
\(
p_i\nmid Q.
\)

Thus \(q\) is not among
\(
p_1,\ldots,p_n,
\)
which is a contradiction.

 

The following theorem explains the gaps between prime numbers:

Theorem \(\PageIndex{6}\)

Let \(n\) be a positive integer. Then there exist \(n\) consecutive composite integers.

Proof

Let \(n\) be an integer. Consider the sequence of integers \[(n+1)!+2, (n+1)!+3,...,(n+1)!+n, (n+1)!+(n+1)\]

This sequence contains exactly \(n\) consecutive composite integers.

Notice that every integer in the above sequence is composite because \(k\) divides \((n+1)!+k\) if \(2\leq k\leq (n+1)\). 

For \(2\leq k\leq n+1\),

\[ (n+1)!+k=k\left(\frac{(n+1)!}{k}+1\right). \]

Both factors exceed \(1\), so the number is composite.

Example \(\PageIndex{4}\):

Does there exist a block of \(1000000\) consecutive integers that contains no prime numbers?

Solution

Use \(1000001!\) and consider \(1000001! +2 , \ldots, 1000001!+1000001\)

Example \(\PageIndex{5}\):

Consider the formula \(y=x^2+x+13\). Then

1. Find the values \(y\) for \( x=1, \cdots, 12\). How many of these values are prime?

2. Can we conclude that this formula always generates a prime number?

Answer

\(x\)	\(f(x)\)	Prime?
1	15	No
2	19	Yes
3	25	No
4	33	No
5	43	Yes
6	55	No
7	69	No
8	85	No
9	103	Yes
10	123	No
11	145	No
12	169	No

RESULT out of \(12\), Only \(19\), \(43\), and \(103\) are prime.

In fact, the formula does not always produce prime numbers, as \(f(1)=15\) immediately shows.

There is also a stronger structural observation:

\[ f(13)=13^2+13+13=13(15), \]

which is composite.

More generally, whenever \(x\) is a positive multiple of \(13\), the resulting value is divisible by \(13\) and is greater than \(13\).

Definition: Twin primes

Two prime numbers are called twin primes if they differ by \(2\).

• \((3,5)\), \((5,7)\), and \((11,13)\) are twin-prime pairs.

• It remains unknown whether infinitely many twin-prime pairs exist.

Theorem \(\PageIndex{7}\) Fundamental Theorem of Arithmetic (FTA)

Every integer \(n>1\) has a unique prime factorization, up to the order of the factors. Equivalently,

For each integer \(n>1\), there exist distinct primes

\( p_1<p_2<\cdots<p_r \)

and positive integers \(\alpha_1,\ldots,\alpha_r\) such that

\( n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}. \)

This expression is unique.

Proof

Use strong induction on \(n\).

For \(n=2\), the result holds because \(2\) is prime.

Suppose every integer \(m\) with \(2\leq m<n\) can be expressed as a product of primes.

If \(n\) is prime, it is already a product of primes.

Otherwise, \(n=ab\), where

\[ 1<a<n,\qquad1<b<n. \]

By the induction hypothesis, both \(a\) and \(b\) are products of primes. Hence so is \(n\).

Proof of uniqueness

Suppose

\[ n=p_1p_2\cdots p_r=q_1q_2\cdots q_s, \]

where every \(p_i\) and \(q_j\) is prime.

Since \(p_1\mid q_1q_2\cdots q_s\), Euclid's lemma implies that \(p_1\mid q_j\) for some \(j\).

As \(q_j\) is prime,

\[ p_1=q_j. \]

Cancel this common prime factor from the two integer products.

Repeating the process matches every prime factor, including repetitions. Thus the prime factorizations agree up to rearrangement.

This proves uniqueness.

Neither the fundamental theorem nor the proof shows us how to find the prime factors. We can use divisibility tests to find prime factors whenever possible.

Example \(\PageIndex{6}\):

Find the prime factorization of

1. \(252\)

2.\(2018\).

3. \(1000\)

Solution

1. Using divisibility tests, we can find that \(252= 2^2 3^2 7\)

 

2. We can see that \(2018\) is divisible by 2, and \(2018= 2 \times 1009\). \(1009 \) is prime (why?).

Answer

Since \( \sqrt{1009}<32, \) it is sufficient to check primes up to \(31\). None divides \(1009\).

3. \(1000=10^3=((2)(5))^3=2^3 5^3\)

Example \(\PageIndex{7}\):

Find the prime factorization of \(1000001\).

Solution

Consider \(1000001=1000000+1= 10^6+1=(10^2)^3+1^3= (10^2+1^2) (10^4-10^2+1^2)= 101 \times 9901 \). \(101\) and \(9901\) are prime (why?)

Example \(\PageIndex{8}\)

Determine \( gcd( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)\) and \(lcm( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)\).

Solution

\( gcd( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)= 2^4 \times 3^8\) (the lowest powers of all prime factors that appear in both factorizations) and \(lcm( 2^6 \times 3^9, 2^4 \times 3^8 \times 5^2)= 2^6 \times 3^9 \times 5^2\) (the largest powers of each prime factors that appear in factorizations).

For \(a,b>0\) with prime factorizations, the GCD uses minimum exponents; the LCM uses maximum exponents.

If

\( a=\prod_i p_i^{\alpha_i}, \qquad b=\prod_i p_i^{\beta_i}, \)

where missing prime factors are assigned exponent \(0\), then

\(\boxed{ \gcd(a,b)=\prod_i p_i^{\min(\alpha_i,\beta_i)} } \)

and

\( \boxed{ \operatorname{lcm}(a,b)= \prod_i p_i^{\max(\alpha_i,\beta_i)}. } \)

\( \boxed{\gcd(a,b)\operatorname{lcm}(a,b)=ab} \) for positive integers \(a,b\).

Note: Conjectures

Goldbach's Conjecture(1742) (unproved)

The strong, or binary, Goldbach conjecture states that every even integer greater than \(2\) is the sum of two primes. It remains unproved.

Goldbach's Ternary Theorem: (proved)

 Every odd integer greater than \(5\) is the sum of three primes. This was proved by Harald Helfgott in 2013.   

 Wilson's Theorem

Theorem \(\PageIndex{8}\)

Let \(p\) be a prime number. Then \((p - 1)! + 1\) is divisible by \(p\).

Proof:

Let \(p\) be a prime number. First consider \(p=2\). Then

\( (p-1)!=1\equiv-1\pmod2, \)

so the result holds.

Now suppose \(p\) is an odd prime.

Every nonzero residue modulo \(p\) has a unique multiplicative inverse.

An element \(a\) is its own inverse precisely when \( a^2\equiv1\pmod p. \)

Equivalently, \( (a-1)(a+1)\equiv0\pmod p. \)

Since \(p\) is prime, Euclid's lemma gives

\( a\equiv1\pmod p \quad\text{or}\quad a\equiv-1\pmod p. \)

Thus the only self-inverse residues are \(1\) and \(p-1\).

Every other residue can be paired with a distinct multiplicative inverse. Each such pair has product congruent to \(1\)modulo \(p\).

Therefore,

\( \begin{aligned} (p-1)! &\equiv1\cdot(p-1)\cdot \prod_{\text{other inverse pairs}}(aa^{-1})\\ &\equiv1\cdot(-1)\cdot1\\ &\equiv-1\pmod p. \end{aligned} \)

This proves Wilson's theorem.

The converse is also true:

Theorem \(\PageIndex{9}\)

For an integer \(n>1\),

\(\boxed{ n\text{ is prime} \iff (n-1)!\equiv-1\pmod n. } \)

Fermat's Little Theorem

Theorem \(\PageIndex{10}\)

 For any prime number \( p \) and an integer \( a \) such that \( p \) does not divide \( a \), we have \( a^{p-1} \equiv 1 \pmod{p} \). 

Also, \(\boxed{a^p\equiv a\pmod p} \).

Proof

Consider the nonzero residue classes

\( 1,2,\ldots,p-1. \)

Because \(\gcd(a,p)=1\), multiplication by \(a\) permutes these classes modulo \(p\).

Hence,

\( a\cdot2a\cdots(p-1)a \equiv1\cdot2\cdots(p-1)\pmod p. \)

Thus

\[(a^{p-1}(p-1)!\equiv(p-1)!\pmod p. \)

Since \(p\nmid(p-1)!\), cancellation is valid, giving

\(\boxed{a^{p-1}\equiv1\pmod p.} \) \(\square\)

If \(n\) is prime, then by Fermat's little theorem, \(a^{(n-1)}\equiv 1\pmod \, n),\) for all integers \(a\) that are relatively prime to \(n.\) Thus,  if \(gcd(a,n)=1\) and \(n\) is prime then \(a^{-1}\equiv a^{(n-2)} \pmod  n).\) That is 

\(\boxed{a^{-1}\equiv a^{p-2}\pmod p} \)

provided \(p\nmid a\).

Example \(\PageIndex{9}\)

In modulo \(7\),

\( 3^{-1}\equiv3^5\equiv5\pmod7. \)

Indeed, \(3(5)=15\equiv1\pmod7\).

Definition: Euler totient function

For every positive integer \(n\), Euler's totient function \(\varphi(n)\) is the number of integers \(k\) satisfying

\[ 1\leq k\leq n, \qquad \gcd(k,n)=1. \]

Euler's Theorem

Theorem \(\PageIndex{10}\)

Let \(n\geq2\) and \(a\in\mathbb Z\). If \(\gcd(a,n)=1\), then

\(\boxed{a^{\varphi(n)}\equiv1\pmod n.} \)

Proof

Let \(r_1,\ldots,r_{\varphi(n)}\) represent the invertible residue classes modulo \(n\).

Since \(\gcd(a,n)=1\), multiplication by \(a\) permutes these classes.

Therefore,

\[ (ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n. \]

Because every \(r_i\) has a multiplicative inverse modulo \(n\), we may cancel their product and obtain

\[ a^{\varphi(n)}\equiv1\pmod n. \]

The following results will help us find Euler's totient function \(\phi(n)\) for \(n\in \mathbb{N}\).

Theorem \(\PageIndex{11}\)

1.  If \(p\) is prime then \(\phi(p)=p-1.\)

2. If \(p\) is prime and \(k\) is a positive integer then \(\phi(p^k)=p^k-p^{k-1}.\)

3. If \(m\) and \(n\) are relatively prime, then \(\phi(mn)=\phi(m)\phi(n).\)

4. \[ \phi(n) = n \times \prod_{p|n} \left(1 - \frac{1}{p}\right) \] where the product is taken over distinct prime factors \(p\) of \(n.\)

 

Example \(\PageIndex{10}\)

Find \(\phi(252)\).

Solution

Since \(252= 2^2 3^2 7\), \(\phi(252)=(2^2-2)(3^2-3)(7-1)=72\).