Using Fermat's Little Theorem with a complicated polynomial exponent

Question

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!

Answer 1

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.

Answer 2

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.