= Solution
Take the positive <integer> $k$ whose existence is allowed by the question and write
$$
3^k=1+t(p-1)(q-1).
$$
Modulo $p$, if $c=0$ then $c^{3^k}=c$ directly. Otherwise <Fermat's little theorem> applies, since $3^k-1$ is a multiple of $p-1$. Hence $c^{3^k}=c\pmod p$. The same two-case argument works modulo $q$. By the <Chinese remainder theorem>,
$$
c^{3^k}\equiv c\pmod n,
$$
so
$$
\boxed{g_k=\gcd(c^{3^k}-c,n)=n.}
$$
This also covers a <ciphertext> that is not <coprime> to $n$; applying <Euler's theorem> without checking that hypothesis would miss this detail. Equivalently, repeated application of a <permutation> on a finite set eventually returns to the starting point, although the arithmetic argument gives the requested sufficient exponent.
Back to article page
