Find all the pairs of prime numbers $ (p,q)$ such that $ pq|5^p+5^q.$
Problem
Source: Chinese National Olympiad 2009 P2
Tags: number theory, relatively prime, number theory proposed
10.01.2009 12:30
Let $ p\le q$. If $ p = q$, then $ p^2|25^p\to p = q = 5$. If $ p = 2$, then $ q > 2,q|5^{q - 1} + 5\to q|6\to q = 3$ or q=5. If $ p = 3$, then $ 3|5^{q - p} + 1\to q - p - odd$ contradition with $ q > p$. If $ p = 5$, then $ q|5^{q - 1} + 625\to q|626\to q = 313.$ Let $ 5 < p < q$, then $ pq|5^{p - 1} + 5^{q - 1}$. Let exist minimal $ n = n(p)$, suth that $ p|5^n + 1$, then for all odd m $ p|5^{nm} + 1$ and $ pq|5^p + 5^q\to \frac {q - 1}{n(p)} - odd$. By anology $ \frac {p - 1}{n(q)}$ is integer and odd. If $ p = 3\mod 4$, then for exist $ n(p)$ must be $ (\frac 5p) = - 1\to p = 3,7\mod 20$. But if $ p = 3\mod 4$, then $ n(p)$ odd. For example $ n(7) = 3$. If $ n(p)$ odd $ \frac {q - 1}{n(p)}$ - even. Therefore p,q must be $ 1\mod 4$. If $ ord_2(q - 1) = k$, then $ ord_2(n(p)) = k\to ord_2(p - 1)\ge ord_2(n(p)) + 1\to ord_2(p - 1) > ord_2(q - 1)$. By anology $ ord_2(q - 1) > ord_2(p - 1)$. Therefore thereare not solutions $ p > 5$. All solutions ($ p\le q$) are $ (2,3),(2,5),(5,5),(5,313)$.
11.01.2009 05:17
(p,q)=(2,5) is a solution!
12.01.2009 15:55
If one of the numbers is $ 5$ we get $ 5p \,|\, 5^p + 5^5$ so either $ p = 5$ or $ p \,|\, 626$. So there are the solutions $ \{2,5\}, \{5, 5\}, \{313, 5\}$. If $ p, q \neq 5$ and one of the numbers is $ 2$, we get $ p \,|\, 30$ and only $ p = 3$ works, so there is also the solution $ \{3, 2\}$. So providing $ p, q \not\in \{5, 2\}$, we always get these solutions. Otherwise, we have that $ p$ also divides $ 5^{q-1} + 1$, hence the order of $ 5$ modulo $ p$ divides $ 2(q-1)$ but does not divide $ q - 1$. As this order divides $ p - 1$, it must be that $ \nu_2 (q - 1) < \nu_2 (p - 1)$. The same reasoning applies in the reverse case too, however, so we have no more solutions.
27.07.2009 05:46
Well... I imagined a problem this simple would have a much less trivial solution, but apparently its quite simple: First we try $ (5,5)$ and notice it works. Then we set $ p=5$, $ q\neq 5$ and end up with $ 5q|5^{5}+5^{q}$. Dividing, we get $ q|5^{4}+5^{q-1}$. Placing it in $ mod$ notation we end up with $ 625+5^{q-1}\equiv 0(mod q)$. By Fermat's Little Theorem, $ 626\equiv 0(mod q)$, which gives the solutions $ (5,313)$ and $ (5,2)$. We now work with $ p,q$ relatively prime to $ 5$: $ 5^{p}+5^{q}\equiv 0(mod pq)\Rightarrow 5+5^{q}\equiv 0 (mod p)\Rightarrow 5^{q-1}\equiv -1 (mod p)$. For our next argument we will exclude the case $ p=2$ (we exclude it since, in that case, $ -1\equiv 1 (mod p)$. We have $ 5^{q-1}\equiv -1(mod p)\Rightarrow 5^{2(q-1)}\equiv 1(mod p)$. Similarly, we also have $ 5^{p-1}\equiv -1(mod q)$. Let $ 2^{k}||ord_{p}5$. Then $ 2^{k}||ord_{p}5|p-1$. Also, $ 2^{k}|2(q-1)$, but $ 2^{k}$ does not divide $ q-1\Rightarrow 2^{k-1}||q-1$. Therefore, we have that the maximum power of $ 2$ that divides $ p-1$ is larger than the maximum power of $ 2$ that divides $ q-1$. Doing the same process with $ 5^{p-1}\equiv -1(mod q)$, we get that the maximum power of $ 2$ that divides $ q-1$ is larger than the maximum power of $ 2$ that divides $ p-1$, which contradicts our previous statement. This implies our only option is $ p=2$ (or $ q=2$). In this case, $ 2q|25+5^{q}\Rightarrow 25+5^{q}\equiv 0(mod 2q)$ and, by Fermat's Little Theorem, $ 30\equiv 0(mod 2q)$. The only primes that divide $ 30$ are $ 2$ and $ 3$, and we can easily verify the last congruence is not met when $ q=2$, but is when $ q=3$. Then the only possible pairs are $ (2,3); (5,5); (5,2); (5,313)$.
03.06.2016 00:16
09.05.2020 11:53
bobthesmartypants wrote:
Can you explain, why we get $v_2(ord_q(5))=v_2(2(p-1))$ ?
05.05.2023 09:28
I will post this in English if I know how do we say "阶" in English. 若 $p=q$, 则 $p^2\mid 2\times 5^p\Rightarrow p=q=5$. 下不妨设 $p\neq q$. 若 $p=5$ 或 $q=5$, 设 $p=5$. 则 $q\mid 5^5+5^q\Rightarrow p\mid 5^5+5=2\times 5\times 313\Rightarrow q=2$ 或 $313$. 若 $p=2$ 或 $q=2$, 设 $p=2$. 则 $q\mid 25+5^q\Rightarrow q\mid 25+5=30\Rightarrow q=3$ 或 ${}5$. 若 $p{}$, ${q}$ 中无 $2,5,$ 且 $p\neq q$, 由 $p\mid 5^p+5^q\Rightarrow p\mid 5+5^q$. 因此 $$5^{p-1}\equiv 1\pmod p,5^{q-1}\equiv -1\pmod p.$$因此 ${}{5}$ 模 ${p}$ 半阶存在, 设为 ${d}$. 此时 $q-1$ 为 ${}{d}$ 奇数倍, $\nu _2(q-1)=\nu _2(d)$. 而 $p-1$ 为 ${d}$ 偶数倍, 故 $$\nu _2(p-1)>\nu _2(d)=\nu _2(q-1).$$同理 $\nu _2(q-1)>\nu _2(p-1)$, 矛盾! 综上所述, 所有解为 $$\boxed{(p,q)=(2,3),(3,2),(2,5),(5,2),(5,5),(5,313),(313,5).}\blacksquare$$
06.05.2023 07:27
EthanWYX2009 wrote: I will post this in English if I know how do we say "阶" in English. order.
03.12.2023 07:06
Suppose one of $p$ or $q$ is 2 or 5. We get (what we claim to be) our only solutions: \[\boxed{(2,3),(3,2),(2,5),(5,2),(5,5),(5,313),(313,5)}\] We want to show a contradiction if we assume otherwise. Our condition is equivalent to \begin{align*} &5^q \equiv -5^p \implies 5^{q-1} \equiv -1 \implies 5^{2(q-1)} \equiv 1 \quad \pmod{p} \\ &5^p \equiv -5^q \implies 5^{p-1} \equiv -1 \implies 5^{2(p-1)} \equiv 1 \quad \pmod{q} \\ \\ &\operatorname{ord}_p5 \mid \gcd(p-1,2(q-1)) \quad \pmod p \\ &\operatorname{ord}_q5 \mid \gcd(2(p-1),q-1) \quad \pmod q \\ \end{align*} Note $\operatorname{ord}_p5$ must divide $2(q-1)$ but not $q-1$, and symmetrically for $\operatorname{ord}_q5$, so $v_2$ tells us \begin{align*} v_2(\operatorname{ord}_p5) = v_2(2(q-1)) \leq v_2(p-1) \implies v_2(p-1)-v_2(q-1) \ge 1 \\ v_2(\operatorname{ord}_q5) = v_2(2(p-1)) \leq v_2(q-1) \implies v_2(p-1)-v_2(q-1) \le -1 \\ \end{align*} which is a contradiction. $\blacksquare$
09.12.2023 08:00
The answers are $\{p,q\} = \boxed{\{2,3\}, \{2,5\}, \{5,5\}, \{5,313\}}$, which can easily be checked to work. Now, we prove they are the only ones. If either of $p$ or $q$ equals $5$, WLOG say $q$, we have \[5p \mid 5^5+5^p \implies p \mid 5^4+5^{p-1}\]\[\implies 5^{p-1}+625 \equiv 626 \equiv 0 \pmod{p}.\] Hence, $p=2,313$, but also note that this applies if and only if $p=5$, which also happens to work. If neither of $p$ or $q$ equals $5$, but WLOG $q=2$. Then, we have \[2p \mid 5^p+25 \implies 5^p+25 \equiv 0 \pmod{p},\] if $p$ is odd. This simplifies to $p \mid 30$, so the only new case is $p=3$. If none of the above conditions holds true, we must have \[5^p+5^q \equiv 0 \pmod{p,q}\] by CRT. Considering modulo $p$ first, we get \[5^p+5^q \equiv 0 \pmod{p} \implies 5^{q-1} \equiv -1 \pmod{p}.\] This means that the order of $5$ modulo $p$ divides $2(q-1)$ but does not divide $q-1$. As the order divides $p-1$, it must be that $\nu_2(q-1) < \nu_2(p-1)$. However, the same reasoning applies in modulo $q$, giving $\nu_2(q-1) > \nu_2(p-1)$, a contradiction. Hence, we have shown that no other cases exist, so we are done.
09.01.2024 18:04
Solved with dolphinday. Very very nice problem. Ok we claim that the answers are $(p,q)=(2,3),(2,5),(3,5)$ and $(5,313)$ which can be checked to work (the last with some work). Now, we deal with showing that these are the only solutions. First, note that when $q=2$ we note that \[2p \mid 25(5^{p-2}+1) \implies 5^{2p-4} \equiv 1 \pmod{p}\]By Fermat's Little Theorem, we also have $5^{2p-2} \equiv 1 \pmod{p}$. Thus, $25\equiv 1 \pmod{p}$ which implies that $p=3$. When $q=3$ we do a similar argument as before and show that there are no solutions. When $q=5$ we repeat the exact same process and obtain the possible solutions $(5,5),(5,13)$ and $(5,313)$ of these $(5,13)$ can be checked to not work so we are left with only the desired solutions. We assume that $(p,q)$ is a pair of solutions such that $q\geq 7$. WLOG, assume that $p\geq q$. If $p=q$ then we have \[p^2 \mid 2 \cdot 5^p \implies p=q=5\]Thus, assume that $p>q$. Now, we note that, \[pq \mid 5^q(5^{p-q}+1)\]So, (since $p,q\neq 5$) this implies that, \[pq \mid 5^{p-q}+1\]Thus, $5^{p-q}\equiv -1 \pmod{p}$. This implies that $5^{2p-2q} \equiv 1 \pmod{p}$. We know that by Fermat's Little Theorem, $5^{2p-2} \equiv 1 \pmod{p}$. Thus, \[5^{2q-2} \equiv 1 \pmod{p}\]We also know that by Fermat's Little Theorem, $5^{2q-2} \equiv 1 \pmod{q}$. Since $p$ and $q$ are relatively prime, this implies that \[5^{2q-2} \equiv 1 \pmod{pq}\]With an entirely similar argument, we obtain that \[5^{2p-2} \equiv 1 \pmod{pq}\]This means, $5^{q-1} \equiv \pm 1 \pmod{pq}$ and $5^{p-1} \equiv \pm 1 \pmod{pq}$. But then, \[0 \equiv 5^p+5^q \equiv \pm 5 \pm 5 \pmod{pq}\]Thus, it is quite clear that one of $p,q$ must be $5$ which is a clear contradiction. Thus, there exists no solution in this case and we have found all solutions as required.
08.04.2024 21:32
cursed_tangent1434 wrote: We claim that the answers are $(p,q)=(2,3),(2,5),(3,5)$ and $(5,313)$. $(3,5)$ fails, $(5,5)$ succeeds.
24.04.2024 04:50
$\textbf{Case 1:}$ $p = q$. Then $p^2 \mid 2 \cdot 5^p \implies (p, q) = (5, 5)$. $\textbf{Case 2:}$ One of $p, q$ is $5$. Without loss of generality, assume $p = 5$. Then $q \mid 5^4 + 5^{q - 1}$, so $q \mid 626$. This yields $(p, q) = (5, 2), (5, 313).$ $\textbf{Case 3:}$ $p, q \ne 5$, and are distinct. Without loss of generality, assume $p < q$. Suppose $p \ne 2$. Let $r = \mathrm{ord}_5(p), s = \mathrm{ord}_5(q), a = \nu_2(q - p)$. Since $5^{q - p} \equiv -1 \pmod{p, q}$ but $5^{2(q - p)} \equiv 1 \pmod{p, q}$, we have $\nu_2(r) = a + 1, \nu_2(s) = a + 1.$ But $r \mid p - 1, s \mid q - 1$, so $q - p$ is divisible by $2^{a + 1}$, a contradiction. Now if $p = 2$, we have $2q \mid 5^2 + 5^q$. Clearly the quantity is always even, and we already covered $q = 5$ in the last case so $0 \equiv 1 + 5^{q - 2} \equiv 1 + \frac{1}{5} \equiv \frac{6}{5} \pmod{q}.$ Here $q = 3$ is the only possibility which works, so $(p, q) = (2, 3)$ is a working case. We have exhausted all necessary cases, and all pairs that work are $(5, 5), (5, 2), (5, 313), (2, 3)$ and permutations.