Math 5336 – Number Theory Day 9 Class activities for October 28, 2002

Topic: The Theory of Congruences, II
Euler’s Phi Function

Review Homework from last time:

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

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

  1. A number n is divisible by 37 if and only if….. (At-Home Practice)

     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  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?
      •  
    1. Find the smallest positive integer  such that (mod 53) for every integer  with .
    2. Perfect out-shuffle:  The idea here is exactly the same as with the perfect in-shuffle, except that the card which was originally on the bottom of the deck remains on the bottom of the deck and the card which was originally on the top of the deck remains on the top of the deck.

      Question: How many perfect out-shuffles does it take to restore a deck of 52 cards to its original ordering?

      Is this question equivalent to the following question?
      What is the smallest integer k such that  (mod 51)?

    3. Come up with a conjecture of the form “There is a positive integer k such that   (mod m) if and only if (some condition on a and m.) The following table might help:

      list of  with

       such that

      there is  a  with  (mod m)

      smallest  such that

       (mod m)  for every

      a in the second column

      Number of a’s

       in the second column.

      3

       

       

       

      4

       

       

       

      5

       

       

       

      6

       

       

       

      7

       

       

       

      8

       

       

       

      9

       

       

       

      10

       

       

       

      11

       

       

       

      12

       

       

       

      13

       

       

       

      14

       

       

       

      15

       

       

       

      16

       

       

       
    4. Euler Phi Function: For  , the value of the Euler Phi Function is defined to be  and gcd .
      • If p is prime what is  where n is a positive integer?
      • If p and q are primes with  , what is