An application to Euler's $\phi$-function

Let

$$\Phi_n=\{1\leq a\leq n\ \vert\ gcd(a,n)=1\},$$

as in 1.4.5.

Proposition 1.7.36   If $gcd(m,n)=1$ then there is a 1-1, onto mapping between the sets

$$f:\Phi_m\times \Phi_n \rightarrow \Phi_{mn}.$$

proof: If $a\in \Phi_m$ and $b\in \Phi_n$, then define $f(a,b)=x$, where $x$ satisfies $x\equiv a\ ({\rm mod}\ m), x\equiv b\ ({\rm mod}\ n)$. This $x$ exists and is unique ${\rm mod}\ mn$, by the Chinese remainder theorem, so $f$ is well-defined - provided we show $x\in \Phi_{mn}$. To show this, we must show that $(x,mn)=1$ if $(x,m)=(x,n)=1$, and that if $(a,m)=1$ and $x\equiv a\ ({\rm mod}\ m)$, then $(x,m)=1$. We leave these as exercises.

$f$ is 1-1: If $x=f(a,b)=f(a',b')$ then $x\equiv a\ ({\rm mod}\ m), x\equiv b\ ({\rm mod}\ n)$ and $x\equiv a'\ ({\rm mod}\ m), x\equiv b'\ ({\rm mod}\ n)$. Subtracting, we get $a'\equiv a\ ({\rm mod}\ m), b'\equiv b\ ({\rm mod}\ n)$, so $a=a'$ and $b=b'$ by definition of $\Phi_m$ and $\Phi_n$. Therefore, $f$ is 1-1.

$f$ is onto: Let $x\in \Phi_{mn}$. Define $1\leq a\leq m$ and $1\leq b\leq n$ by $x\equiv a\ ({\rm mod}\ m), x\equiv b\ ({\rm mod}\ n)$. Then, by definition $x=f(a,b)$. Therefore, $f$ is onto. $\Box$

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 $gcd(m,n)=1$ then $\phi(m)\phi(n)=\phi(mn)$.

proof: The number of elements in the range of $f$ is $\phi(m)\phi(n)$ and the number of elements in the domain of $f$ is $\phi(mn)$. Since $f$ is a bijection, these two must be equal. $\Box$

Corollary 1.7.38   If $n=p_1^{e_1}...p_k^{e_k}$ is the prime factorization of an integer $n$ then $\phi(n)=n\cdot (1-1/p_1)(1-1/p_2)...(1-1/p_k)$.

Example 1.7.39   $\phi(100)=100\cdot (1-1/2)(1-1/5)=40$.

Exercise 1.7.40   Verify Example 1.7.39.

Exercise 1.7.41   Define $s_{i+2}=s_{i+1}+s_i\ ({\rm mod 19})$, $s_1=1$, $s_2=1$. Find a formula for $s_i$ as in the above example.

Exercise 1.7.42 (Fibonacci numbers)   Let $s_n$ satisfy $s_n=s_{n-1}+s_{n-2}$ and let $s_1=1,s_2=0$. Solve for $s_n$.

Exercise 1.7.43   Let $s_n$ satisfy $s_{n+3}=s_{n+1}+s_{n}$ and let $s_0=3$, $s_1=0$, $s_2=2$. Solve for $s_n$. (This is the Lucas-Perrin sequence.)

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

Exercise 1.7.45   An internet pyramid scheme starts with a group of $a$ 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 $a$ friends) and forward the email to $N$ others, where $N$ is the number of people on the list. Find the linear recurrence relation which describes this process after $n$ iterations (assuming every email is sent to a different person). First, solve it in terms of $a$ in general. Next, for specific values of $a$ (say $a=3$).

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 $12345$ and recursion equation $s_{5+i}\equiv s_i+s_{i+1}\ ({\rm mod}\ 10)$, $i>0$.

Exercise 1.7.48   Find the first 20 terms of the LFSR with seed $10101$ and recursion equation $s_{5+i}\equiv s_i+s_{i+1}\ ({\rm mod}\ 2)$, $i>0$.

Exercise 1.7.49   A sequence $\{a_n\}_{n=1,2,...}$ is eventually periodic if there are fixed $P>0$ (called the period) and $n_0>0$ such that $a_n=a_{n+P}$,for all $n>n_0$. (If $n_0=0$ 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 $2$, $3$, $4$, $5$, and $6$ at a time, there remain respectively $1$, $2$, $3$, $4$, and $5$ eggs. But if the eggs are removed $7$ 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 $\Phi_{10}=\{1,3,7,9\}$, in the notation of §1.7.11. Compute $\{17 ({\rm mod}\ 10),17\cdot 3 ({\rm mod}\ 10)$, $17\cdot 9 ({\rm mod}\ 10) , 17\cdot 9 ({\rm mod}\ 10)\}$.