Scribd Logo
Upload

Welcome to Scribd!

  • 16 views

    Poly Euclid Algorithm

    Uploaded by

    mashareco
    The document summarizes number theory concepts including: 1) The Euclidean algorithm provides an efficient method to compute the greatest common divisor (GCD) of two integers without needing their prime factorizations. 2) The extended Euclidean algorithm allows expressing the GCD of two integers as a linear combination of the integers. 3) Relatively prime integers (coprime) are integers with a GCD of 1. The Chinese remainder theorem guarantees a unique solution exists to finding an integer satisfying two modulo equations involving relatively prime moduli.

    Copyright:

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

    Poly Euclid Algorithm

    Uploaded by

    mashareco
    16 views6 pages
    The document summarizes number theory concepts including: 1) The Euclidean algorithm provides an efficient method to compute the greatest common divisor (GCD) of two integers without needing their prime factorizations. 2) The extended Euclidean algorithm allows expressing the GCD of two integers as a linear combination of the integers. 3) Relatively prime integers (coprime) are integers with a GCD of 1. The Chinese remainder theorem guarantees a unique solution exists to finding an integer satisfying two modulo equations involving relatively prime moduli.

    Original Title

    poly euclid algorithm

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes number theory concepts including: 1) The Euclidean algorithm provides an efficient method to compute the greatest common divisor (GCD) of two integers without needing their prime factorizations. 2) The extended Euclidean algorithm allows expressing the GCD of two integers as a linear combination of the integers. 3) Relatively prime integers (coprime) are integers with a GCD of 1. The Chinese remainder theorem guarantees a unique solution exists to finding an integer satisfying two modulo equations involving relatively prime moduli.

    Copyright:

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

    Poly Euclid Algorithm

    Uploaded by

    mashareco
    The document summarizes number theory concepts including: 1) The Euclidean algorithm provides an efficient method to compute the greatest common divisor (GCD) of two integers without needing their prime factorizations. 2) The extended Euclidean algorithm allows expressing the GCD of two integers as a linear combination of the integers. 3) Relatively prime integers (coprime) are integers with a GCD of 1. The Chinese remainder theorem guarantees a unique solution exists to finding an integer satisfying two modulo equations involving relatively prime moduli.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 6

    Number Theory.

    Tutorial 2:
    The Euclidean algorithm

    1 The number of divisors of n


    Let n be a positive integer with the prime factorisation
    n = pα1 1 pα2 2 . . . pαr r , (1)
    where pi are distinct primes and αi are positive integers. How can we find
    all divisors of n? Let d be a divisor of n. Then n = dm, for some m, thus
    n = dm = pα1 1 pα2 2 . . . pαr r ,
    Since the prime factorisation of n is unique, d cannot have in its prime
    factorisation a prime which is not among the primes p1 , p2 , . . . , pr . Also, a
    prime pi in the prime factorisation of d cannot have an exponent greater than
    αi . Therefore
    d = pβ1 1 pβ2 2 . . . pβr r , 0 ≤ βi ≤ αi , i = 1, 2, . . . , r. (2)
    Theorem 1. The number of positive divisors of n is
    d(n) = (α1 + 1)(α2 + 1) . . . (αr + 1). (3)
    Proof. Indeed, we have exactly αi + 1 possibilities to choose βi in (2), namely
    0, 1, 2, . . . , αi . Thus the total number of divisors will be exactly the product
    (α1 + 1)(α2 + 1) . . . (αr + 1).
    Definition 1. The numbers kn, where k = 0, ±1, ±2, . . . , are called multi-
    ples of n.
    It is clear that any multiple of n given by (1) has the form
    m = kpγ11 pγ22 . . . pγr r , γi ≥ αi , i = 1, 2, . . . , r,
    where k has no primes p1 , p2 , . . . , pr in its prime factorisation. The number
    of multiples of n is infinite.

    1
    2 Greatest common divisor and least com-
    mon multiple
    Let a and b be two positive integers. If d is a divisor of a and also a divisor of
    b, then we say that d is a common divisor of a and b. As there are only a finite
    number of common divisors, there is a greatest common divisor, denoted by
    gcd (a, b). The number m is said to be a common multiple of a and b if m is a
    multiple of a and also a multiple of b. Among all common multiples there is a
    minimal one (Least-integer principle!). It is called the least common multiple
    and it is denoted by lcm (a, b).
    In the decomposition (1) we had all exponents positive. However, some-
    times it is convenient to allow some exponents to be 0. This is especially
    convenient, when we consider prime factorisations of two numbers a and b,
    looking for gcd (a, b) and lcm (a, b), since we may assume that both a and b
    have the same set of primes in their prime factorisations.
    Theorem 2. Let

    a = pα1 1 pα2 2 . . . pαr r , b = pβ1 1 pβ2 2 . . . pβr r ,

    where αi ≥ 0 and βi ≥ 0, be two arbitrary positive integers. Then


    min(α1 ,β1 ) min(α2 ,β2 )
    gcd (a, b) = p1 p2 . . . pmin(α
    r
    r ,βr )
    , (4)

    and
    max(α1 ,β1 ) max(α2 ,β2 )
    lcm (a, b) = p1 p2 . . . pmax(α
    r
    r ,βr )
    . (5)

    Moreover,

    gcd (a, b) · lcm (a, b) = a · b. (6)

    Proof. Formulas (4) and (5) follow from our description of common divisors
    and common multiples. To prove (6) we have to notice that min(αi , βi ) +
    max(αi , βi ) = αi + βi .
    We suspect (in fact it is an open question) that prime factorisation is
    computationally difficult and we don’t know easy algorithms for that but
    fortunately the greatest common divisor gcd (a, b) of numbers a and b can be
    found without knowing the prime factorisations for a and b. This algorithm
    was known to Euclid and maybe even was discovered by him.

    2
    Theorem 3 (The Euclidean Algorithm). Let a and b be positive inte-
    gers. We use the division algorithm several times to find:

    a = q1 b + r1 , 0 < r1 < b,
    b = q2 r1 + r2 , 0 < r2 < r1 ,
    r1 = q3 r2 + r3 , 0 < r3 < r2 ,
    ..
    .
    rs−2 = qs rs−1 + rs , 0 < rs < rs−1,
    rs−1 = qs+1 rs .

    Then rs = gcd (a, b).

    Proof. Is based on the observation that if a = qb + r, then gcd (a, b) =


    gcd (b, r). Indeed, if d is a common divisor of a and b, then a = a0 d and
    b = b0 d and then r = a − qb = a0 d − qb0 d = (a0 − qb0 )d and d is also a common
    divisor of b and r. Also if d is a common divisor of b and r, then b = b0 d,
    r = r0 d and a = qb + r = qb0 d + r 0 d = (qb0 + r 0 )d, whence d is a common
    divisor of a and b.
    It is clear now that gcd (a, b) = gcd (b, r1 ) = gcd (r1 , r2 ) = . . . =
    gcd (rs−1 , rs ) = rs .

    Theorem 4 (The Extended Euclidean Algorithm). Let us write the fol-


    lowing table with two rows R1 , R2 , and three columns:
     
    a 1 0
    .
    b 0 1

    In accordance with the Euclidean Algorithm above, we perform the following


    operations with rows of this table. First we will create the third row R3 by
    subtracting from the first row the second row times q1 , we denote this as R3 :=
    R1 − q1 R2 . Then similarly we create the fourth row: R4 := R2 − q2 R3 . We
    will continue this process as follows: when creating Rk we will obtain it taking
    Rk−2 and subtracting Rk−1 times qk−2 , which can be written symbolically as

    3
    Rk := Rk−2 − qk−2 Rk−1 . Eventually we will obtain the table:
     
    a 1 0
     b 0 1 
     
     r1 1 −q1 
     
     r2 −q 1 + q q .
     2 1 2 
     .. 
     . 
    rs m n

    Then gcd (a, b) = rs = am + bn.

    Proof. We will prove this by induction. Let the kth row of the table be

    Rk = (uk , vk , wk ).

    We assume that ui = avi +bwi for all i < k. This is certainly true for i = 1, 2.
    Then by induction hypothesis

    uk = uk−2 − qk uk−1 = avk−2 + bwk−2 − qk (avk−1 + bwk−1 ) =

    a(vk−2 − qk vk−1 ) + b(wk−2 − qk wk−1 ) = avk + bwk .

    Thus the statement ui = avi + bwi is true for all i. In particular, this is true
    for the last row, which gives us rs = am + bn.

    Example 1. Let a = 321, b = 843. Find the greatest common divisor


    gcd (a, b), the least common multiple lcm (a, b), and a linear presentation
    of the greatest common divisor in the form gcd (a, b) = ka + mb.
    The Euclidean algorithm:

    321 = 0 · 843 + 321


    843 = 2 · 321 + 201
    321 = 1 · 201 + 120
    201 = 1 · 120 + 81
    120 = 1 · 81 + 39
    81 = 2 · 39 + 3
    39 = 13 · 3 + 0,

    4
    321 · 843
    and therefore gcd (321, 843) = 3 and lcm (321, 843) = = 107 · 843 =
    3
    90201. The Extended Euclidean algorithm:
    321 1 0
    843 0 1
    321 1 0
    201 −2 1
    120 3 −1
    81 −5 2
    39 8 −3
    3 −21 8
    obtaining the linear presentation gcd (321, 843) = 3 = (−21) · 321 + 8 · 843.

    3 Relatively prime numbers


    Definition 2. If gcd (a, b) = 1, the numbers a and b are said to be relatively
    prime (or coprime).
    The following properties of relatively prime numbers are often used.
    Lemma 1. Let gcd (a, b) = 1, i.e., a and b are relatively prime. Then
    1. a and b do not have common primes in their prime factorisations;
    2. If c is a multiple of a and also a multiple of b, then c is a multiple of
    ab;
    3. If ac is a multiple of b, then c is a multiple of b;
    4. There exist integers m, n such that ma + nb = 1.
    Proof. Part 1 follows from equation (4), parts 2 and 3 follow from part 1,
    and part 4 follows from Theorem 4.
    Theorem 5 (The Chinese remainder theorem). Let a and b be two rel-
    atively prime numbers, 0 ≤ r < a and 0 ≤ s < b. Then there exists a unique
    number N such that 0 ≤ N < ab and
    r = N (mod a) and s = N (mod b), (7)
    i.e., N has remainder r on dividing by a and remainder s on dividing by b.

    5
    Proof. Let us prove first, that there exists at most one integer N with the
    conditions required. Assume, on the contrary, that for two integers N1 and
    N2 we have 0 ≤ N1 < ab, 0 ≤ N2 < ab and

    r = N1 (mod a) = N2 (mod a) and s = N1 (mod b) = N2 (mod b).

    Let us assume that N1 > N2 . Then the number M = N1 − N2 satisfies


    0 ≤ M < ab and

    0 = M (mod a) and 0 = M (mod b). (8)

    By Lemma 1 part 3, condition (8) implies that M is divisible by ab, whence


    M = 0 and N1 = N2 .
    Now we will find an integer N, such that r = N (mod a) and s =
    N (mod b), ignoring the condition 0 ≤ N < ab. By Theorem 4 there are
    integers m, n such that gcd (a, b) = 1 = ma + nb. Multiplying this equation
    by r − s we get the equation

    r − s = (r − s)ma + (r − s)nb = m0 a + n0 b.

    Now it is clear that the number

    N = r − m0 a = s + n0 b

    satisfies the condition (7). If N does not satisfy 0 ≤ N < ab, we divide N by
    ab with remainder N = q · ab + N1 . Now 0 ≤ N1 < ab and N1 satisfies (7).
    Theorem is proved.
    This is a constructive proof of the Chinese remainder theorem, which
    gives also an algorithm of calculating such N with property (7). A shorter
    but nonconsructive proof, which uses Pigeonhole principle can be found in the
    training material ”Pigeonhole Principle.” It is used there to prove Fermat’s
    theorem that any prime of the type 4n + 1 can be represented as a sum of
    two squares.

    Copyright: MathOlymp.com Ltd 2001. All rights reserved.

    You might also like