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
    7319
  • [ "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:

    eratosthenes-sieve-2.png

    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.