Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 44 views

    Introduction To Number Theory MATH3304, Prime Factorization: Ben Kane, Jincheng Tang

    Uploaded by

    acdb
    This document is a lecture on prime factorization from a course on number theory taught by Ben Kane and Jincheng Tang at the University of Hong Kong. It introduces prime numbers and states Theorem 3.5, which says that every natural number greater than 1 can be written as a finite product of prime numbers. It then provides a proof of this theorem by induction.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Introduction To Number Theory MATH3304, Prime Factorization: Ben Kane, Jincheng Tang

    Uploaded by

    acdb
    44 views18 pages
    This document is a lecture on prime factorization from a course on number theory taught by Ben Kane and Jincheng Tang at the University of Hong Kong. It introduces prime numbers and states Theorem 3.5, which says that every natural number greater than 1 can be written as a finite product of prime numbers. It then provides a proof of this theorem by induction.

    Original Description:

    Original Title

    MATH3304-PrimeFactor-2021

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is a lecture on prime factorization from a course on number theory taught by Ben Kane and Jincheng Tang at the University of Hong Kong. It introduces prime numbers and states Theorem 3.5, which says that every natural number greater than 1 can be written as a finite product of prime numbers. It then provides a proof of this theorem by induction.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    44 views18 pages

    Introduction To Number Theory MATH3304, Prime Factorization: Ben Kane, Jincheng Tang

    Uploaded by

    acdb
    This document is a lecture on prime factorization from a course on number theory taught by Ben Kane and Jincheng Tang at the University of Hong Kong. It introduces prime numbers and states Theorem 3.5, which says that every natural number greater than 1 can be written as a finite product of prime numbers. It then provides a proof of this theorem by induction.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 18

    Introduction to Number Theory MATH3304,

    Prime Factorization

    Ben Kane, Jincheng Tang

    The University of Hong Kong

    January 18–21, 2021

    B. Kane, J. Tang MATH3304, Prime Factorization


    Prime Numbers

    I Every integer n has divisors 1 and n.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Prime Numbers

    I Every integer n has divisors 1 and n.

    I Only divisors are 1 and n > 1: call n prime.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Prime Numbers

    I Every integer n has divisors 1 and n.

    I Only divisors are 1 and n > 1: call n prime.

    I Omit n = 1.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Prime Numbers

    I Every integer n has divisors 1 and n.

    I Only divisors are 1 and n > 1: call n prime.

    I Omit n = 1.

    I Usually denote primes by p.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Theorem 3.5

    Theorem (Theorem 3.5)


    Every natural number n > 1 can be represented as a product of
    finitely many primes.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Theorem 3.5

    Theorem (Theorem 3.5)


    Every natural number n > 1 can be represented as a product of
    finitely many primes.

    Remark: later see prime factorization is unique.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done. Otherwise,

    n = m1 m2

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done. Otherwise,

    n = m1 m2

    with 2 ≤ m1 < n and 2 ≤ m2 < n.

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done. Otherwise,

    n = m1 m2

    with 2 ≤ m1 < n and 2 ≤ m2 < n. Induction:

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done. Otherwise,

    n = m1 m2

    with 2 ≤ m1 < n and 2 ≤ m2 < n. Induction:


    `1
    Y
    m1 = pj,1 ,
    j=1

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done. Otherwise,

    n = m1 m2

    with 2 ≤ m1 < n and 2 ≤ m2 < n. Induction:


    `1
    Y `2
    Y
    m1 = pj,1 , m2 = pj,2 ,
    j=1 j=1

    B. Kane, J. Tang MATH3304, Prime Factorization


    Proof of Theorem 3.5

    Proof by induction.
    Base case: n = 2 prime (Thm. 3.4 (9): d | 2 =⇒ |d| ≤ 2)
    Suppose n > 2 and claim holds for 2 ≤ m < n.
    If n prime: done. Otherwise,

    n = m1 m2

    with 2 ≤ m1 < n and 2 ≤ m2 < n. Induction:


    `1
    Y `2
    Y
    m1 = pj,1 , m2 = pj,2 ,
    j=1 j=1
    `1
    Y `2
    Y
    =⇒ n = pj,1 pj,2 .
    j=1 j=1

    B. Kane, J. Tang MATH3304, Prime Factorization

    You might also like