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

Question

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

Answer 1

It seems like there are too many pigeons in this problem. We can assume that all the $p_i$ are distinct otherwise for $p_i=p_j, i<j$ the product in question is $0$ hence a multiple of $5777$.

In particular, the idea is to see when two primes $p,q$ satisfy $53 | p^q-q^p$ and $109 | p^q-q^p$ respectively, then transform this accordingly into an argument which allows the use of pigeonhole principle.

Eveerything the OP has done for $53$ fails for $109$ because the problem is that the number of pigeonholes isn't constrained enough while the number of pigeons stays the same.

The idea for both $53$ and $109$ seems to be the following. Suppose, without loss of generality that $p,q$ are two primes such that $p,q$ do not divide $108$ or $109$. In that case, $p,q$ are coprime to $108$ and by Bezout's lemma , we can find non-negative $p',q'$ such that $$pp' \equiv qq' \equiv 1 \pmod{108}$$

Once this is done, then for such $p,q$ as above, the following implication holds : $$ p^{p'} \equiv q^{q'} \pmod{109} \implies p^q \equiv q^p \pmod{109} $$ Indeed, begin with primes $p,q$ coprime to $108,109$ such that $p^{p'} \equiv q^{q'} \pmod{109}$. Then, raise both sides to the power $pq$ to get $$ p^{p'pq} \equiv q^{q'qp} \pmod{109} \tag{1} \label{1} $$

However, by Fermat's little theorem, $p^{108} \equiv 1 \pmod{109}$ because $p \neq 109$. Similarly, $p^{108k+1} \equiv p \pmod{109}$ for any $k \geq 1$. In particular, as $pp' = 108k+1$ for some $k \geq 1$, $$ p^{p'p} \equiv p \pmod{109} \implies p^{p'pq} \equiv p^q \pmod{109} $$

