TITLE: How to prove by modular arithmetic
QUESTION [0 upvotes]: 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).

REPLY [1 votes]: 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.
{"set_name": "stack_exchange", "score": 0, "question_id": 2450385}