SOLUTIONS SOLUTIONS


Math 2320.03
Quiz 2 Version 2     November 3, 2000

  1. Find gcd(574,434) .
    Answer:
    574
    =
    1(434) + 140
    434
    =
    3(140) + 14
    140
    =
    10(14) + 0
    We have gcd(574,434) = 14 .
  2. Solve 23x      18 mod 5 and list three solutions.
    Answer:
    23x
    18 mod 5
    3x
    3 mod 5
    7·3x
    7·3 mod 5
    21x
    21 mod 5
    x
    1 mod 5
    Now choose any three elements of {, -9, -4, 1, 6, 11, 16, }.
  3. Prove that if d|a and d|a-k then d|k.
    Answer:| a a = ad for some a and d | a+k a -k = bd for some b.
    Then k = (a-b)d so that d | k. Does gcd(a,a-k)|k for k 0 ? Explain.
    Answer: Yes. Since every common divisor of a and a - k divides k, the greatest common divisor certainly does. What is gcd(a,a-1) ? Explain.
    Answer: As gcd(a,a-1) | 1 we must have gcd(a,a-1) = 1.

  4. Find all integers that satisfy simultaneously
    x
    1 mod 2
    x
    4 mod 5
    x
    7 mod 3

    Answer:
    We have M1 = 15, M2 = 6, M3 = 10.
    Solve 15y1 1 mod 2 to get y1 = 1.
    Solve 6y2 1 mod 5 to get y2 = 1.
    Solve 10y3 1 mod 3 to get y3 = 1.
    One solution is 15·1·1 + 6 ·1 ·4 + 10 ·1 ·7 = 109 and the general solution is
    x 19 mod 3o  .


File translated from TEX by TTH, version 2.60.
On 4 Nov 2000, 19:02.