1
$\begingroup$

I want to solve the following problem:

Let $d$ and $e$, both natural numbers, be each others inverses modulo $\varphi(n)$, where $n = p\cdot q$ is a product of two different prime numbers $p$ and $q$. Let $M = \{0,1,2,\dots,(n-1)\}$ be the set of nonnegative numbers smaller than $n$. Define two functions $f: M \rightarrow M$ and $g: M \rightarrow M$ as \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)) = x$ and $g(f(x))= x$ for all $x \in M$.

I understand that $f(x)$ and $g(x)$ will always produce numbers between 0 and $n$, since $x$ is smaller than $n$. In that respect, $f(x) = g(x)$ no matter what $e$ and $d$ we choose.
But I don't understand why $f(g(x)) = x$ and $g(f(x))= x$.

$\endgroup$
1
$\begingroup$

One has $ed=k\varphi(n)+1$ for some integer $k$ because $ed\equiv 1\pmod{n}$. So if $\gcd(x,n)=1$, we can write bearing in mind that $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=x$$

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, I see. Very elegant. But how can you know that $\gcd(x,n) = 1$? $\endgroup$ – SBS Oct 20 '16 at 19:59
  • $\begingroup$ Yes you're right it is only valid for those $x$ such that $\gcd(x,n)=1$ $\endgroup$ – marwalix Oct 20 '16 at 20:07
0
$\begingroup$

I think I figured it out. First I have to prove that $x^{k\varphi(n) + 1} \equiv x \pmod{n}$, even when I don't know if $\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} Since $q$ and $p$ 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*} 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*} Thus, a solutions to the set of congruences above is \begin{align*} y = x^{k\varphi(n) + 1} \end{align*} By the Chinese Remainder Theorem, this solution is unique modulo $p\cdot q =n$. Thus, \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*}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.