Find all pairs of prime numbers $p,\,q(p\le q)$ satisfying the following condition: There exists a natural number $n$ such that $2^{n}+3^{n}+\cdots+(2pq-1)^{n}$ is a multiple of $2pq$.
Problem
Source: KJMO 2019 p3
Tags: number theory, prime numbers, KJMO
09.01.2021 01:28
Let’s note $p,q$ are odd. we need to find $n$ so that $1+2^n+...+(2pq)^n-1$ is a multiple of $2pq$. At first, $1+2^n+...+(2pq)^n-1$ is a multiple of $2$, that is $1+3+...+(2pq-1)$ is even, but $1+3+...+(2pq-1)=1+(2pq-1)+3+(2pq-3)+...+(pq-2)+(pq+2)+pq$, but $pq$ is odd, so we have divisibility by two. Thus, $p,q$ are odd. we need to find $n$ so that $1+2^n+...+(2qp)^n-1$ is a multiple of $p$. $1+2^n+...+(2qp)^n-1\equiv 2q(1+2^n+...+p^n)-1$ mod $p$ $2q(1+2^n+...+p^n)-1\equiv 2q(g^n+...+(g^n)^{p-1})-1$ where g is a generator mod p $2q(g^n+...+(g^n)^{p-1})-1\equiv 2q\frac{g^{pn}-1}{g^n-1}-1$ This number leaves either $-2q-1$ mod $p$ if $p-1|n$ or $-1$ mod $p$ in other cases. Hence, $p|2q+1$.By the same reasoning $q|2p+1$. If $p\neq 2q+1$, then $p<q$, because $\frac{2q+1}{3}<q$. By the same reasoning if $q\neq 2p+1$, then $q<p$. Therefore, wlog $p=2q+1$. $q|2(2q+1)+1$ $q|3$ Since $q$ is a prime $q=3$, then $p=7$.
09.01.2021 03:37
We have no solution neither for $(p,q)$ nor $n$. Note firstly that we are dealing with $2(pq-1)$ integers with same numbers of even and odd numbers. Then if at least $p$ or $q=2$ we get: $2 \nmid 2^{n}+3^{n}+\cdots+(2pq-1)^{n}$ Then all $two$ $numbers$ must be $odd.$ Now it suffice to prove that $pq$ don't divide the given expression. $Lemme :$ For every positif integer $n \not= k.\phi(pq)= k.(p-1)(q-1),$ $k$ a natural number and $\phi$ the number of integer coprime with $pq$ and less than $pq$, we get: $1^n + 2^n+...+(pq-1)^n\equiv 0 \mod (pq)$ $Proof:$ By induction, for $n=1$ we get : $(1+pq-1) + (2+pq-2)...+(\frac{pq+1}{2} + \frac{pq-1}{2} )\equiv 0 \mod (pq)$ Suppose for every $n>1$ that the assertion is true et to demonstrate for $n+1$ we must pose: $$[1^n + 2^n+...+(pq-1)^n][ 1+ 2+...+(pq-1)] \equiv 0 \mod (pq)$$ $$\implies [1^{n+1} + 2^{n+1}+...+(pq-1)^{n+1}] + \frac{p(p-1)}{2}[ 1+ 2+...+(pq-1)] \equiv 0 \mod (pq)$$ $$\implies 1^{n+1} + 2^{n+1}+...+(pq-1)^{n+1} \equiv 0 \mod (pq)$$$ \boxed{} $ Returning to the expression, we observe that before $pq$ we get $ pq -2 $ integers numbers and after $pq - 1.$ So we observe that at the left side of $ pq $ the number $1^n$ misses. Then we get unfortunatly : $$2^n+...+(2pq-1)^n\equiv -1 \mod (pq)$$ So no solution is possible because we don't get condition to apply the lemme.
09.01.2021 08:49
I'm sorry, $p\le q$ was missing.
09.01.2021 09:20
pixi wrote: $2q(g^n+...+(g^n)^{p-1})-1\equiv 2q\frac{g^{pn}-1}{g-1}-1$ This number leaves either $-1$ mod $p$ if $p-1|n$ or $2q-1$ mod $p$ in other cases. Hence, $p|2q-1$.By the same reasoning $q|2p-1 $. These two conditions mean that either $p<q$ and $q<p$, since they are odd, or $p=2q-1$. You almost got the right solution, but $$2q(g^n+...+(g^n)^{p-1})-1\equiv 2q\frac{g^{pn}-g^n}{g^n-1}-1$$leaves $-1 (\bmod\,p)$ if $p-1\nmid{n}$ or $-2q-1(\bmod\,p)$ if $p-1\mid{n}$ (because $g^n+...+(g^{n})^{p-1}\equiv p-1(\bmod p)$. Hence, $p\mid 2q+1$ and by the same reasoning $q\mid 2p+1$ Because $p\le q$, $q\le 2p+1\le 2q+1<3q$, and both $p$ and $q$ are odd, $q=2p+1$. $p\mid 2q+1=2(2p+1)+1$, $p\mid 3$. Therefore, $p=3$ and $q=7$ is the only answer. $Note$: $2^n+3^n+\cdots+(2pq-1)^n$ is a multiple of $2pq$ when $p-1$ and $q-1$ both divide $n$
09.01.2021 12:24
Sorry for my incorrect solution. Next contribution will be well studied.
18.01.2021 12:03
Rama12 wrote: pixi wrote: $2q(g^n+...+(g^n)^{p-1})-1\equiv 2q\frac{g^{pn}-1}{g-1}-1$ This number leaves either $-1$ mod $p$ if $p-1|n$ or $2q-1$ mod $p$ in other cases. Hence, $p|2q-1$.By the same reasoning $q|2p-1 $. These two conditions mean that either $p<q$ and $q<p$, since they are odd, or $p=2q-1$. You almost got the right solution, but $$2q(g^n+...+(g^n)^{p-1})-1\equiv 2q\frac{g^{pn}-1}{g-1}-1$$leaves $-1 (\bmod\,p)$ if $p-1\nmid{n}$ or $-2q-1(\bmod\,p)$ if $p-1\mid{n}$ (because $g^n+...+(g^{n})^{p-1}\equiv p-1(\bmod p)$. Hence, $p\mid 2q+1$ and by the same reasoning $q\mid 2p+1$ Because $p\le q$, $q\le 2p+1\le 2q+1<3q$, and both $p$ and $q$ are odd, $q=2p+1$. $p\mid 2q+1=2(2p+1)+1$, $p\mid 3$. Therefore, $p=3$ and $q=7$ is the only answer. $Note$: $2^n+3^n+\cdots+(2pq-1)^n$ is a multiple of $2pq$ when $p-1$ and $q-1$ both divide $n$ Thank you, I fixed my solution:) But I got that pair $(3,5)$ and $n=2k+1$ satisfy, is it wrong? And why did you write that $2q(g^n+...+g^{n(p-1)})-1\equiv -1$ mod $p$ if $n$ isn’t divisible by $p-1$? I thought $2q(g^n+...+g^{n(p-1)})\equiv 2q(\frac{g^{np}-1}{g^n-1})-1\equiv 2q-1$
18.01.2021 14:08
Oh, I(actually we..) miscalculated $g^n+\cdots +g^{n(p-1)}$. It starts from $g^n$, not $1$. $$g^n+\cdots +g^{n(p-1)}=\frac{g^{np}-g^n}{g^n-1}$$So, if $p-1\nmid n$, we get $g^{n(p-1)}\equiv 1$ $\implies g^n+\cdots +g^{n(p-1)}\equiv \frac{g^{np}-g^n}{g^n-1}\equiv 0(\bmod p)$ Also, you may check that $p=3, q=5, n=3$ doesn't satisfy the condition.
18.01.2021 20:42
@above oh, I see, thank you!