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
    So, in the induction step, do I have to assume what I am trying to prove?2012-04-16
  • 0
    You have to assume it for k and prove it for k+12012-04-16