# Tag Info

If $n$ is prime, $\mathbb{Z}_n^{*}$ has a primitive root $g$ and order $n-1$. So if $e$ divides $n-1$ you have $(g^{\frac{n-1}{e}})^e=1$. For $n=11$ you have e.g. the primitive root $g=2$ and therefore with $$b\equiv 2^{10/5}\equiv 2^2 \equiv 4 \pmod {11}$$ you compute $$b^5 \equiv 4^5 \equiv 1024 \equiv 1 \pmod {11}.$$ With the remaining primitive roots $... 7 Claim: If$A$and$Bare coprime, the map \begin{align*} \{0,\dots,B-1\}\ &\to\ \{0,\dots,B-1\} ,\\ x \ &\mapsto\ A\cdot x\bmod B \end{align*} is a well-defined bijection. It is clear directly from the definition of\bmod$that$A\cdot x\bmod B$is indeed between$0$and$B-1$. Surjectivity follows, e.g., from Bézout's lemma. Any surjection ... 6 When choosing the public exponent$e$, if the value chosen is the first coprime after$\phi(n)/2$then the resulting public and private exponents are equal. Well, yeah, that'll always be true. Why does this happen? We have$e=d$whenever we have both of the following true: $$e^2 \equiv 1 \pmod{p-1}$$ $$e^2 \equiv 1 \pmod{q-1}$$ Now, if$e = (...