1.4: Primes, Prime factorization, GCD and LCM

Definition:

An integer \(p>1\) is prime if its only positive divisors are \(1 \) and \(p\). An integer \(n>1\) that is not prime is composite. Neither \(1\) nor negative integers are prime under this convention. 

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:

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}\)

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

Proof

Suppose \(p\) is the smallest prime divisor of \(n\). Then there exists an integer \(m\) such that \(n=pm\). Assume that \(p > \sqrt{n}\). Then \(m < \sqrt{n}.\)

Let \( q\) be any prime divisor of \(m\). Then \( q \) is also a prime divisor of \(n\) and \( q < m < \sqrt{n} < p.\) This is a contradiction.

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

yes.

Theorem \(\PageIndex{3}\): Prime divisibility theorem

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 \(x,y \in \mathbb{Z}\) such that \(1=ax+py\). Hence \(b=abx+pby\). Since \(p \mid ab\), \(ab=pm, m\in \mathbb{Z}.\) Thus \(b=pmx+pby=p(mx+by).\) Hence, \(p\mid b.\)

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{5}\)

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)\]

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

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?

Definition: Twin primes

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

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

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

\(n=p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k}\), where \(p_1 <p_2< ... <p_k\) are primes and  positive integers \(n_1, \cdots, n_k\).

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?).

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.

Note: Conjectures

Goldbach'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.

 Wilson's Theorem

Theorem \(\PageIndex{7}\)

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

Proof:

Consider the product \(P = 1 \cdot 2 \cdot 3 \cdots (p-1)\). Now, let's pair each number \(k\) from \(1\) to \(p-1\) with its modular inverse \(k^{-1}\) modulo \(p\). 

We know that for every \(k\) such that \(1 \leq k \leq p-1\), there exists a unique \(k^{-1}\) such that \(kk^{-1} \equiv 1 \pmod{p}\). Moreover, these pairs will be distinct because if \(kk^{-1} \equiv 1 \pmod{p}\) and \(jj^{-1} \equiv 1 \pmod{p}\) for \(k \neq j\), then \(k = kj^{-1}\) and \(j = jk^{-1}\), implying \(k = j\), which contradicts the distinctness of the pairs. 

Thus, we can pair each \(k\) with \(k^{-1}\) such that the product of these pairs is congruent to \(1 \pmod{p}\). Therefore, \(P \equiv (p-1)! \equiv -1 \pmod{p}\). Adding \(1\) to both sides gives \((p-1)! + 1 \equiv 0 \pmod{p}\), which means \((p-1)! + 1\) is divisible by \(p\).

Fermat's Little Theorem

Theorem \(\PageIndex{8}\)

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

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),\)

 

Euler's Theorem

Theorem \(\PageIndex{9}\)

If \(a\) and \(n\) are relatively prime (i.e., \(\gcd(a, n) = 1\)), then \[ a^{\phi(n)} \equiv 1 \pmod{n} \]

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

Theorem \(\PageIndex{10}\)

 

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{9}\)

Find \(\phi(252)\).

Solution

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