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:

- 141x+120y=3
- 243x+41y=1
- 243x+41y=6
- 1721x+378y=7

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?

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