If $p$ and $q$ are distinct primes and $a$ be any integer then $a^{pq} -a^q -a^p +a$ is divisible by $pq$.

If $p$ and $q$ are distinct primes and $a$ be any integer then $a^{pq} -a^q -a^p +a$ is divisible by $pq$.

Factorising we get $a^{pq} -a^q -a^p +a =a^p(a^q -1) - a(a^{q-1}-1)$ and we know $p \mid a^{p-1}-1$ and $q \mid a^{q-1}-1$.

I can't proceed further with the proof. Please Help!

4 Answers

Hint Look at this $\pmod{p}$ and $\pmod{q}$. If you prove that your expression is $0$ in both modular arithmetics, you are done.

$\pmod{p}$ you have $a^p \equiv a \pmod{p}$ therefore you also have $$(a^p)^q \equiv a^q \pmod{p}$$

$\pmod{q}$ you can do a similar computation.

For prime $q,$ $$a^{pq}-a^q-a^p+a=[(\underbrace{a^p})^q-(\underbrace{a^p})]-[a^q-a]$$

Now by Fermat's Little Theorem, $b^q\equiv b\pmod q$ where $b$ is any integer

Set $b=a^p, a$

Similarly for prime $p$

Now if $p,q$ both divides $a^{pq}-a^q-a^p+a,$ the later must be divisible by lcm$(p,q)$

${\bf Hint}\ \ {\rm Assume\ that }\ \ \forall a\!:\ P(a)\equiv a\pmod p$
$\qquad\qquad\qquad\qquad\ \ \ \forall a\!:\ Q(a)\equiv a\pmod q,\$ for polynomials $\,P,Q\in\Bbb Z[x]$

$\text{Then mod }pq\!: R(a) := P(Q(a))-P(a)-Q(a)+a\equiv 0$ ${\rm since}\,\ {\rm mod}\ p\!:\,\ R(a) \ \ \equiv\ \ \ Q(a)\ -\quad a\ \ -\ Q(a)+a\equiv 0$
${\rm and\,\ \ \ mod}\ q\!:\,\ R(a)\ \ \equiv \ \ \ P(a) \ -\ P(a)-\ \ \,a\ \ +\ \, a\equiv 0$

Therefore $\ p,q\mid R(a)\,\Rightarrow\, pq = {\rm lcm}(p,q)\mid R(a)\quad$ QED

The OP is the special case $\ P(a) = a^p,\ \ Q(a) = a^q.$

Hint $\,\ \{a^{pq},a\} \equiv \{a^p,a^q\}$ mod $p,q,\,$ via $\,a^p\equiv a\pmod p,\ a^q\equiv a\pmod q\$ [little Fermat]

Hence $\, a^{pq}\!+\!a \ \equiv\ a^p\! + a^q\,$ mod $\,p,q,\,$ so also mod $\,pq = {\rm lcm}(p,q)$

since addition $\,f(x,y)\, =\, x + y\,$ is $\rm\color{#c00}{symmetric}$ $\,f(x,y)= f(y,x),\,$ therefore its value depends only upon the (multi-)set $\,\{x,\,y\}.\,$

Generally  if a polynomial $\,f\in\Bbb Z[x,y]\,$ is $\rm\color{#c00}{symmetric}$ then

$\qquad\qquad\quad \{A, B\}\, \equiv\, \{a,b\}\,\ {\rm mod}\,\ m,\, n\,\ \Rightarrow\,\ f(A,B)\equiv f(a,b)\, \pmod{\!{\rm lcm}(m,n)}\qquad\quad$

a generalization of the constant-case optimization of CRT = Chinese Remainder, combined with a generalization of the Polynomial Congruence Rule to (symmetric) bivariate polynomials.