Repeating this with $q$ tells us that $q^{q'qp} \equiv q^p \pmod{109}$. Going back to \eqref{1}, we get to $p^q \equiv q^p \pmod{109}$, as desired.

Therefore, we are reduced to merely looking at $p_i^{p_i'}$ for all $i$ such that $p_i$ is coprime to all of $52,53,108$ and $109$. That's just the primes $2,3,13,53,109$, so taking these out we have at least $2012$ primes to work with.

---

Taking those out, we have $2012$ pigeons, which are $p_i^{p_i'}$ for $i=1,\ldots,2012$. We have only $109$ pigeonholes which are remainders of these quotients modulo $109$. By PHP we can find $i<j$ such that $p_i^{p_{i}'} \equiv p_j^{p_j'} \pmod{109}$. As $p_i,p_j \neq 2,3,13,53,109$, it follows that $p_i^{p_j} \equiv p_j^{p_i} \pmod{109}$ for this choice of $i$ and $j$.

For a possible different choice of $i$ and $j$, but with $53$ instead of $109$, we will get that some $i<j$ exist such that $p_i^{p_j} \equiv p_j^{p_i} \pmod{53}$.

As $5777 = 109 \times 53$ is the product of these two primes, it follows that $5777$ is also a multiple of the product. However, $2017$ seems like an unusually large number of pigeons and it almost seems bewildering to have so many unnecessary pigeons in a "tough" PHP problem. I can't see anything wrong with my solution immediately, though.

Answer 2

$\newcommand{\eqvm}[1]{\underset{\small #1}{\equiv}}$ As already observed, $5777=53\times 109$. We can prove for divisibility of $P_T:=\displaystyle \prod_{i<j} (p_i^{p_j}-p_j^{p_i})$ by $53$ easily and then adapt the method for $109$.

If we have two primes $p$ and $q$ such that both $p \eqvm{53} q$ and $p \eqvm{52}q$, then it is clear from Fermat's Little Theorem that $p^q \eqvm{53} q^p$. If we discard primes $2, 13$ and $53$ (if among the given primes), all other primes are coprime to both $53$ and $52$, meaning a choice of $\phi(53)\phi(52)=52\cdot 24 = 1248$ possible different combination values of $\bmod (53,52)$, and we have at least $2014$ primes to consider, so by the pigeonhole principle we will have $p^q - q^p\eqvm{53} 0$ for some $p,q$ in the set (in fact for hundreds of cases).

If we attempt to use the same process for divisibility by $109$, we end up with $\phi(109)\phi(108)=$ $108\cdot 36 =3888$ pigeonholes; too many for our $2014$ pigeons (since $108=2^23^3$, we may be excluding $2,3$ and $109$ this time, if present).

But we can reduce the number of pigeonholes by considering the multiplicative order of each possible equivalence class $\bmod 109$. $1$ only has one slot available, since $1^j \equiv 1^k$ for any $j,k$. Also $108^j \equiv 108^k$ for any $j,k$ in our permitted primes, since they are all odd. The two order-$3$ values, $\{45,63\}$, create $2$ cases each and likewise the $2$ order-$4$ values $\{76,33\}$. The $2$ order-$6$ values $\{46,64\}$ also have two cases, since all exponents are $1$ or $5 \bmod 6$. The $6$ order-$9$ and $6$ order-$18$ have $6$ cases each, $4$ order-$12$ have $4$ cases, $18$ order-$27$ and $18$ order-$54$ have $18$ cases each, $12$ order-$36$ have $12$ cases and finally the $36$ order-$108$ primitive roots have $36$ cases each. This brings the total pigeonhole count to $1+1+4+4+36+36+16+324+324+144+1296=2190$.

Still too many pigeonholes. However let's look at the primitive root set (order-$109$) $\{6,10,11,13,$ $14,18,24,30,$ $37,39,40,42,$ $44,47,50,51,$ $52,53,56,57,$ $58,59,62,65,$ $67,69,70,72,$ $79,85,91,95,$ $96,98,99,103\}$ a little more and show that we can fill only (at most) half those pigeonholes. So far we have only considering that for $p \eqvm{(109,108)} (p_d,p_o)$ we cannot allow a $q \eqvm{(109,108)} (p_d,p_o)$. However if we consider some other $q \eqvm{(109,108)} (q_d,q_o)$ this may still be ineligible if $p_d^{q_o} \eqvm{109} q_d^{p_o}$. And in fact because we are dealing with only primes which are coprime to $108$, every solution to $p_d^{q_o}$ is a primitive root too and for each $(p_d,p_o)$ there is always a corresponding valid $q_o$ for each of the $35$ other $q_d$ classes $\bmod 108$ in the primitive root set. So for example if we have a prime $p\eqvm{(109,108)} (11,5)$ then $\color{red}{11}^{43} \eqvm{109} 6^{\color{red}5}$, $\color{red}{11}^{103} \eqvm{109} 10^{\color{red}5}$, $\color{red}{11}^{73} \eqvm{109} 13^{\color{red}5}$, etc. So choosing $p\equiv (11,5)$ eliminates choices $(6,43), (10,103), (13,73)$, etc covering all other primitive roots$\bmod 109$. Thus if we chose all $36$ possibilities for $11 \bmod 109$ we would not be able to use any choices at all from other primitive root classes. The best we could hope for is to choose $18$ options for each primitive root which eliminates the other $18$ options for all other primitive roots, giving $18\cdot 36=648$ options and thus we now have more prime pigeons $(2014)$ than available pigeonholes (now $1542$), so $P_T$ is indeed divisible by $109$.

---

---

An "after-proof" thought:

"The best we could hope for" relies on the possibility that the exclusion relation between candidate primes is not transitive, but experimentally this is not the case. In the example for excluded cases from $(11,5)$ above, we find $13^{43} \eqvm{109} 6^{73}$, for example. In fact using $a'$ to denote the multiplicative inverse of $a\bmod 108$, we can see that $p^{q} \eqvm{109} q^{p} \iff p^{p'} \eqvm{109} q^{q'}$. This ensures that exclusion is always transitive and we thus only actually have $36$ "pigeonholes" for the primitive root cases. Likewise using inverses to the multiplicative order of each class in turn, there are only $108$ pigeonholes overall.

Answer 3

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.

Answer 4

We can simplify Sarvesh's approach to proving the following:

Given $n+1$ integers $a_i$, then there is some $i, j$ such that $ n \mid (a_i - a_j)$.

Proof: Consider the remainders of $a_i \pmod{n}$. Since there are $n+1$ terms, and $n$ possible remainders, by PHP 2 of them are the same. Hence $ n \mid a_i - a_j$.

---

Now apply this to $n = 53,$ (resp 109).
If any of the $p_i = 53, 109$, let's ignore them.
Let $a_i = {p_i} ^ { 1/p_i}$, where the rational exponent is interpreted mod 53 (resp 109) so we have an integer. These exist and are well defined in prime modulus as they have a generator. Then, by the above, there is some $i,j$ such that $p_i^{1/p_i} \equiv p_j ^{1/p_j} \pmod{53}$. Raising the expoenets by $p_i p_j$, we get that $ p_i^{p_j} \equiv p_j^{p_i} \pmod{53}$.
Hence, we only need 112 prime numbers to draw the conclusion.

Note: To extend this to all integers

• We exclude multiples of 53 (resp 109). However, if there are 2 or more such multiples, then clearly $ p_i^{p_j} - p_j^{p_i}$ is a multiple of 53.
• The rest hold, and so we do only need 112 integers.