SOLUTIONS SOLUTIONS


Math 2320.03
Quiz 2 Version 1     November 3, 2000

  1. Find gcd(689,234) .
    Answer:
    689
    =
    2(234) + 221
    234
    =
    1(221) + 13
    221
    =
    17(13) + 0
    We have gcd(689,234) = 13 .
  2. Solve 25x      30 mod 4 and list three solutions.
    Answer:
    25 x
    30 mod 4
    3x
    2 mod 4
    3·3x
    3·2 mod 4
    9x
    6 2 mod 4
    x
    2 mod 4
    Now choose any three elements of {, -10, -6, -2, 2, 6, 10, 14, }.
  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 = (b-a)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
    2 mod 3
    x
    3 mod 5
    x
    5 mod 2

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


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