# Week 6 Problems

Note: you will probably need a computer to solve these problems. Wolfram alpha can do what you need.

1. Find $\phi(n)$ for $n=51,60,100$.

2. Use repeated squaring to check that $2^{100}\equiv 1\pmod{101}.$

3. Let $P=353$ and $Q=359$. These are prime numbers. Let $N=PQ$ and $M=(P-1)(Q-1)$.

• Solve the equation $3x\equiv 1\pmod{M}$ Using Euclid’s algorithm.
• Assume $3$ is the public key and $x$ is the secret key for an RSA system. Encrypt the message “100” using the public key. What is the value of this message?
• Verify that you can decrypt the message using the secret key to obtain “100”.
4. The number $F_5=2^{32}+1=4,294,967,297$ is called the fifth Fermat number. Prove that it is composite by computing $3^{F_{5}-1} mod F_{5}$