# RSA Encryption problem for Discrete Math

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly appreciated.

For (a) I got $\mathbb{Z}^*_8 = \{1,2,3,4,5,6,7\}$,

(b) i got $3*3 = 1 \text{ mod } 8 = 3^{-1} = 3$

(c) this one i am not sure how to do

(d) $M = N^d \text{ mod } 15$, i got $d = 3$, so $M = 4^3 \text{ mod } 15 = 4$ • For (a), only elements co-prime to $n$ are in $\mathbb{Z}^*_n$, in other words $x \in \mathbb{Z}^*_n$ iff $gcd(x, n) = 1$. Therefore $Z^*_8 = \{1,3,5,7\}$. You can read more about multiplicative groups here. – puzzlepalace May 9 '16 at 23:17

(a) $\mathbb{Z}_8^* = \{1,3,5,7\}$.

(b) $x = 3$.

(c) Assuming $a \in \mathbb{Z}^*_{15}$: $a^8 \bmod 15 = 1$ and $a^9 \bmod 15 = a$.

(d) $M = 4$.

• can you explain how a^9 mod 15 = a? – spatel May 10 '16 at 1:39
• @spatel: Since $a^8 \equiv 1 \pmod{15}$, it follows that $a^9 \equiv a^8 \cdot a \equiv a \pmod{15}$ and $a \bmod 15 = a$ for $a \in \mathbb{Z}^*_{15}$. – user94293 May 10 '16 at 2:13
• @spatel: More generally, note that $a^9 \equiv a \pmod{15}$ for any $a \in \mathbb{Z}_{15}$ ---the relation $a^8 \equiv 1 \pmod {15}$ assumes $a \in \mathbb{Z}_{15}^*$. – user94293 May 10 '16 at 2:24
• This answer is not quite correct. Note that the question is not $a \in \mathbb{Z}^*_{15}$ but is rather $a \in \mathbb{Z}_{15}$. If we set $a = 5$ for instance we get $5^8 = 10 \text{ mod } 15,$ so not all $a \in \mathbb{Z}_{15}$ are congruent to 1 when raised to the 8th power. – puzzlepalace May 10 '16 at 2:31
• @puzzlepalace: Corrected. Let $a \in \mathbb{Z}_{15}$. If $3$ divides $a$ then $a^8 \bmod 15 = 6$ and if $5$ divides $a$ then $a^8 \bmod 15 = 10$. – user94293 May 10 '16 at 2:38