5
$\begingroup$

We are given $2017$ prime numbers $p_1,p_2,\ldots,p_{2017}$. Prove that $\displaystyle \prod_{i<j} (p_i^{p_j}-p_j^{p_i})$ is divisible by $5777$.

Note that $5777 = 53 \cdot 109$. We first consider $p_i^{p_j}-p_j^{p_i}$ modulo $53$. We are to prove that \begin{align*}p_i^{p_j} \equiv p_j^{p_i} \pmod{53} \quad \tag{1}\end{align*} for some primes $p_i,p_j$.There exist primes in the list such that $p_i = 53k_1+d,p_j = 53k_2+d$, where $0 \leq d \leq 52$ and $k_1,k_2 > 0$. Then $(1)$ is equivalent to $$d^{53k_1} \equiv d^{53k_2} \pmod{53} \iff d^{53(k_1-k_2)} \equiv 1 \pmod{53}.$$ Now since $53$ is odd, $k_1,k_2$ must be only odd or only even. Then note there are at least $2017-15 = 2002$ such primes $p_i,p_j$ because there are $28$ primes between $0$ and $53$. Therefore, since $\left\lceil\dfrac{2002}{53}\right\rceil = 39$, there exist $p_i,p_j$ such that $k_1 \equiv k_2 \pmod{26}$ and $k_1$ and $k_2$ have the same parity quotient upon division by $26$ and $k_1 > k_2$. Therefore, $$52 \mid 53(k_1-k_2)$$ and so we have found primes $p_i,p_j$ that satisfy $(1)$.

I tried proving divisibility by $109$ using the same argument, but it didn't work:

Now we consider modulo $109$. We are to prove that \begin{align*}p_i^{p_j} \equiv p_j^{p_i} \pmod{109} \quad \tag{2}\end{align*} for some primes $p_i,p_j$. primes in the list such that $p_i = 109m_1+d_1,p_j = 109m_2+d_1$, where $0 \leq d_1 \leq 108$ and $m_1,m_2 > 0$. Then $(2)$ is equivalent to $$d_1^{109m_1} \equiv d_1^{109m_2} \pmod{109} \iff d_1^{109(m_1-m_2)} \equiv 1 \pmod{109}.$$ Now since $109$ is odd, $m_1,m_2$ must be only odd or only even. Then note there are at least $2017-28 = 1989$ such primes $p_i,p_j$ because there are $28$ primes between $0$ and $109$. Therefore, $\left\lceil\dfrac{1989}{109}\right\rceil = 19$.

Is it possible to use the same argument to prove divisibility by $109$?

$\endgroup$
  • $\begingroup$ Are the prime numbers any prime numbers or the first 2017 prime numbers. Can was assume 53 and 109 are among the primes? $\endgroup$ – fleablood Jan 19 '17 at 0:30
  • $\begingroup$ @fleablood We are given the $2017$ primes, so they aren't necessarily the first $2017$ primes. $\endgroup$ – Puzzled417 Jan 19 '17 at 0:31
  • $\begingroup$ @Puzzled417 Unfortunately, you haven't even proven it's true for $53$. This is since "... there exist $p_i,p_j$ such that $k_1 \equiv k_2 \pmod{26}$ and $k_1$ and $k_2$ have the same parity quotient upon division by $26$ and $k_1 > k_2$. Therefore, $52 \mid 53(k_1-k_2)$" isn't necessarily true. For example, let $k_1 = 28$ & $k_2 = 2$. In this case, $k_1 \equiv k_2 \pmod{26}$, have the same parity, but as $k_1-k_2 = 26$, then $52 \not\mid 53(k_1-k_2)$. It's likely whatever method is used to prove it for $109$ can also be used for the $53$ case. I've tried a few things, but no success so far. $\endgroup$ – John Omielan Apr 22 at 4:20
0
$\begingroup$

Hint: Among the 2017 primes, there are a pair which is same modulo 53 and another pair which is same modulo 109. Edit: Even if $p_i$ equals $p_j$ modulo 53, we don't know if $p_i^{p_j}-p_j^{p_i}$ is divisible by 53.

$\endgroup$
  • $\begingroup$ That's not enough, either, because of raising everything to different powers. But it is the start of the trail. $\endgroup$ – Joffan Jan 19 '17 at 0:32

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.