13
$\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$
4
  • $\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, 2017 at 0:30
  • $\begingroup$ @fleablood We are given the $2017$ primes, so they aren't necessarily the first $2017$ primes. $\endgroup$
    – Puzzled417
    Jan 19, 2017 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$ Apr 22, 2019 at 4:20
  • 1
    $\begingroup$ Are you only interested in commentary on your approach or are you interested in other approaches? $\endgroup$
    – DanielV
    Feb 21, 2023 at 6:22

4 Answers 4

6
+50
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ In fact, we can simplify it to "For 110 integers $a_i$, $\prod (a_i - a_j ) $ is a multiple of 109 by using PHP on the remainders mod 109, then set $ a_ i = {p_i} ^ { p_i } $. $\quad$ There is no need to reference FLT or cast out small primes. $\endgroup$
    – Calvin Lin
    Feb 25, 2023 at 4:16
  • $\begingroup$ @CalvinLin You're right, it seems that there is no need to throw out the "bad" numbers. I will edit the answer with that remark once I frame it carefully. I am very, very surprised about the downvotes on your answer below, consider flagging for mod attention. $\endgroup$ Feb 26, 2023 at 3:54
  • $\begingroup$ It's unclear to me how $p'$ and $q'$ are generated and you seem to claim that $p^q \equiv q^p$ for any choice of $p,q$, which clearly not true. $\endgroup$
    – Joffan
    Feb 26, 2023 at 8:57
  • $\begingroup$ @Joffan By (suitably extending) Bezout's lemma, if $p$ is coprime to $108$ then there exist positive integers $a,b$ such that $ap-1=108b$ and one can take $p' = a$ so that $pp' \equiv 1 \pmod{108}$. A similar logic yields $q'$ for $q$. The next line claims that if $p^{p'} \equiv q^{q'} \pmod{109}$ then $p^q \equiv q^p \pmod{109}$ provided that $p,q$ don't divide $108$, and this is clear from the explanation on the line after that. Clearly $p^{p'} \equiv q^{q'} \pmod{109}$ need not hold for all $p,q$ but if you take a large enough bunch of them then PHP comes into play. $\endgroup$ Feb 26, 2023 at 9:43
1
$\begingroup$

$\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.

$\endgroup$
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$
3
  • 1
    $\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, 2017 at 0:32
  • $\begingroup$ @Joffan I think it is enough. $p^q \equiv p \pmod q$ if $q$ is prime $\endgroup$
    – D S
    Feb 21, 2023 at 14:35
  • $\begingroup$ What we need is $ p \equiv q \pmod{52}$ in order to definitively conclude that $ p ^ q \equiv p^p \equiv q^p$. EG With $ p = 2, q = 11$, $2^{11} \equiv 2 \pmod{3}$ and $ 11^2 \equiv 1 \pmod{3}$. $\endgroup$
    – Calvin Lin
    Feb 27, 2023 at 17:27
-1
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ Interesting, why all the downvotes? $\endgroup$
    – Calvin Lin
    Feb 25, 2023 at 12:09
  • 2
    $\begingroup$ I think you misread the question. The term in the product should be $p_i ^ {p_j} - p_j ^ {p_i}$. (Look carefully at the exponents) $\endgroup$
    – suncup224
    Feb 26, 2023 at 10:40
  • $\begingroup$ @suncup224 OHHHH. I def missed that. Now, let me fix it...... Thanks! $\endgroup$
    – Calvin Lin
    Feb 26, 2023 at 13:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .