Math 5336 – Number Theory Class activities for October 21, 2002

Dr. Cordero

Topic: The Theory of Congruences, II

Review Homework from last time:

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

5. 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!)

Basic Properties of Congruences

  1. 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.
  2. Practice: Find the least residue:
    • 93 modulo 17
    • 421 modulo 17
    • 93 + 421  modulo 17
    • (93)(421)  modulo 17
    •    modulo  21.
  3. 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.
  4. Compute the least residue of  modulo 17.
  5. At-home Practice: Find the least residue of   modulo 4;  modulo 19;  modulo 23
  6. Find the last two digits of .
  7. Homework: Pp. 68-69 # 2, 4, 5, 16.

 C. Special Divisibility Tests

  1. A number n is divisible by 3 if and only if…..
  2. A number n is divisible by 9 if and only if…..
  3. A number n is divisible by 11 if and only if…..
  4. A number n is divisible by 37 if and only if….. (At-Home Practice)
  5. Card Shuffling:
    Suppose we have a deck of 52 cards and we cut it into two piles, the top half and the bottom half. If we then interlace the cards, with the bottom card of the top half going on the bottom of the shuffle pile, the bottom card of the bottom half going on top of this card, etc., we call this process an in-shuffle (because the original top and bottom cards of the deck are inside the deck after the shuffle).
    • Questions:
      • If a card starts out x spots from the bottom of the original deck, where does it end up after one perfect in-shuffle?
      • If a card starts out x at position x (counting from from the bottom of the original deck), where is  it  after 2  perfect in-shuffles? 3 perfect in-shuffles? K perfect in-shuffles?
      • Is there a positive number of shuffles that one can do which will restore the entire deck to its original position?