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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.