Math 5336 – Number Theory Class activities for October 14th, 2002

Dr. Cordero

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
  2. At-home Practice: Page 50 # 1, 2, 5;  Page 59 # 1, 2,  19
  3. Definition: We say that  is congruent to  modulo , written  (mod ) if  divides .
  4. 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.
  5. Look at the lists you made above and see how many patterns you can spot. For example:
    1. How are the numbers within a specific list related?
    2. How are the numbers in different lists related?
    3.  How many distinct lists are there?
  6. 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.