Math 5336 Number Theory Dr. Cordero

Class activities for October 14th, 2002

Topics: Primes and Their Distribution, II

The Theory of Congruences, I

- 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

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

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

- T
__ask__: 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.**

** **

** **

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

** **

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