Math 5336 Number Theory                                                       Dr. Cordero

Class activities for October 14th, 2002

Topics: Primes and Their Distribution,  II

The Theory of Congruences, I

1. In-class Practice:

·         Page 44 # 3 (a, c, e ), 4, 5a (Hint: Use Corollary 1, p. 41), 6a (Hint: Write  and make “obvious” choices for the coefficients.)

·         Page 59 # 3, 9

1. At-home Practice: Page 50 # 1, 2, 5;  Page 59 # 1, 2,  19

1. Definition: We say that  is congruent to  modulo , written  (mod ) if  divides .

1. Task: For each value of a among 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, find at least 4 positive integers and at least 4 negative integers b which are congruent to a modulo 6.

1. Look at the lists you made above and see how many patterns you can spot. For example:

i.      How are the numbers within a specific list related?

ii.      How are the numbers in different lists related?

iii.      How many distinct lists are there?

1. Fill in the blanks on each of the following sentences:
• a is even if and only if a is congruent to _____modulo ______.
• a is odd if and only if a is congruent to _____modulo _______.
• a is a four-one number if and only if a is congruent to ____ modulo____.
• a is a four-three number if and only if a is congruent to ____ modulo____.

7.Conjecture: Let a, b c, d and m be integers with m>0. Assume that

·        a is congruent to b modulo m

·        c is congruent to d modulo m

Then we have;

·        a+c is congruent to b+d modulo m

·        ac is congruent to bd modulo m

Prove this conjecture. (Hint: You’ve already done this!)

8. Definition: If m>0 and r is the remainder when the division algorithm is used to divide b by m, then r is called the least residue of b modulo m.

9. Practice: Find the least residue:

·        93 modulo 17

·        421 modulo 17

·        93 + 421  modulo 17

·        (93)(421)  modulo 17

·         modulo  21.

10. General method to find the least residue of  modulo m:

Step 1: Write z as a sum of powers of 2.

Step 2: Successively square a until you’ve gone as high as you need, reducing modulo m at each stage. Feel free to use negative numbers if it makes the computations easier.

Step 3: Put it together, using laws of exponents.

11. Compute the least residue of  modulo 17.

12. At-home Practice: Find the least residue of   modulo 4;  modulo 19;  modulo 23

13. Find the last two digits of .

14. Homework: Pp. 68-69 # 2, 4, 5, 16.