# Prove that $\prod_{i<j} (p_i^{p_j}-p_j^{p_i})$ is divisible by $5777$

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$?

• Are the prime numbers any prime numbers or the first 2017 prime numbers. Can was assume 53 and 109 are among the primes? – fleablood Jan 19 '17 at 0:30
• @fleablood We are given the $2017$ primes, so they aren't necessarily the first $2017$ primes. – Puzzled417 Jan 19 '17 at 0:31
• @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. – John Omielan Apr 22 '19 at 4:20

## 1 Answer

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.

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