Scribd Logo
Upload

Welcome to Scribd!

  • 41 views

    DM CWK1 Myrie Ranordo

    Uploaded by

    Ranordo Myrie
    The document contains examples and proofs related to number theory concepts: 1) Euclid's algorithm is used to find the greatest common divisor (gcd) of 1230,96 (which is 3) and 34,411 (which is 1). 2) Modular arithmetic examples, finding 361620 modulo 17 (which is 16) and modulo 30 (which is 6). 3) Solving modular equations, finding solutions to 5x+1≡0 (mod 13) and 17x-5 ≡0 (mod 211). 4) Proofs that: a) the gcd of a,b is equal to the gcd of b,a-kb for any integers a,b,

    Copyright:

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

    DM CWK1 Myrie Ranordo

    Uploaded by

    Ranordo Myrie
    41 views2 pages
    The document contains examples and proofs related to number theory concepts: 1) Euclid's algorithm is used to find the greatest common divisor (gcd) of 1230,96 (which is 3) and 34,411 (which is 1). 2) Modular arithmetic examples, finding 361620 modulo 17 (which is 16) and modulo 30 (which is 6). 3) Solving modular equations, finding solutions to 5x+1≡0 (mod 13) and 17x-5 ≡0 (mod 211). 4) Proofs that: a) the gcd of a,b is equal to the gcd of b,a-kb for any integers a,b,

    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 contains examples and proofs related to number theory concepts: 1) Euclid's algorithm is used to find the greatest common divisor (gcd) of 1230,96 (which is 3) and 34,411 (which is 1). 2) Modular arithmetic examples, finding 361620 modulo 17 (which is 16) and modulo 30 (which is 6). 3) Solving modular equations, finding solutions to 5x+1≡0 (mod 13) and 17x-5 ≡0 (mod 211). 4) Proofs that: a) the gcd of a,b is equal to the gcd of b,a-kb for any integers a,b,

    Copyright:

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

    DM CWK1 Myrie Ranordo

    Uploaded by

    Ranordo Myrie
    The document contains examples and proofs related to number theory concepts: 1) Euclid's algorithm is used to find the greatest common divisor (gcd) of 1230,96 (which is 3) and 34,411 (which is 1). 2) Modular arithmetic examples, finding 361620 modulo 17 (which is 16) and modulo 30 (which is 6). 3) Solving modular equations, finding solutions to 5x+1≡0 (mod 13) and 17x-5 ≡0 (mod 211). 4) Proofs that: a) the gcd of a,b is equal to the gcd of b,a-kb for any integers a,b,

    Copyright:

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

    2. Euclid’s algorithm. Use the Euclid’s Algorithm to find each of the following.

    (a) gcd(1230, 96) = 1230 = 96 · 12 + 78


    96 = 78 · 1 + 18
    78 = 18 · 4 + 6
    18 = 6 · 3
    Ans. = gcd(1230, 96) = 3.

    (b) gcd(34, 411) = 411=34.12+3


    34= 3.11+1
    Ans. = gcd(34, 411) = 1.

    3. Congruence. Evaluate the following.

    (a) 361620(mod 17) =

    By Fermat’s little theorem 3616 ≡ 1 (mod 17).


    1620 = 16 ∗ 101 + 4.
    Therefore, 361620 ≡ 364 ≡ 24 = 16 (mod 17).

    (b) 361620(mod 30) =


    36 ≡ 6 (mod 30) and 6 · 6 ≡ 6 (mod 30).
    It follows that 36k ≡ 6 (mod 30) for every positive integer k, and,
    in particular,
    for k = 1620.
    4. Modular equations. Solve the following equations.
    (a) 5x + 1 ≡ 0 (mod 13); 5 · 8 − 13 · 3 = 1.
    Therefore 5 · 8 ≡ 1 (mod 13).
    5x ≡ −1 (mod 13)
    8 · 5x ≡ 8 · (−1) (mod 13)
    x ≡ −8 ≡ 5 (mod 13).

    (b) 17x − 5 ≡ 0 (mod 211);


    Using Eucledian algorithm we obtain 5·211−62·17 = 1, and (−62)·17 ≡
    1(mod 211).
    As in (a), we get x ≡ (−62) · 5 = −310 ≡ 112 (mod 211).

    (c) x2 − 3x + 2 ≡ 0 (mod 17).

    x2 − 3x + 2 ≡ 0 (mod 17)
    (x − 1)(x − 2) ≡ 0 (mod
    17) x ≡ 1, 2 (mod 17).
    5. Proofs.

    (a) Show that for all integers a, b and k we have


    gcd(a, b) = gcd(b, a − kb).

    (b) Show that for all positive integers m and n

    gcd(2m − 1, 2n − 1) = 2gcd(m,n) −
    1.

    Solution: a) Let d1 = gcd(a, b) and let d2 = gcd(b, a − kb). We have d1|a and d1|b,
    therefore d1|a − kb and consequently d1|d2. On the other hand, d2|b and d2|a − kb,
    therefore d2|(a − kb) + k · b = a. It follows that d2|d1. Thus, d1 = d2, as required.
    b): Suppose not. Let m, n be the pair of positive integers for which the formula does not hold
    chosen with m + n as small as possible and with m > n. (If m = n the formula is clearly correrct.)
    Using part (a) we have,

    gcd(2 m − 1, 2n − 1) = gcd(2n − 1, 2m − 1 − 2m−n(2n − 1)) = gcd(2 n − 1, 2m−n − 1).


    As n + (m − n) = m < m + n, by the choice of m and n as the counterexample with the smallest
    sum, we have

    gcd(2n − 1, 2m−n − 1) = 2gcd(n,m−n) − 1 = 2gcd(m,n)


    − 1,
    where we used the result of part (a) again in the last equality. Therefore the formula is correct
    fro m and n, contradicting existence of a counterexample.

    You might also like