Introduction to Number Theory Part 2

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.
    • ◼
  • 2345 =
    2*
    3
    10
    +3*
    2
    10
    +4*
    1
    10
    +5*
    0
    10
    • ◼
  • abc
    d
    10
    =a
    3
    10
    +b
    2
    10
    +c
    1
    10
    +d
    0
    10
    where
    0<=a,b,c,d<10
    • ◼
  • abc
    d
    p
    =a
    3
    p
    +b
    2
    p
    +c
    1
    p
    +d
    0
    p
    where
    0<=a,b,c,d<p

    • Examples

    123
    4
    =1*
    2
    4
    +2*4+3
    In[]:=
    1*
    2
    4
    +2*4+3
    Out[]=
    27
    1011
    2
    =1
    3
    2
    +0
    2
    2
    +12+1
    In[]:=
    1
    3
    2
    +0
    2
    2
    +12+1
    Out[]=
    11

    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:
    • 11a
    2
    11
    =
    3
    11
    +
    2
    11
    +1011+2
    In[]:=
    3
    11
    +
    2
    11
    +1011+2
    Out[]=
    1564
    12
    12
    =1*12+2
    14
    1
    a
    11
    =11+10
    21
    bacd
    11
    =??
    ◼
  • We can’t calculate the last one because b does not mean anything in base 11.
    • In[]:=
    ff
    16
    =1516+15
    Out[]=
    255

    Where do we use this?

    ◼
  • Color picking for computers
    • In[]:=
    SystemOpen["https://htmlcolorcodes.com/"]
    ◼
  • 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
    • In[]:=
    SystemOpen["https://www.programiz.com/javascript/online-compiler/"]
    In[]:=
    0.1+0.2
    Out[]=
    0.3
    In[]:=
    1
    3
    +
    1
    3
    +
    1
    3
    Out[]=
    1
    In[]:=
    BaseForm[0.1,2]
    Out[]//BaseForm=
    0.00011001100110011001101
    2
    In[]:=
    BaseForm[0.2,2]
    Out[]//BaseForm=
    0.0011001100110011001101
    2
    In[]:=
    BaseForm[0.3,2]
    Out[]//BaseForm=
    0.01001100110011001101
    2
    In[]:=
    BaseForm[2^^0.00011001100110011001101+2^^0.0011001100110011001101,2]
    Out[]//BaseForm=
    0.01001100110011001101
    2

    Do the following calculation Manually

    0.00011001100110011001101​​0.00110011001100110011010
    0.01001100110011001100111
    In[]:=
    2^^0.01001100110011001100111
    Out[]=
    0.3
    In[]:=
    N[2.0000000000000000000000000000^-2+2^-5+2^-6+2^-9+2^-10+2^-13+2^-14+2^-17+2^-18+2^-21+2^-22+2^-23,30]
    Out[]=
    0.3000000715255737304687500000
    ​

    The Extended Euclidean Algorithm

    ◼
  • Consider the Euclidean Algorithm:
    ​
    • ◼
  • Let
    a,b∈
    *
    
    then by following the procedure
    • ◼
  • 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
    i
    =
    r
    i+1
    q
    i+2
    +
    r
    i+2
    with
    0<=
    r
    i+2
    <
    r
    i+1
    • ◼
  • ...
    • ◼
  • r
    n-2
    =
    r
    n-1
    q
    n
    +
    r
    n
    • ◼
  • r
    n-1
    =
    r
    n
    q
    n+1
    +0
    • ◼
  • Where
    r
    n
    is the last non-zero residue, then
    r
    n
    is GCD(
    a,b
    )
    • ◼
  • Let us consider the following Procedure where our goal is to write
    r
    n
    in terms of
    a
    and
    b
    .
    • ◼
  • A bit of an intuition for the procedure comes from rewriting
    r
    n
    in terms of
    r
    n-1
    and
    r
    n-2
    ​
    Indeed
    ​
    r
    n
    =
    r
    n-2
    -
    q
    n
    r
    n-1
    ​
    Then using that
    r
    n-3
    =
    r
    n-2
    q
    n-1
    +
    r
    n-1
    we get that
    r
    n-1
    =
    r
    n-3
    -
    r
    n-2
    q
    n-1
    and substituting we get
    ​
    r
    n
    =
    r
    n-2
    -
    q
    n
    (
    r
    n-3
    -
    r
    n-2
    q
    n-1
    )=
    r
    n-2
    (1+
    q
    n
    q
    n-1
    )+
    r
    n-3
    (-
    q
    n
    )
    • ◼
  • Let b=
    r
    0
    ,
    a=
    r
    -1
    • ◼
  • The we have
    r
    i+2
    =
    r
    i
    -
    r
    i+1
    q
    i+2
    • ◼
  • r
    i
    =
    r
    i-2
    -
    r
    i-1
    q
    i
    ​
    ​
    r
    n
    =
    t
    i-1
    r
    n-i
    +
    s
    i-1
    r
    n-i+1
    ​
    ​
    r
    n
    =
    t
    i
    r
    n-i
    +
    s
    i-1
    (
    r
    n-i-1
    -
    r
    n-i
    q
    n-i+1
    )=
    s
    i-1
    r
    n-i-1
    +
    r
    n-i
    (
    t
    i
    -
    s
    i-1
    q
    n-i+1
    )
    • ◼
  • So we define:
    ​
    s
    i
    =-(
    s
    i-2
    -
    s
    i-1
    q
    n-i-1
    )
    ​
    with
    ​
    s
    1
    =-
    q
    n
    and
    s
    2
    =1
    • ◼
  • s
    i
    is the coefficient of
    r
    n-i
    when we express
    r
    n
    =
    s
    i
    r
    n-i
    +
    s
    i-1
    r
    n-i+1
    • ◼
  • Thus we can express
    r
    n
    =
    s
    n+1
    a+
    s
    n
    b
    .
    • ◼
  • To summarize: Let
    a,b∈
    *
    
    . There are
    x,y∈
    such that
    GCD(a,b)=xa+yb
    . This form is called a linear combination. We call the above procedure to find
    s
    n+1
    and
    s
    n
    the extended Euclidean Algorithm.
    • ◼
  • A couple observations, if we can express a number m as a linear combination of two integer numbers
    a
    and
    b
    , (e.g.
    m=xa+yb
    ) then we have that the greatest common divisor of
    a
    and
    b
    divides m. (i.e.
    GCD(a,b)|m
    ).
    • ◼
  • We can write this as a theorem:
    Let
    a,b,m∈
    . If there are
    x,y∈
    such that
    ax+by=m
    then
    GCD(a,b)|m
    • ◼
  • In fact, thanks to the extended Euclidean algorithm the converse also holds true:
    • ◼
  • Let
    a,b,m∈
    . If
    GCD(a,b)|m
    , then there exists
    x,y∈
    such that
    ax+by=m
    .
    • ◼
  • Proof: First find
    x
    0
    and
    y
    0
    such that
    a
    x
    0
    +b
    y
    0
    =GCD(a,b)
    let k =
    m
    GCD(a,b)
    then
    a
    x
    0
    k+b
    y
    0
    k=GCD(a,b)k=m
    so our solution (i.e x, and y) is given by
    x
    0
    k
    and
    y
    0
    k
    .
    • ◼
  • Thus we have the equivalence:
    • ◼
  • Let
    a,b,m∈
    . There exists
    x,y∈
    such that
    ax+by=m
    if and only if
    GCD(a,b)|m
    .
    • ◼
  • Examples:
    • ◼
  • GCD(2,4) = 2 and 2 = 2(1)+4(0)
    • ◼
  • (2)=(4)0+2
    4 = (2)2
    • ◼
  • n=1
    so we are looking for
    s
    2
    = 1 and
    s
    1
    =0
    • ◼
  • GCD(5,3)= 1 and 1 = 5(-1) + 3(2)
    • ◼
  • a)
    5=(3)1+2
    ​
    b)
    3=(2)1+1
    ​
    c)
    2=(1)2
    • ◼
  • 1=(3)-(2)1
    (using b)
    ​
    1=3-(5-31)1
    (using a)
    ​
    1=(3)-(5)+(3)
    ​
    ​
    1=3(2)+(-1)5
    • ◼
  • n=2
    So we are looking for
    s
    3
    and
    s
    2
    ​
    ​
    s
    1
    =-1
    s
    2
    =1
    ​
    ​
    s
    3
    =-( -1 - 1*1)=2 (by
    s
    i
    =
    s
    i-2
    -
    s
    i-1
    q
    n-i-1
    )

    • Congruences

    ◼
  • If
    n∈
    , then we say that
    a
    is congruent to
    b
    modulo
    n
    if
    n|(a-b)
    . We usually denote this as
    a≡b(modn)
    and sometimes
    a
    ≡
    n
    b
    . Now if
    n(a-b)
    then we write
    a≢b(modn)
    .
    • ◼
  • This is equivalent to saying that
    a
    and b have the same residue when dividing by n.Indeed, if
    a=nk+
    r
    1
    with
    0<=
    r
    1
    <n
    , and
    b=nm+
    r
    2
    with
    0<=
    r
    2
    <n
    for integers
    k,m,
    r
    1,
    and
    r
    2
    ​Then we have that
    a-b=n(k-m)+(
    r
    1
    -
    r
    2
    )
    . Note that
    |
    r
    1
    -
    r
    2
    |<n
    , so in order for
    n|a-b
    we must have
    r
    1
    -
    r
    2
    =0
    . This implies that
    r
    1
    =
    r
    2
    . That is, the residue of
    a
    when dividing by
    n
    is the same as the residue of
    b
    when dividing by
    n
    .
    • ◼
  • Note that congruence modulo n is an equivalence relation.
    ​Reflexive: n|a-a since n|0
    ​Symmetric: If n|a-b, then n|b-a
    ​Transitive: If a and b have the same residue when dividing by n, and b and c have the same residue when dividing by n, then a and c have the same residue when dividing by n.

    • Modular Arithmetic

    1
    .
    Let
    a,b,c,d∈
    such that
    a
    ≡
    n
    b
    and
    c
    ≡
    n
    d
    . Then:
    1
    .
    1
    .
    a+c
    ≡
    n
    b+d
    1
    .
    2
    .
    a-c
    ≡
    n
    b-d
    ◼
  • Example

    • Multiplicative Inverses

    ◼
  • We do not always have a way to divide in the integers. But we do have (for some numbers) multiplicative inverses in the setting of congruences.
    • ◼
  • Examples:
    • ◼
  • 2 does not have a multiplicative inverse modulo 4.

    • Solving Congruences

    ◼
  • But we do not always have a solution...
    • ◼
  • Examples:
    • ◼
  • Example
    • ◼
  • Example

    • Diophantine Equations

    ◼
  • In many “real life problems” we are encountered with the mathematical question of finding integer solutions to equations. Some examples include balancing budgets, chemical equations, flow control for networks, and such.
    • ◼
  • These type of problems are called Diophantine equations.
    • ◼
  • Example:
    • ◼
  • We want to find x and y such that 5x + 3y = 2
    We know that (by an example above)
    5(-1) + 3(2) = 1 So we have that
    5(-2) + 3 (4) = 2
    5(-2 - k 3) +3(4+5 k) should also give me 2.
    Let us check:
    5(-2) -15k + 3(4) +15k = 5(-2) +3(4) = 2

    • Number Theory Class Exercises

    1
    .
    Show that x-1<⌊x⌋≤x
    3
    .
    Find the GCD of the following, and express it as a linear combination of the two numbers.
    3
    .
    1
    .
    22,55
    3
    .
    2
    .
    15,113
    4
    .
    Find the LCM of the following:
    4
    .
    1
    .
    15,385
    4
    .
    2
    .
    28,577
    5
    .
    Determine the solutions to the following congruences