[Math] How prove this $pq|p^{aq}+q^{ap}+a$

number theory

let $p,q$ are prime numbers,show that
for any $(p,q)$,there must exist positive integer numbers $a$,such
$$pq|p^{aq}+q^{ap}+a$$

since I consider this problem,and I found this problem is maybe from this http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1704114&sid=3b8ef31515f3721e84dda4acdff4823f#p1704114

Korean Olympiad Finals (2007-4) problem is this

Find all pairs $ (p, q)$ of primes such that $ p^p+q^q+1$ is divisible by $ pq$.

But for my problem I can't prove it,Thank you,and I think this is nice problem.

Best Answer

It's equivalent to $$q^a+a\equiv0 \pmod p \\p^a+a\equiv0 \pmod q.$$

Lemma 1: If $q^a+a\equiv0 \pmod p$ then $q^{a+kp(p-1)}+a+kp(p-1)\equiv0 \pmod p.$

Lemma 2: If $(p,q)=1$, then $$q^a+a\equiv0 \pmod p$$ has $p-1$ solutions when $1\leq a\leq p(p-1),$ and they are distinct $\mod p-1.$

Proof: Let $1\leq a,b,\leq p(p-1),$ if $a≠b,a\equiv b\pmod {p-1}$ then $q^a+a\not\equiv q^b+b\pmod p$, otherwise we get $a\equiv b\pmod p$, a contradiction.

Hence we can pick $x$ such that $x\equiv (p-1,q-1) \pmod {p-1}$ and $q^x+x\equiv0 \pmod p$.

Also, we can pick $y$ such that $y\equiv (p-1,q-1) \pmod {q-1}$ and $p^y+y\equiv0 \pmod q$.

Case 1: If $(p,q-1)=(q,p-1)=1$, then by Chinese remainder theorem, there exist $a$ such that

$$a\equiv x \pmod {p(p-1)} \\a\equiv y \pmod {q(q-1)}.$$ Then by lemma $1$, we are done.

Case 2: If $p<q$ and $q\equiv1 \pmod p$, then it's equivalent to $$1+a\equiv0 \pmod p \\p^a+a\equiv0 \pmod q.$$ By lemma $2$, we can pick $a\equiv -1\pmod {q-1},$ then $1+a\equiv0 \pmod p$, we are done.

Related Question