Question about modulo of prime numbers (or prime factorization (I guess))

Question

I would like to prove the following:

Let $p$ and $q$ different prime numbers and let $a$ be an integer such that $a < p$ and $a < q$.

I want to prove that $$pq \; | \; a^{pq} - a^p - a^q + a$$

i.e. I would like to prove: $$ \frac{a^{pq} - a^p - a^q + a}{pq} \in \mathbb{Z}$$.

Can any body help me to prove this?

Answer 1

Use lil' Fermat:

Since $p$ is prime, $a^p\equiv a\mod p$, so $a^{pq}-a^p-a^q+a\equiv a^q-a-a^q+a\equiv 0\mod p$

Similarly $a^{pq}-a^p-a^q+a\equiv 0\mod q$.

So $a^{pq}-a^p-a^q+a\equiv 0\mod pq$ by the Chinese remainder theorem.

Answer 2

Show it for p divides the entity and similarly the same argument will hold for q. Now I think using fermats little theorem will help. $ a^{qp} - a^q - (a^p - a)$ will be divided by p.

Answer 3

The other answer is correct that this can be easily solved by Fermat’s Little Theorem. However, you also need a second lemma that went unstated so I’ll state and prove it.

Definition: Let $a,b,c\in\mathbb Z$ such that $a$ is prime. Then $a|bc\Rightarrow a|b$ or $a|c$.

Lemma: Let $p,q\in\mathbb Z$ be distinct primes. Then for all $x\in\mathbb Z$

$$p| x\land q|x\iff pq|x$$

Proof: The $\Leftarrow$ direction is trivial. For the $\Rightarrow$ direction, suppose that $x=kp=\ell q$. Since $q|kp$ and distinct primes don’t divide each other, by the definition of primality we have that $q|k$. Therefore $x=mpq\Rightarrow $pq|x$.