Skip to main content
\(\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}}\)
Mathematics LibreTexts

6.1: Prime numbers

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)


    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


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


    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?


    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.

    Exercise \(\PageIndex{1}\)

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


    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.