2
$\begingroup$

This is not a hard question, but I am stuck trying to prove the following by induction: Let $\begin{align}C_1&\equiv C^e\pmod n\text{ and}\\ C_{j+1}&\equiv C_j^e\pmod n\end{align}$ for all $j\in\mathbb{N}$, with 0 < C_1 < n and $(e,\phi(n))=1$.

Show that $C_j\equiv C^{e^j}\pmod n$, with 0 < C_j < n.


This is what I have tried:

Base:

$C_1\equiv C^{e^1}\pmod n.$

($j=1$):

$C_2\equiv C_1^e\equiv(C^e)^e\equiv C^{e^2}\pmod n.$

Hence the base case is met.

Step:

$C_{k+1}\equiv C_k^e\pmod n.$

($j=k+1$):

$C_{k+2}\equiv C_{k+1}^e\equiv(C_k^e)^e\equiv C_k^{e^2}\pmod n.$

I get stuck here, however; I do not know how to proceed. How can I finish this proof?

1 Answers 1

1

Step:

$C_{k}\equiv C^{e^k}\pmod n.$

$C_{k+1}\equiv C_{k}^e\equiv(C^{e^k})^e\equiv C^{e^{k+1}}\pmod n.$

  • 0
    You have to assume it for k and prove it for k+12012-04-16