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.$$
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.