## An application to Euler's -function

Let

as in 1.4.5.

Proposition 1.7.36   If then there is a 1-1, onto mapping between the sets

proof: If and , then define , where satisfies . This exists and is unique , by the Chinese remainder theorem, so is well-defined - provided we show . To show this, we must show that if , and that if and , then . We leave these as exercises.

is 1-1: If then and . Subtracting, we get , so and by definition of and . Therefore, is 1-1.

is onto: Let . Define and by . Then, by definition . Therefore, is onto.

The following result has been proven by more direct methods above. We given another proof as an application of the Chinese remainder theorem.

Proposition 1.7.37   If then .

proof: The number of elements in the range of is and the number of elements in the domain of is . Since is a bijection, these two must be equal.

Corollary 1.7.38   If is the prime factorization of an integer then .

Exercise 1.7.40   Verify Example 1.7.39.

Exercise 1.7.41   Define , , . Find a formula for as in the above example.

Exercise 1.7.42 (Fibonacci numbers)   Let satisfy and let . Solve for .

Exercise 1.7.43   Let satisfy and let , , . Solve for . (This is the Lucas-Perrin sequence.)

Exercise 1.7.44   An internet pyramid scheme starts with a group of friends in different states. They come up with an email which asks the recipient to forward the email to others. Find the linear recurrence relation which describes this process after iterations (assuming every email is sent to a different person). First, solve it in terms of and in general. Next, for specific values of and (say and ).

Exercise 1.7.45   An internet pyramid scheme starts with a group of friends in different states. They come up with an email which asks the recipient to add their name onto the list (which originally contains the names of the friends) and forward the email to others, where is the number of people on the list. Find the linear recurrence relation which describes this process after iterations (assuming every email is sent to a different person). First, solve it in terms of in general. Next, for specific values of (say ).

Exercise 1.7.46   Use Caeser's cipher in §1.7.7 to decode ehdw dupb''. (Hint: a commonly uttered phrase at the U. S. Naval Academy.)

Exercise 1.7.47   Find the first 20 terms of the LFSR with seed and recursion equation , .

Exercise 1.7.48   Find the first 20 terms of the LFSR with seed and recursion equation , .

Exercise 1.7.49   A sequence is eventually periodic if there are fixed (called the period) and such that ,for all . (If then we call the sequence periodic.) Are the sequences in the above exercises eventually periodic? If so, what are their periods?

Exercise 1.7.50   Using the algorithm in §1.7.9, solve for the day of the week of your birthday.

Exercise 1.7.51   Using the algorithm in §1.7.9, solve for the day of the week of today's date.

Exercise 1.7.52   Using the algorithm in §1.7.9, solve for the day of the week of your birthday.

Exercise 1.7.53   Using the algorithm in §1.7.9, solve for the day of the week of today's date.

Exercise 1.7.54   At the annual Mathematics Department Fun Run, when the joggers lined up 4 abreast there was 1 left over, when the joggers lined up 5 abreast there were 2 left over. How many were at the fun run? (Take the smallest solution to the congruences.)

Exercise 1.7.55   Solve the following problem: If eggs are removed from a basket , , , , and at a time, there remain respectively , , , , and eggs. But if the eggs are removed at a time no eggs remain. What is the least number of eggs that could have been in the basket?

Exercise 1.7.56   A politician runs for office every 6 years and cheats on his taxes every 5 years. He was just elected and cheated on his taxes last year. When is the next time he does both in the same year?

Exercise 1.7.57   At a local triathalon, when everyone lined up 4 abreast there was 1 left over, when everyone lined up 5 abreast there were 2 left over, and when everyone lined up 7 abreast there were 3 left over. How many were at the triathalon? (Take the smallest solution to the congruences.)

Exercise 1.7.58   Show that , in the notation of §1.7.11. Compute , .

david joyner 2008-04-20