## Exercises 5.6 Exercises Set 10

###### Investigation Work

###### 1.

Finish all investigations from in-class activities.

###### Computation Based Exercises

###### 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

- \(x^a=x \pmod{14}\) for all \(x\) mod 14.
- \(x^a=x \pmod{26}\) for all \(x\) mod 26.
- \(x^a=x \pmod{34}\) for all \(x\) mod 34.
- \(x^a=x \pmod{38}\) for all \(x\) mod 38.
- \(x^a=x \pmod{46}\) for all \(x\) mod 46.
- Make a conjecture!

###### 4.

Use the Sage code in Sage Computation 5.11.2 to find all \(a\) such that

- \(x^a=x \pmod{15}\) for all \(x\) mod 15.
- \(x^a=x \pmod{21}\) for all \(x\) mod 21.
- \(x^a=x \pmod{33}\) for all \(x\) mod 33.
- \(x^a=x \pmod{39}\) for all \(x\) mod 39.
- \(x^a=x \pmod{51}\) for all \(x\) mod 51.
- 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

- \(x^a=x \pmod{55}\) for all \(x\) mod 55.
- \(x^a=x \pmod{77}\) for all \(x\) mod 77.
- \(x^a=x \pmod{143}\) for all \(x\) mod 143.
- \(x^a=x \pmod{221}\) for all \(x\) mod 221.
- \(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.

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

###### Writing Based Exercises

###### 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!

###### Enrichment Opportunities

###### 18.

Read the article by Diffie-Hellman providing the foundation for public key cryptography `http://ee.stanford.edu/~hellman/publications/24.pdf`

and write a paragraph about something interesting you learned.