Suppose that in an RSA algorithm, we have the public key $(n,e)$ where $n = 2413, e = 323$.
(a) Given that $2413 = 19 \times 127$, find the private key $(n,d)$.
(b) Explain why $(x^e)^{\hat d} \equiv x \mod n$ for all $x$ with $\gcd(x,n) = 1$ and $\hat d \equiv 71 \mod 126$.
My Try: (a) Given that $2413 = 19 \times 127$, we have $\phi(n) = 18 \times 126$.
Also using Euclidean Algorithm we found that $d = 323$. Hence the private key is $(2413,323)$.
(b) Since $\gcd(x,n) = 1$ if we can show that $e \times \hat d \equiv 1 \mod \phi(n)$, then we are done.
Given that $\hat d \equiv 71 \mod 126$, we have $\hat d = 126k+71$ for some integer $k$.
Thus we have $e \times \hat d = 323 \times (126k+71) = 17 \times 19 \times (126k+71) = (18-1) \times (18+1) \times (126k+71)$
Hence we have $e \times \hat d = (18^2 -1) \times (126k+71)$.
I am unable to proceed after this. Can someone provide some hints?
Thanks.
In the context of RSA, observe that $$x^{e\hat{d}} \equiv x \pmod{pq} \Leftrightarrow \begin{align*}x^{e\hat{d}} & \equiv x \pmod{p}\\ x^{e\hat{d}} &\equiv x \pmod{q}\end{align*}$$ So if we can show that $$\begin{align*}e\hat{d} & \equiv 1 \pmod{p-1}\\ e\hat{d} &\equiv 1 \pmod{q-1}\end{align*},$$ then we are done.
In your question, we should show that $$\begin{align*}e\hat{d} & \equiv 1 \pmod{18}\\ e\hat{d} &\equiv 1 \pmod{126}\end{align*}.$$ For the second congruence, with $\hat{d}\equiv 71 \pmod{126}$, it is easy to see that $(323)(71) \equiv 1 \pmod{126}$.
Note that $126 \equiv 0 \pmod{18}$. So if the second congruence holds, then by transitivity ($18$ divides $126$ and $126$ divides $e\hat{d}-1$ etc.), the first congruence will hold as well.