Introduction to Number Theory Concepts

◼
  • This topic will center around properties of  and  with a couple of guest appearances of elements of  and 

    • Divisibility

    Definition

    ◼
  • Let
    a,b∈
    we say that
    a
    divides
    b
    if there is c∈ such that
    ac=b
    . We usually denote it by
    ab
    and read it as “
    a
    divides
    b
    ”. We sometimes write
    ab
    to denote that
    a
    does not divide b.
    • ◼
  • Examples:
    • ◼
  • 2|4
    • ◼
  • 5|25
    • ◼
  • 3|12
    • ◼
  • 1021
    • ◼
  • For integers
    a
    ,
    b
    . If
    ab
    and
    a
    is non zero then there is a unique number c such that
    ac=b
    .
    • ◼
  • If
    a
    divides
    b
    , then b is a multiple of
    a
    and furthermore if
    b≠0
    , we say that
    a
    is a divisor of
    b
    .
    • ◼
  • If
    a
    divides
    b
    and
    a≠0
    , then the remainder upon dividing
    b
    by
    a
    is zero
    • ◼
  • From now on, since it is common that we consider non-zero integers or natural numbers, we will use the notation
    *
    
    to denote the set \{0} and
    *
    
    =\{0}
    .
    • ◼
  • If
    n|a
    and
    n|b
    , then
    n|a±b
    • ◼
  • Proof: Assume
    n|a
    and
    n|b
    ​
    There is k∈ such that
    a=nk
    and there is j∈ such that
    b=nj
    .
    ​
    a+b=nk+nj=n(k+j)
    . Note that k+j is an integer
    So
    n|a+b.
    • ◼
  • If
    n|a
    then
    n|ac
    for all c ∈
    • ◼
  • Proof: Assume
    n|a
    then there is k such that
    nk=a
    so
    ac=nkc
    so
    n|ac

    • Parity

    ◼
  • A special case of divisibility is considered when evaluating divisibility of a number by 2. If a number is divisible by 2 we say that it is even if it is not divisible by 2, then we say that it is odd.
    • ◼
  • If two integers are both odd or they are both even, we say that they have the same parity.
    • ◼
  • Notethattherelation
    having the same [arity is an equivalence relation
    • ◼
  • a number has the same parity as itself
    • ◼
  • if x has the same parity as y then y has the same parity as x
    • ◼
  • If x has the same parity as y, and y has the same parity as z, thus x and z have the same parity.

    • The floor function

    ◼
  • ⌊⌋: ⟶, where ⌊x⌋is the largest integer less than or equal to x. This is called the floor function.
    • ◼
  • Examples:
    • ◼
  • ⌊k⌋= k for all k∈
    • ◼
  • ⌊0.5⌋ = 0
    • ◼
  • ⌊-0.5⌋ = -1
    • ◼
  • ⌊π⌋=3
    • ◼
  • ⌊0.9⌋=0
    • ◼
  • The floor function is not injective but it is surjective Note that both 0 and
    1
    2
    are such that their image is 0 (⌊0⌋=
    1
    2
    = 0). Let
    k∈
    . Then
    ⌊k⌋=k
    .
    • Out[]=

    The absolute value function

    ◼
  • Let x∈ we say that the absolute value of x is x if x is non-negative, or -x if x is negative.
    • ◼
  • We denote the absolute value of x by |x|
    • ◼
  • The following is a graph plot of the absolute value function for x between -5 and 5.
    • Out[]=
    ◼
  • It is easy to note that if
    a
    and
    b
    are integers and
    a
    divides
    b
    , then
    |a|<=|b|
    • ◼
  • This follows from the fact that the absolute value is multiplicative. (i.e
    |ab|=|a||b|
    )

    • The division algorithm

    ◼
  • Let
    a∈
    and
    b∈
    then there exists unique integers
    q,r∈
    with
    0≤r<b
    such that
    a=bq+r
    .
    • ◼
  • The above is such an important result that it deserves a formal proof. As with any existence and uniqueness theorems there are two things to prove:
    • ◼
  • Existence: Define q =
    a
    b
    . And let
    r=a-bq∈
    . It then remains to show that
    0<=r<a
    . Since
    q<=
    a
    b
    we then have that
    bq<=b
    a
    b
    =a
    . So
    0<=r
    .Note that
    a=b
    a
    b
    -1+b
    ​​
    b
    a
    b
    -1+b<b
    a
    b
    +b=bq+b
    , so
    r=b-aq<b
    .
    • ◼
  • Uniqueness: Assume
    a=bq+r
    and
    a=bs+t
    . with q,r,s,t∈ and 0≤r < b and 0≤ t< b.
    Without loss of generality r≥t. So (s-q)b = r-t so b|r-t, hence r=t and thus q = s.

    • Greatest Common Divisor and Least Common Multiple

    ◼
  • Let
    a,b,c∈
    *
    
    . If
    ca
    and
    cb
    we say that
    c
    is a common divisor of
    a
    and
    b
    .
    • ◼
  • Common divisors always exist because 1 is always a divisor of any Integer.
    • ◼
  • The largest of these common divisors is called the greatest common divisor. We usually denote the greatest common divisor of
    a
    and
    b
    as
    GCD(a,b)
    • ◼
  • Examples:
    • ◼
  • GCD(6,4)=2
    • ◼
  • GCD(16,8)=8
    • ◼
  • GCD(6,9)=3
    • ◼
  • GCD(10,9)=1
    • ◼
  • If
    m|n
    then
    GCD(m,n)=m
    • ◼
  • If
    n|ab
    , then
    n
    GCD(n,a)
    b
    • ◼
  • Examples:
    • ◼
  • 4|12
    4|62
    take a = 6, n = 4 and b = 2 then we get that 2|2
    • ◼
  • 4|12
    4|34
    take a = 3, n = 4, and b = 4 then we get that 4|4
    • ◼
  • If a number
    c
    is a multiple of both
    a
    , and
    b
    we say that it is a common multiple of
    a
    and
    b
    .
    • ◼
  • The least positive number that is a common multiple of both
    a
    and
    b
    is called the least common multiple. We usually denote it as
    LCM(a,b)
    • ◼
  • Examples:
    • ◼
  • LCM(2,3)=6
    • ◼
  • LCM(6,10)=30
    • ◼
  • LCM(9,10)=90
    • ◼
  • LCM(4,5)=20
    • ◼
  • LCM(6,8)=24

    • Relatively Prime Numbers

    ◼
  • We say that two numbers are relatively prime if their greatest common divisor is 1. We sometimes also use the name coprime
    • ◼
  • Examples of relatively prime pairs are:
    • ◼
  • 2,3
    • ◼
  • 4,5
    • ◼
  • 9,10
    • ◼
  • 121,36
    • ◼
  • Note that it seems as though if
    aand
    b
    are relatively prime, then their least common multiple is the product
    ab
    . This is in fact true, but we have a more powerful statement.
    • ◼
  • The product of two numbers is the same as the product of their greatest common divisor and their least common multiple. In other words: Let
    a,b
    be positive integers, then
    ab=GCD(a,b)LCM(a,b)
    .
    • ◼
  • Examples:
    • ◼
  • 610=230
    • ◼
  • 68=224

    • The Euclidean Algorithm

    ◼
  • The euclidean algorithm is a procedure to obtain the greatest common divisor of two integer numbers. It consists of repeatedly applying the division algorithm until you obtain a remainder of 0,
    • ◼
  • Let
    a,b∈
    . We apply the division algorithm to
    a
    and b to get
    ​
    a=b
    q
    1
    +
    r
    1
    with
    0<=
    r
    1
    <b
    ​
    b =
    r
    1
    q
    2
    +
    r
    2
    with
    0<=
    r
    2
    <
    r
    1
    ​
    ​
    r
    1
    =
    r
    2
    q
    3
    +
    r
    3
    with
    0<=
    r
    3
    <
    r
    2
    ​
    ...
    ​
    r
    n-2
    =
    r
    n-1
    q
    n
    +
    r
    n
    with
    0<=
    r
    n
    <
    r
    n-1
    ​
    ​
    r
    n-1
    =
    r
    n
    q
    n+1
    ​
    ​
    Then we have that
    r
    n
    is the greatest common divisor of
    a
    and b
    • ◼
  • Proof:
    • ◼
  • We show that
    GCD(a,b)=GCD(b,
    r
    1
    )
    • ◼
  • We check this by showing that the set of common divisors of (a,b) is the same as the set of common divisors of b and
    r
    1
    .
    • ◼
  • Let d be a common divisor of a and b. so
    d|a-b
    q
    1
    that is
    d|
    r
    1
    so d is a common divisor of b and
    r
    1
    • ◼
  • Now let f be a divisor of b and
    r
    1
    . So
    f|b
    q
    1
    +
    r
    1
    . That is, f|a. Thus f is a common divisor of a and b.
    • ◼
  • A similar argument shows that
    GCD(
    r
    i
    ,
    r
    i+1
    )=GCD(
    r
    i+1
    ,
    r
    i+2
    )
    for
    i∈{1,2,...,n-2}
    .
    • ◼
  • Thus
    GCD(
    r
    n-1
    ,
    r
    n
    )=GCD(a,b)
    .
    • ◼
  • Now note that
    GCD(
    r
    n-1
    ,
    r
    n
    )=
    r
    n
    since
    r
    n
    |
    r
    n-1
    .
    • ◼
  • Ergo
    GCD(a,b)=
    r
    n
    ​
    ​
    • ◼
  • Examples:
    • ◼
  • a = 5 b = 2
    ​
    5=22+1
    ​
    ​
    2=12
    ​
    So 1 is GCD(5,2)
    • ◼
  • a=12 b=8
    ​
    12=81+4
    ​
    ​
    8=42
    ​
    So 4 is GCD(12,8)
    • ◼
  • a = 9 b = 121
    ​
    9=1210+9
    ​
    ​
    121=913+4
    ​
    ​
    9=42+1
    ​
    ​
    4=14
    ​
    So GCD(9,121) = 1

    • The Well Ordering Principle

    ◼
  • Every nonempty subset of the Natural numbers has a least element.

    • Prime Numbers

    ◼
  • A prime number is an integer p that has exactly 4 divisors, namely {1,-1,p,-p}.
    • ◼
  • Note that 1, and -1 are not considered prime numbers.
    • ◼
  • The first ten positive primes are 2,3,5,7,11,13,17,19,23,29
    • ◼
  • Prime Number Factorization: Every natural number greater than 1 can be factored as a product of prime numbers. Moreover the prime factorization is unique modulo the order of the factors (i.e. if the order they appear in is ignored).
    • ◼
  • Examples:
    • ◼
  • 10 = 2x5
    • ◼
  • 12 = 2x2x3
    • ◼
  • 27 = 3x3x3
    • ◼
  • 121 = 11x11
    • ◼
  • 70 = 2x5x7
    • ◼
  • 36 = 2x2x3x3
    • ◼
  • 11 = 11
    • ◼
  • Proof: Assume there is a number that is not the product of primes. Let n be the smallest such number. Then n is divisible by 1, and -1, and n, and -n If n has no other divisors then it is prime. So n = n. The other case is that n has a proper divisor. Let m be such a divisor so n = m k for some k∈. But then m,k<n. And thus m and k are products of primes. thus n is also a product of products of primes. Arriving to a contradiction.
    • ◼
  • There are an infinite number of primes!

    • Number Systems

    ◼
  • The way we represent numbers is a convention that we as humans have. Arabic numerals {0,1,2,3,4,5,6,7,8,9} are used as the digits in the most common representation of decimal numbers in the world.
    • ◼
  • २३४५६ = 23456
    • ◼
  • Even though the study of different base 10 (decimal) number numerals is interesting in itself, we will focus on the base portion of the representation.

    • Examples

    Number representation for bases larger than 10

    ◼
  • When representing numbers in a base larger than 10, we will use an extension of the arabic numerals to enhance our digit {0,1,2,3,4,5,6,7,8,9,a,b,c,d,...}
    • ◼
  • For representing base 11 digits we commonly use {0,1,2,3,4,5,6,7,8,9,a}
    • ◼
  • For representing base 12 digits we commonly use {0,1,2,3,4,5,6,7,8,9,a,b}
    • ◼
  • ... and so on until base 36.
    • ◼
  • Examples:

    • Where do we use this?

    ◼
  • Color picking for computers
    • ◼
  • Number representation in computers
    • ◼
  • You’ve probably heard the phrase “it’s just 0’s and 1’s” when referring to something computational. This has to do with the way that numbers(and really anything) is represented in computers, which uses the binary (or base 2) system.
    • ◼
  • floating point arithmetic

    • Do the following calculation Manually

    Congruences

    ◼
  • Note that congruence modulo n is an equivalence relation

    • Modular Arithmetic

    ◼