Math 5336 Number Theory                                                       Dr. Cordero


Class activities for September 16, 2002

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: Compute:

·        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.


a.  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,

                          b.   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.


                    c.  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.


              5. 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?


  6. 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.


7. a. Question: If a|bc, must a|b and a|b?

     b. If a|bc with gcd(a,b)=1, must a|c?


8. Practice: §2.2 p.25 # 7, 14


9. Euclidean Algorithm: Read page 27 (up to Lemma ).

·        What is the Euclidean Algorithm?

·        What is the Euclidean Algorithm used for?

·        Write an example where you use the Euclidean Algorithm.


10. a. Find gcd(364, 140).

       b. How can we write gcd(364, 140) as a linear combination of 364 and 140?


11. Use the Extended Euclidean Algorithm to find integers x and y such that:


12. 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?