1.3: Primes

Definition:

Prime Numbers - integers greater than \(1\) with exactly \(2\) positive divisors: \(1\) and itself.
Let \(n\) be a positive integer greater than \(1\). Then \(n\) is called a 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.  

There are infinitely many primes, which was 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:

The following will provide us a way to decide 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\) be 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. If \(p \mid ab, a,b \in \mathbb{Z}, \) then \(p\mid a\) or \(p\mid b\).

Proof

Let \(p\) be a prime number and let \(a,b \in \mathbb{Z}.\)  Assume that \(p \mid ab\). If \(p\mid a\), we are done. So we suppose that \(p\) does not divide \(a\). Thus \(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 there are finitely many primes \(p_1, p_2, ...,p_n\), where \(n\) is a positive integer. Consider the integer \(Q\) such that

\[Q=p_1p_2...p_n+1.\]

Notice that \(Q\) is not prime. Hence \(Q\) has at least a prime divisor, say \(q\). If we prove that \(q\) is not one of the primes listed then we obtain a contradiction. Suppose now that \(q=p_i\) for \(1\leq i\leq n\). Thus \(q\) divides \(p_1p_2...p_n\) and as a result \(q\) divides \(Q-p_1p_2...p_n\). Therefore \(q\) divides 1. But this is impossible since there is no prime that divides 1 and as a result \(q\) is not one of the primes listed.

The following theorem explains the gaps between prime numbers:

Theorem \(\PageIndex{5}\)

Let \(n\) be an integer. Then there exists \(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 without a prime number among them?

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)

Let \(n \in\mathbb{Z_+}\), then n can be expressed as a product of primes in a unique way. This means

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

Neither the fundamental theorem nor the proof shows us how to find the prime factors. We can use tests for divisibility 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).

 

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

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