# How to prove by modular arithmetic

Let $p$ and $q$ be distinct primes and let $N=pq$. Let $k=(p-1)(q-1)$. For each e with $\gcd(e,k)=1$, by Proposition 3.5 there is $d$ satisfying $de=1 \pmod k$. Prove that $n^{de}=n \pmod N$ for all $n\in\Bbb{N}$.

Proposition 3.5: Suppose $\gcd(c,m)=1$. If $cx=cy \pmod m$, then $x=y \pmod m$; moreover, for any b, the congruence $cx=b \pmod m$ has a solution, and any two solutions are congruent (mod m).

• What have you tried? Do you know about Fermat's Little Theorem and the Euler-Fermat Theorem? – Teddy38 Sep 29 '17 at 12:59
• I am clueless on how to solve this. Fermat's Little Theorem is in the text but I don't know how to apply it. – user485232 Sep 29 '17 at 13:01
• So, Fermat's Little Theorem says that if $p$ is prime and $p$ does not divide $a$, then $$a^p\equiv a\mod p\ .$$ The Euler-Fermat theorem generalises this to when you don't have a prime, it says that if gcd$(a,n)=1$, then $$a^{\phi(n)}\equiv 1\mod n\ .$$ The first thing to do is make sure that you understand these two results, then see if you can see the connection between them and what you're trying to prove. – Teddy38 Sep 29 '17 at 13:11

A few hints/things you need to notice:

Firstly, if you have that $de \equiv$ $1$ $($ $mod$ $k)$, this means that $de = mk +1$ for some $m \in \mathbb{Z}$

You can now substitute this in to what you're trying to prove.

You now need to work out what $\phi(N)$ is, expressed in terms of $p$ and $q$.

Now, given your previous substitution, notice that if $n$ is co-prime to $N$ you're now practically done, by the Euler-Fermat Theorem.

You then have to figure out what's going on if $n$ is not co-prime to $N$ (IE gcd($n$,$N$) $\neq 1$). In this case $n$ is either a multiple of $p$, a multiple of $q$, or a multiple of both $p$ and $q$.

Summary:

$de \equiv 1 \mod k \iff de = mk + 1$ for $m \in \mathbb{Z}$

Now

$n^{de} \equiv n \mod N \iff n^{mk+1} \equiv n \mod N \iff n*(n^{m})^{k} \equiv n \mod N$ for $m \in \mathbb{Z}$.

and following the hints above, you should probably be able to finish this off.

• If you are going to use Euler's totient function, then what you really want is $n \cdot (n^k)^m$ – DanielV Sep 29 '17 at 15:48