## Exercises5.6Exercises Set 10

Let $p$ be a prime for all of this assignment (and the rest of this book!)
###### 1.

Finish all investigations from in-class activities.

###### 2.

Use Exercise 5.6.10 to construct two different number tricks mod 73. That is, find two different pairs of $s$ and $d$ such that $(x^s)^d \equiv x \pmod{31}$ for all $x$ mod 73.

###### 3.

Use the Sage code in Sage Computation 5.11.2 to find all $a$ such that

1. $x^a=x \pmod{14}$ for all $x$ mod 14.
2. $x^a=x \pmod{26}$ for all $x$ mod 26.
3. $x^a=x \pmod{34}$ for all $x$ mod 34.
4. $x^a=x \pmod{38}$ for all $x$ mod 38.
5. $x^a=x \pmod{46}$ for all $x$ mod 46.
6. Make a conjecture!
###### 4.

Use the Sage code in Sage Computation 5.11.2 to find all $a$ such that

1. $x^a=x \pmod{15}$ for all $x$ mod 15.
2. $x^a=x \pmod{21}$ for all $x$ mod 21.
3. $x^a=x \pmod{33}$ for all $x$ mod 33.
4. $x^a=x \pmod{39}$ for all $x$ mod 39.
5. $x^a=x \pmod{51}$ for all $x$ mod 51.
6. Make a conjecture!
###### 5.

Use the Sage code in Sage Computation 5.11.2 to find all $a$ such that $x^a=x \pmod{35}$ for all $x$ mod 35. (This means try enough values of $a$ until you can identify the pattern. )

###### 6.

Use the Sage code in Sage Computation 5.11.2 to find all $a$ such that

1. $x^a=x \pmod{55}$ for all $x$ mod 55.
2. $x^a=x \pmod{77}$ for all $x$ mod 77.
3. $x^a=x \pmod{143}$ for all $x$ mod 143.
4. $x^a=x \pmod{221}$ for all $x$ mod 221.
5. $x^a=x \pmod{323}$ for all $x$ mod 323.
###### 7.

Use the Sage code in Sage Computation 5.11.2 to find all $a$ such that $x^a=x \pmod{105}$ for all $x$ mod 105. (This means try enough values of $a$ until you can identify the pattern. ) This is a different case from most of your other examples. Why? Can you expand your conjecture to include this case?

###### 8.

Use the Sage code in Sage Computation 5.11.2 to list all $n$ between 6 and 35 where there is NO $a>1$ such that $x^a=x \bmod{n}$ for all $x$ mod n. Make a conjecture!

###### 9.

Use the Sage code in Sage Computation 5.11.2 to answer the following.

1. Can you find an $a>1$ such that $2^a=2 \bmod{9}$ for all $x$ mod 9?
2. Can you find an $a>1$ such that $3^a=3 \bmod{9}$ for all $x$ mod 9?
3. Can you find an $a>1$ such that $4^a=4 \bmod{9}$ for all $x$ mod 9?
4. Can you find an $a>1$ such that $5^a=5 \bmod{9}$ for all $x$ mod 9?
5. Can you find an $a>1$ such that $6^a=6 \bmod{9}$ for all $x$ mod 9?
6. Can you find an $a>1$ such that $7^a=7 \bmod{9}$ for all $x$ mod 9?
7. Can you find an $a>1$ such that $8^a=8 \bmod{9}$ for all $x$ mod 9?
8. What do you notice?
###### 10.

Use Theorem 5.5.8 to prove that if $p$ is a prime and $a=1+(p-1)k$ for an integer $k$ then $x^a \equiv x \pmod{p}$ for all $x\text{.}$ There should be two cases for $x\text{.}$ Case 1: $\gcd(x,p)=1\text{.}$ Case 2: $\gcd(x,p) \neq 1\text{.}$

###### 11.

Write a small program (using a for loop) in Sage with a variable, $p$ for a prime number that checks the factorization of $1+(p-1)k$ for at least 10 different values of $k\text{.}$ For example, the command factor(10) will factor 10 into prime factors. You may initialize $p$ with a prime number of your choice.

###### 12.

Explain how to use Exercise 5.6.10 to construct number tricks mod $p$ for a prime $p\text{.}$ Give an example of creating your own number trick for a prime $p$ of your choice.

###### 13.

In the computational exercises, you explored many cases for when there are values for $a>1$ such that $x^a=x \bmod{n}$ for all $x$ mod $n$ and what the pattern for those $a$ values are when $n$ is not prime. Write up the conjectures you have. Try to combine them into a single conjecture if possible!

###### 14.

Here's a new number trick algorithm. The encryption algorithm is $E(x):y \equiv x^7 \bmod 55\text{.}$ The decryption algorithm is $D(y):x=y^{23} \bmod 55\text{.}$ Explain why the number trick works. (Remember that you found all $a$ such that $x^a \equiv x \bmod 55$ above.)

###### 15.

Recall that $\phi(n)$ counts all the numbers, $a$ between 1 and $n$ such that $\gcd(a,n)=1\text{.}$ Compute $\phi(2*3)\text{,}$ $\phi(2*5)\text{,}$ $\phi(2*7)\text{,}$ $\phi(2*11)\text{,}$ $\phi(2*13)\text{.}$ Make a conjecture for a formula for $\phi(2q)$ where $q$ is an odd prime. Prove it.

###### 16.

Compute $\phi(3*5)\text{,}$ $\phi(3*7)\text{,}$ $\phi(3*11)\text{,}$ $\phi(3*13)\text{.}$ Make a conjecture for a formula for $\phi(3q)$ where $q$ is a prime other than 3. Prove it.

###### 17.

Create your own examples and calculate $\phi(pq)$ when $p>3$ and $q>3$ are distinct primes. Make a conjecture!