Math 5336 Number Theory Dr. Cordero
Class activities for October 28, 2002
Topic: The Theory of Congruences, II
Euler’s Phi Function
A Review Homework from last time:
5. Athome Practice: Find the least residue of modulo 4; modulo 19; modulo 23
7. Homework: Pp. 6869 # 2, 4, 5, 16.
1. A number n is divisible by 37 if and only if….. (AtHome Practice)
B. 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 inshuffle (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 inshuffle?
· If a card starts out x at position x (counting from the bottom of the original deck), where is it after 2 perfect inshuffles? 3 perfect inshuffles? k perfect inshuffles?
· 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 outshuffle: The idea here is exactly the same as with the perfect inshuffle, 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 outshuffles 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