# How prove this $pq|p^{aq}+q^{ap}+a$

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.

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.

• Hello,can you explain why equivalent to $$q^a+a\equiv 0(mod p),p^a+a\equiv (mod q)$$ – china math Sep 28 '13 at 8:33
• @china math If $(p,q)=1$ then $q^p\equiv q\pmod p,q^{pa}\equiv q^a\pmod p$ – lsr314 Sep 28 '13 at 8:39
• I think you just need to use Chinese Remainder Theorem. – Shane Sep 28 '13 at 10:11

Here is an incomplete attempt at a solution. I am posting it in the hopes that the ideas contained within can be used by someone else to find a complete solution before I can.

Let $p,q$ be fixed primes, and let $f(a)=p^{aq}+q^{ap}+a$. If $S_p=\{a\in \mathbb N \mid f(a)\equiv 0 \pmod p \}$, and similarly for $S_q$, then the problem is equivalent to showing $S_p \cap S_q \neq \emptyset$.

Let us examine $S_p$ more closely. By Fermat's little theorem, $f(a)\equiv 0^{aq} + q^{a}+a \pmod p$. Therefore, if $f(a)\equiv b \pmod p$, then $$f(a+b(p-1)) \equiv q^a (q^{p-1})^b + a -b \equiv q^a (1)^b +a -b \equiv b-b \pmod p,$$ and so we have an effective way of producing (some of the) elements of $S_p$. In particular, this argument shows that $S_p$ must be $(p(p-1))$-periodic in the sense that $p(p-1)+S_p\subset S_p$. Additionally, we have $p-1\in S_p$

By symmetry, $S_q$ is $q(q-1)$-periodic and contains $q-1$. If the linear progressions $(p-1)+p(p-1)\mathbb Z$ and $(q-1)+q(q-1)\mathbb Z$ intersect, then any (positive) element in the intersection will be a solution to the original problem. Unfortunately, I do not currently see why this should be the case, and I need to sleep.