Show that f(g(x))=xf(g(x)) = x and g(f(x))=xg(f(x))= x, with f(x)=xemodnf(x) = x^e \bmod n and g(x) = x^d \bmod ng(x) = x^d \bmod n

I want to solve the following problem:

Let dd and ee, both natural numbers, be each others inverses modulo \varphi(n)\varphi(n), where n = p\cdot qn = p\cdot q is a product of two different prime numbers pp and qq. Let M = \{0,1,2,\dots,(n-1)\}M = \{0,1,2,\dots,(n-1)\} be the set of nonnegative numbers smaller than nn. Define two functions f: M \rightarrow Mf: M \rightarrow M and g: M \rightarrow Mg: M \rightarrow M as
\begin{align*}
f(x) = x^e \bmod n \quad \mbox{and}\quad g(x) = x^d \bmod n
\end{align*}\begin{align*}
f(x) = x^e \bmod n \quad \mbox{and}\quad g(x) = x^d \bmod n
\end{align*}
Show that f(g(x)) = xf(g(x)) = x and g(f(x))= xg(f(x))= x for all x \in Mx \in M.

I understand that f(x)f(x) and g(x)g(x) will always produce numbers between 0 and nn, since xx is smaller than nn. In that respect, f(x) = g(x)f(x) = g(x) no matter what ee and dd we choose.
But I don’t understand why f(g(x)) = xf(g(x)) = x and g(f(x))= xg(f(x))= x.

=================

1

 

Introduction to RSA? Hint: en.wikipedia.org/wiki/Euler%27s_theorem. – But f(x)=g(x)f(x)=g(x) is wrong.
– Martin R
Oct 20 at 18:52

  

 

Here is an explanation: math.stackexchange.com/questions/20157/rsa-in-plain-english.
– Martin R
Oct 20 at 18:54

  

 

We’re gonna start learning about RSA next week, so maybe there’s a connection, yes.
– SBS
Oct 20 at 20:00

=================

2 Answers
2

=================

One has ed=k\varphi(n)+1ed=k\varphi(n)+1 for some integer kk because ed\equiv 1\pmod{n}ed\equiv 1\pmod{n}. So if \gcd(x,n)=1\gcd(x,n)=1, we can write bearing in mind that x^{\varphi(n)}\equiv 1\pmod{n}x^{\varphi(n)}\equiv 1\pmod{n}

f(g(x))=x^{ed}=x^{k\varphi(n)+1}=\left(x^{\varphi(n)}\right)^k\cdot x^1=xf(g(x))=x^{ed}=x^{k\varphi(n)+1}=\left(x^{\varphi(n)}\right)^k\cdot x^1=x

Similarly we prove that g(f(x))=xg(f(x))=x

When \gcd(x,n)\gt 1\gcd(x,n)\gt 1 it doesn’t work as shown by the example n=4n=4, x=2x=2, e=1e=1 and d=3d=3.

  

 

Ah, I see. Very elegant. But how can you know that \gcd(x,n) = 1\gcd(x,n) = 1?
– SBS
Oct 20 at 19:59

  

 

Yes you’re right it is only valid for those xx such that \gcd(x,n)=1\gcd(x,n)=1
– marwalix
Oct 20 at 20:07

I think I figured it out. First I have to prove that x^{k\varphi(n) + 1} \equiv x \pmod{n}x^{k\varphi(n) + 1} \equiv x \pmod{n}, even when I don’t know if \gcd(x,n) = 1\gcd(x,n) = 1.

We look at the system
\begin{align}
\begin{cases}
y \equiv x \pmod p \\
y \equiv x \pmod q
\end{cases}
\end{align}\begin{align}
\begin{cases}
y \equiv x \pmod p \\
y \equiv x \pmod q
\end{cases}
\end{align}
Since qq and pp are two different prime numbers, they are relatively prime to eachother. Then we have
\begin{align*}
&\varphi(n) = \varphi(p)\cdot \varphi(q)
\end{align*}\begin{align*}
&\varphi(n) = \varphi(p)\cdot \varphi(q)
\end{align*}
and so, by Eulers theorem,
\begin{align*}
&x^{k\varphi(n) + 1} = (x^{\varphi(p)})^{k\varphi(q)} \cdot x \equiv 1^{k\varphi(q)} x \equiv x \pmod{p}\\
&x^{k\varphi(n) + 1} = (x^{\varphi(q)})^{k\varphi(p)} \cdot x \equiv 1^{k\varphi(p)} x \equiv x \pmod{q}
\end{align*}\begin{align*}
&x^{k\varphi(n) + 1} = (x^{\varphi(p)})^{k\varphi(q)} \cdot x \equiv 1^{k\varphi(q)} x \equiv x \pmod{p}\\
&x^{k\varphi(n) + 1} = (x^{\varphi(q)})^{k\varphi(p)} \cdot x \equiv 1^{k\varphi(p)} x \equiv x \pmod{q}
\end{align*}
Thus, a solutions to the set of congruences above is
\begin{align*}
y = x^{k\varphi(n) + 1}
\end{align*}\begin{align*}
y = x^{k\varphi(n) + 1}
\end{align*}
By the Chinese Remainder Theorem, this solution is unique modulo p\cdot q =np\cdot q =n. Thus,
\begin{align*}
x^{k\varphi(n) + 1} \equiv x \pmod{n}
\end{align*}\begin{align*}
x^{k\varphi(n) + 1} \equiv x \pmod{n}
\end{align*}
Then, I can apply the solution as proposed by marwalix, namely
\begin{align*}
&f(g(x)) = x^{ed} = x^{k\varphi(n) + 1} \equiv x \pmod{n}\\
&g(f(x)) = x^{de} = x^{k\varphi(n) + 1} \equiv x \pmod{n}
\end{align*}\begin{align*}
&f(g(x)) = x^{ed} = x^{k\varphi(n) + 1} \equiv x \pmod{n}\\
&g(f(x)) = x^{de} = x^{k\varphi(n) + 1} \equiv x \pmod{n}
\end{align*}