Using Fermat's Little Theorem with a complicated polynomial exponent I am to prove that if:

*

*$p$ and $q$, two distinct odd primes

*$N = pq$

*$a$ is an integer such that $gcd(a,N)=1$
Then...
$a^{(p-1)(q-1)+1} ≡ a(mod N) $
My idea was to use Fermat's little theorem to somehow break down the exponent but I was at a roadblock because how do we use Fermat with something like $a^{N - p - q +2} ≡ a(mod N) $
My second idea was to say that b/c of what we're given we can say that $(p-1)(q-1)+1≡ 1(mod (p-1)(q-1))$
but I wasn't sure what to do with that either.
Would appreciate a hint or two!
 A: Your idea to use Fermat's little theorem can work to prove the result. First, $\gcd(a,N) = 1 \implies \gcd(a,p) = 1$. Thus, by Fermat's little theorem, we get
$$\begin{equation}\begin{aligned}
a^{p-1} & \equiv 1 \pmod{p} \\
(a^{p-1})^{q-1} & \equiv 1^{q-1} \pmod{p} \\
a^{(p-1)(q-1)} & \equiv 1 \pmod{p} \\
a\left(a^{(p-1)(q-1)}\right) & \equiv a(1) \pmod{p} \\
a^{(p-1)(q-1) + 1} & \equiv a \pmod{p}
\end{aligned}\end{equation}\tag{1}\label{eq1A}$$
Similarly, we also get $a^{(p-1)(q-1) + 1} \equiv a \pmod{q}$. Since $\gcd(p,q) = 1$, with $N = pq$, this means
$$a^{(p-1)(q-1) + 1}  \equiv a \pmod{N} \tag{2}\label{eq2A}$$
Alternatively, as stated in J. W. Tanner's question comment, using Euler's totient theorem instead, since $\varphi(pq) = (p - 1)(q - 1) \implies a^{(p-1)(q-1)} \equiv 1 \pmod{pq}$, would make the solution shorter & more direct than using Fermat's little theorem as shown above.
A: Your idea is just fine and mostly done.
Hint:  $a^{(p-1)(q-1) + 1} = (a^{p-1})^{q-1}a = (a^{q-1})^{p-1} a$.
So $a^{(p-1)(q-1) + 1}\equiv (a^{p-1})^{q-1}a\equiv 1^{q-1} a \equiv a \pmod p$ by FLT.
And $a^{(p-1)(q-1) + 1}\equiv (a^{q-1})^{p-1}a\equiv 1^{p-1} a \equiv a \pmod q$ by FLT.
So by CRT there is a unique solution $ \pmod{N=pq}$ to $x \equiv a \pmod p$ and $x \equiv a \pmod q$ and obviously $a\equiv a \pmod N$ so whatever the solution is it must be equivalent to $a \pmod N$.
......
Or we could use Euler's The.  $\phi(N=pq) = (p-1)(q-1)$ so if $\gcd(a,N) = 1$ then $a^{(p-1)(q-1)+1} \equiv a \pmod N$.
And if $\gcd(a,N)\ne 1$.  Oh, well I guess we have cases.
$\gcd(a,N) =$ either $p$ or $q$ or $N$.  If $\gcd(a,N) = N$ then $N|a$ and $a\equiv 0$ and the result is trivial.  If $\gcd(a,N)=p$ then .... tedious... but minor... can use CRT for that.
Oh.... it was a condition that $\gcd(a,N) = 1$..... so I guess they included the require because the expected you to use Euler's.  By FLT and CRT the condition is not necessary.
