Math 5336 – Number Theory Day 3 Class activities for September 16, 2002

Dr. Cordero

Topic: Divisibility Theory in the Integers, II

  1. Question: Let a, b, c be integers. If a|b and  a|c, must a|bx+cy for any integers x and y?
  2. Greatest common divisor

What is the greatest common divisor of two integers a and b?

Practice:

  • gcd(14, 21)
  • gcd(15, 35)
  • gcd(96,48)
  • gcd(13, 43)
  • gcd(7696, 4144)

3. The division algorithm

Let a and b be integers with b = 0. Then there are unique integers q and r such that 0<r<|b| and a=bq+r.

  1. Practice: Find the unique q and r guaranteed by the Division Algorithm for each pair a and b:

    • a=96, b=48
    • a=96, b=36
    • a=87, b=15
    • a=7696, b=4144
    • b=47
    • a=235

  2. Applications of the Division Algorithm

    • Use the division algorithm to show that the square of any odd integer n is of the form 8k+1.

    • Use the division algorithm to show that for any, the expression is an integer.
  3. Practice: §2.1 pp 19-20 # 1, 2, 3a, 3b.

4. Question: What does it mean for two integers a and b to be “relatively prime”?

  • Give an example of a pair of integers a and b which are relatively prime but none of which is a prime number.
  1. Study the following theorem:
    Theorem  Given integers a and b not both 0, there exists integers x and y such that gcd(a,b)=ax+by.
  • What is the statement for integers that are relatively prime?
  1. a. Question: If a|b and b|c, must ab|c? Study some cases.
    b. Prove the following theorem:
          Theorem If a|c and b|c with gcd(a,b)=1, then ab|c.
  2. a. Question: If a|bc, must a|b and a|b?
    b. If a|bc with gcd(a,b)=1, must a|c?
  3. Practice: §2.2 p.25 # 7, 14
  4. Euclidean Algorithm:Read page 27 (up to Lemma ).
  1. a. Find gcd(364, 140).
    b. How can we write gcd(364, 140) as a linear combination of 364 and 140?
  2. Use the Extended Euclidean Algorithm to find integers x and y such that:
  • 141x+120y=3
  • 243x+41y=1
  • 243x+41y=6
  • 1721x+378y=7
  1. The Stamps Problem
    Suppose you have an unlimited supply of 6 -cents stamps and 11- cents stamps.
    What amounts  of postage  can you make with these stamps?
  • Solve the Stamps problem.
  • What if the stamps were of 6-cents and 9-cents?
  • What if the stamps were of 6-cents and 10-cents?