1. Encryption relies on numerous results about modular arithmetic. [9 pts] Prove in prose Fermat’s Little Theorem: If 𝑝

[answerhappygod]

1. Encryption relies on numerous results about modulararithmetic.
[9 pts] Prove in prose Fermat’s Little Theorem: If 𝑝 is anyprime number and 𝑎 is any integer such
that𝑝∤𝑎,then𝑎𝑝−1 ≡1(mod𝑝).
[6 pts] Suppose you are encrypting the message 𝑀 = 6 usingpublic key (55,17). Show that the
cyphertext is 41.