Find the least prime $p$, such that for some positive integers $a$, $b$, $c$, $d$, $(ab + a – b)(bc + b – c)(cd + c – d)(da + d – a) = 2023^2p.$

algebra-precalculuselementary-number-theorypolynomialsprime numbers

Problem

Find the least prime $p$, such that for some positive integers $a$, $b$, $c$, $d$, $(ab + a – b)(bc + b – c)(cd + c – d)(da + d – a) = 2023^2p.$

  • This problem is from the algebra round of a high school math competition that has ended.

My Work

Odd primes work, because if $a=b=c=1$, we will be left with $2d-1 = 2023^2*p$.

To see if $p$ could be 2, we can plug it in!
We have: RHS = $2 \cdot 7^2 \cdot 17^4$.
Therefore, we know that out of the four factors, three have to be odd and one is even.

$$\big((a-1)(b+1)+1\big)\big((b-1)(c+1)+1\big)\big((c-1)(d+1)+1\big)\big((d-1)(a+1)+1\big)= 2 \cdot 7^2 \cdot 17^4$$

Let us say that $((a-1)(b+1)+1)$ is even. $((a-1)(b+1)+1)$ will only be even if both $a$ and $b$ are even. The second term in the equation can not be equal to $1$, but if $c$ and $d$ are equal to $1$, the third and fourth term could be equal to $1$. We can create some cases, and if any case works, $p=2$ would work for the equation.

Case 1: $c=d=1$

In this case, the last two terms of the LHS are 1, which would not affect the product. The second term would simplify into $3b-2$. We can see that $b$ can not be even in this scenario, because then both the first and second term of the LHS would be even, which would not work.

We need two more cases on if $b$ is even or odd.

Is this the correct?

I am having trouble finishing the problem. Could I please receive some help? Thank you.

Best Answer

Here is a possible approach, which collects as many ideas as possible to sieve. Some order is brought into the mess by using a tabular form, when the information can be systematically presented.

It may be that somebody comes up with a really short solution by exploiting the one or the other idea in a cleverer manner or with a complementary new argument. The solution given is the one that i may have written in an Olympiad contest till they would have forced me to submit the many sheets of paper. I am not quite happy with this solution, so i waited till the bounty is over. Let's start.

Let us use the notations: $$ X = 2\cdot 2023^2=2\cdot 7^2\cdot 17^4\ , \\ N(a,b)=ab+a-b=(a-1)(b+1)+1\ . $$ As the OP also mentions, the case of $p=2$ is the only one of interest, so it remains to show:

The product of the four numbers $N(a,b)$, $N(b,c)$, $N(c,d)$, $N(d,a)$ is not $X$ for any choice of integers $a,b,c,d>0$.

Proof:

$\bbox[yellow]{(1)}$ We first observe that $N(a,b)\in\{1,2\}$, i.e. $(a-1)(b+1)\in \{0,1\}$, cannot be realized, since the factor $(b+1)$ is at least two. Same for the other numbers.

$\bbox[yellow]{(2)}$ A further observation concerns the numbers $a,b,c,d$ taken modulo four. At one and exactly one of the four factors is $2$ modulo four. After cyclic replacement, assume it is $N(a,b)=(a-1)(b+1)+1$. So $(a-1)(b+1)=1$ modulo four, so $(a-1)=(b+1)=\pm 1$ modulo four. So $(a,b)$ is either $(0,2)$ or $(2,0)$. And the other two numbers, $c,d$ are not among $0,2$, else we have one more even factor.

So modulo four we have after using the cyclic symmetry one of the patterns $(0,2,\pm1,\pm 1)$ or $(2,0,\pm1,\pm1)$.

$\bbox[yellow]{(3)}$ From $$ %\prod_{\text{cyclic}} (a-1)(a+1) %= \prod_{\text{cyclic}} (a-1)(b+1) < %\prod_{\text{cyclic}} ((a-1)(b+1)+1) %= \underbrace{\prod_{\text{cyclic}} N(a,b)}_{=X=2\cdot 2023^2} %= %\prod_{\text{cyclic}} (ab+a-b) < \prod_{\text{cyclic}} a(b+1) %= %\prod_{\text{cyclic}} (a-1)(a+1) $$ we obtain a useful double inequality: $$ \prod_{\text{cyclic}} (a-1)(a+1) <2\cdot 2023^2 < \prod_{\text{cyclic}} a(a+1)\ . $$ It is handy to use a notation for the product, and their pieces. Let $K(a):=(a-1)(a+1)$, $L(a):=a(a+1)$. We set for pairs the $K$-value and the $L$-value to be $K(a,b):=K(a)K(b)$, $L(a,b):=L(a)L(b)$, and the same for triples, and for the quadruple $(a,b,c,d)$. So: $$K(a,b,c,d)< 2\cdot 2023^2 < L(a,b,c,d)\ .$$

$\bbox[yellow]{(4)}$ The next observation concerns the small(er) factors. At least one of the four factors is $\le X^{1/4}=(2\cdot 7^2)^{1/4}\cdot 17<625^{1/4}\cdot 17=5\cdot 17=85$. The divisors of $X$ in this range are $1,2,7,14,17,34,49$. We may and do assume that $N(a,b)$ is this divisor. For a special choice of $(a,b)$ we denote by $\Pi=\Pi(a,b)$ the value of $N(b,c)\; N(c,d)\; N(d,a)=X/N(a,b)$. Then at least one of these three factors is a divisor $D\ne 1,2$ which is less or equal $\Pi^{1/3}$, and we list the possibilities. Then we tabulate the cases: $$ \scriptstyle \begin{array}{|r|r|l|l|l|l|} \hline N(a,b) & (a-1)(b+1) &(a-1,b+1) & (a,b) & \Pi & D\ :\ D^3\le \Pi \\ \hline 1 & 0 & - & - & - & - \\\hline % 2 & 1 & - & - & - & - \\\hline % 7 & 6 & (3,2)\ (2,3)\ (1,6) & (4,1)\ (3,2)\ (2,5) & 2\cdot 7\cdot 17^4 & 7,\ 14,\ 17,\ 34\\\hline % 14 & 13 & (1,13) & (2,12) & 7\cdot 17^4 & 7,\ 17\\\hline % 17 & 16 & (8,2)\ (4,4)\ (2,8)\ (1,16) & (9,1)\ (5,3)\ (3,7)\ (2,15) & 2\cdot7^2\cdot 17^3 & 7,\ 14,\ 17,\ 34,\ 49\\\hline % 34 & 33 & (11,3)\ (3,11)\ (1,33) & (12,2)\ (4,10)\ (2,32) & 7^2\cdot 17^3 & 7,\ 17,\ 49\\\hline % \color{magenta}{49} & 48 & (24,2)\ (16,3)\ (12,4)\ (8,6)\ (6,8) & \color{red}{(25,1)\ (17,2)\ (13,3)\ (9,5)\ (7,7)} & 2\cdot 17^4 & 17,\ 34\\ & & (4,12)\ (3,16)\ (2,24)\ (1, 48) & \color{red}{(5,11)\ (4,15)\ (3,23)\ (2, 47)} & & \\ \hline % \end{array} $$ The column $(a,b)$ shows possible values for $(a,b)$, realizing the few values for $N(a,b)$. In the last column we have possible $D$-values, which are also in the table in this first column.

$\bbox[yellow]{(5)}$ The case $N(a,b)=\color{magenta}{49}$ is annoying. Let us eliminate it. Assume we can realize it. Let $D'$ be the even factor of $\Pi=X/49=2\cdot 17^4$ among $N(b,c)$, $N(c,d)$, $N(d,a)$. The case $2\cdot 17^4$ is excluded, else the two remained factors are equal to one. The case $2\cdot 17^3$ is excluded, else one of the two remained factors is one.

So there remain only the cases $D'=2\cdot 17=34$, which can be realized by the pairs $\color{blue}{(12,2),\ (4,10),\ (2,32)}$, and $D'=2\cdot 17^2=578=577+1$, and since $577$ is prime we can realize this number only as $\color{blue}{(2,576)}$.

Can $D'$ be $N(b,c)$ or $N(d,a)$, i.e. a factor appearing cyclically immediately before or after $N(a,b)$? We consider the cases:.

  • For $(a,b)=(12,2)$. There is no $(d,a)=(?,12)$ in the red cell. But there is an $(a,b)=(2,47)$ in that red cell. We must examine the case $(d,a,b)=(12,2,47)$. Which leads to $(46c + 47)(13c - 12)=17^3$. The smaller factor $13c-12$ must be either $1$ or $17$. No solution.
  • For $(4,10)$. There is no $(10,?)$ and no $(?,4)$ in the red cell.
  • For $(2,32)$. There is no $(32,?)$ in the red cell. But there is a $(17,2)$ match. We must examine the case $(d,a,b)=(17,2,32)$. Which leads to $(31c + 32)(18c - 17)=17^3$. The smaller factor $18c-17$ must be either $1$ or $17$. No solution.
  • For $(2,576)$. There is no $(576,?)$ in the red cell. But there is a $(17,2)$ match. We must examine the case $(d,a,b)=(17,2,576)$. Which leads to $(575c + 576)(18c - 17)=17^3$. The smaller factor $18c-17$ must be either $1$ or $17$. No solution.

So the red pair $(a,b)$ has no "collision" with the blue pair realizing $D'$, which means that we have all possible $a,b,c,d$ values, obtained by the cartesian product of the red set of all $(a,b)$ with the blue set of all $(c,d)$. We first eliminate the case $(a,b)=\color{red}{(25,1)}$. In this case, $a=25$ leads to the following possible values for $N(d,a)$:

$N(2,25)=1\cdot 16+1=27=3^3$, $N(10,25)=9\cdot 26+1=235=5(\dots)$, $N(32,25)=31\cdot 26+1=807=3(\dots)$, $N(576,25)=575\cdot 26+1=14951$ which is a prime.

In the other cases, we will apply the $K$-test or the $L$-test from $(3)$.

The $K$-test eliminates $(2,576)$, since $K(2,576)=1\cdot 3\cdot575\cdot 577>2\cdot (2023/4)^2 $ So we must pair the blue $(c,d)=(2,576)$ with a red entry with $K$-value $K(a,b)$ smaller than $X/K(2,576)$ thus smaller than $\frac{2\cdot 2023^2}{2\cdot (2023/4)^2}=16$. There is no such a small value, since $\max(a,b)\ge 7$, thus $K(a,b)\ge 5\cdot 7$.

The remained $K$-values and $L$-values are:

$K(12,2)=429$, $K(4,10)=1485$, $K(2,32)=3069$.

$L(12,2)=936$, $L(4,10)=2200$, $L(2,32)=6336$.

$K(17, 2) = 864$, $K(13, 3) = 1344$, $K(9, 5) = 1920$, $K(7, 7) = 2304$, $K(5, 11) = 2880$, $K(4, 15) = 3360$, $K(3, 23) = 4224$, $K(2, 47) = 6624$.

$L(17, 2) = 1836$, $L(13, 3) = 2184$, $L(9, 5) = 2700$, $L(7, 7) = 3136$, $L(5, 11) = 3960$, $L(4, 15) = 4800$, $L(3, 23) = 6624$, $L(2, 47) = 13536$.

We consider the blue values one by one.

  • For $(12,2)$ we have a relatively "small" $L$-value, $L(12,2)=936<2023/2$, so it can be paired with a red $L$-value which must be bigger $4\cdot 2023$. Only $L(2, 47) = 13536$ is big enough. But then $(a,b,c,d)=(2,47,12,2)$ leads to a factor $N(d,a)=N(2,2)=1\cdot 3+1=4=2^2$. Failure.

  • For $(2,32)$ we have a relatively "big" $K$-value, $K(2,32)=3069 > 2023\cdot \frac32$, so it can be paired with a red $K$-value which must be smaller $\frac 43\cdot 2023<\frac 43\cdot 2025=2700$. Only two red pairs do correspond, $(17,2)$ and $(13,3)$. But then $(a,b,c,d)$ is either $(17,2,2,32)$ or $(13,3,2, 32)$, so we have one factor $N(d,a)$ which is either $N(32,17)=559=13\cdot 43$, or $N(32,13)=435=5(\dots)$. Failure.

  • For the remained blue pair, $(4,10)$, the $K$-value is moderate, $1485 >\frac 23\cdot 2023$. It rejects $(2,47)$ with $K$-value bigger $3\cdot 2023$. The $L$-value $L(4,10)=2200$ is also moderate, but better, it rejects red pairs with value smaller $2\cdot 2023^2/2200>2\cdot 2000^2/2500=3200$. So there remain the pairs $(5,11)$, $(4,15)$, $(3,23)$. We compute $N(10,5)=9\cdot 6+1=55=5\cdot 11$ and $N(10,4)=9\cdot 5+1=46=2\cdot 23$ and $N(10,3)=9\cdot 4+1=37$. In each case there is an alien prime involved.

$\bbox[yellow]{(6)}$ After excluding the $49$-case for one and/or any factor, the table of possibilities can be actualized to: $$ \scriptstyle \begin{array}{|r|r|l|l|l|l|} \hline N(a,b) & (a-1)(b+1) &(a-1,b+1) & (a,b) & \Pi & D\ :\ D^3\le \Pi \\ \hline 7 & 6 & (3,2)\ (2,3)\ (1,6) & (4,1)\ (3,2)\ (2,5) & 2\cdot 7\cdot 17^4 & 7,\ 14,\ 17,\ 34\\\hline % 14 & 13 & (1,13) & (2,12) & 7\cdot 17^4 & 7,\ 17\\\hline % 17 & 16 & (8,2)\ (4,4)\ (2,8)\ (1,16) & (9,1)\ (5,3)\ (3,7)\ (2,15) & 2\cdot7^2\cdot 17^3 & 7,\ 14,\ 17,\ 34\\\hline % 34 & 33 & (11,3)\ (3,11)\ (1,33) & (12,2)\ (4,10)\ (2,32) & 7^2\cdot 17^3 & 7,\ 17\\\hline % \end{array} $$ Can this $D$ from the last column be realized by a factor cyclically "near" $N(a,b)$? In other words, can it be that this $D$ is on position $D=N(b,c)$, or on position $D=N(d,a)$? Let us consider all these cases. Such pairs realizing any value of $D$ from the last column are already pairs from the column $(a,b)$ from the table. Can we match two pairs from this column, so that one ends in the number which is the start for the other pair? Recall that matches must satisfy $(2)$.

  • The case $(d,a)$ among $(4,1)$, $(9,1)$, $(3,7)$, $(2,15)$, $(4,10)$, $(2,32)$, there is no $(a,?)$ in the list.
  • The case $(d,a)=(3,2)$ matches $(a,b)=(2,12)$ and $(a,b)=(2,32)$. (We ignore the match $(2,5)$ since after the $2$ there must be something equal to zero modulo four, condition $(2)$.) From $(d,a,b)=(3,2,12)$, resp. $(d,a,b)=(3,2,32)$ we obtain $(11c + 12)(4c - 3)=17^4$, resp. $(31c + 32)(4c - 3)=7\cdot 17^3$. The smaller factor $(4c-3)$ is one modulo four, must be one of the divisors $1$, $17$ in both cases, so $c=1$ or $c=5$, but then the other factor is too small. No solution.
  • The case $(d,a)=(2,5)$ matches only $(a,b)=(5,3)$, and from $(d,a,b)=(2,5,3)$ we obtain $(3c - 2)(2c + 3)=2\cdot7\cdot 17^3$. The bigger factor $3c-2$ must be the even one, so it is at least $2\cdot 17^2$, but then the remained factor is too small to have a ratio of $\approx 3/2$ of the factors. (The ratio is at least two.)
  • The case $(2,12)$ for $N(a,b)=14$ can be paired only with $(12,2)$ from the list. But this is excluded by $(2)$, or by the fact (same thing) that in the line $N(a,b)=14$ we allow only $D=7,17$.
  • The case $(d,a)=(5,3)$ matches only $(a,b)=(3,2)$, (since $(3,23)$ contradicts $(2)$,) and from $(d,a,b)=(5,3,2)$ we obtain $(6c - 5)(c + 2)=2\cdot7\cdot 17^3$. The smaller factor $c+2$ must be the even one, so it is in the list $14, 34$, but then the remained factor is too small to have a ratio of $\approx 3/2$ of the factors. (The ratio is at least two.)
  • The case $(d,a)=(12,2)$ matches only $(a,b)$ equal to $(2,5)$. For $(d,a,b)=(12,2,5)$ we obtain the equation $(13c - 12)(4c + 5)=7\cdot 17^3$. The smaller factor $4c+5$ must be in $(5, 17^2)$, cannot have the factor $7$ by test modulo four, so it is $17$. This gives $c=3$, but then $13c-12=27=3^3$ has alien factors. (Note: There is no match $(2,32)$ since for $N(d,a)=N(12,2)=34$ we are interested in a $D$ among $7, 17$, but $(2,32)$ occurs for $N(2,32)=34$.)

We conclude that $(a,b)$ is one of the pairs in the same name column from the table, and the factor $D$ comes as $N(c,d)$, where $(c,d)$ is also a pair from the same column, since it corresponds to a value $D$ among $7,14,17,34$, and the table covers the possibilities for other names of the variables.

$\bbox[yellow]{(7)}$ Let us arrange now the pairs in columns, by taking the values modulo four: $$ \begin{array}{|c|c||c|c|} \hline 0\text{ and }2 &\pm 1\text{ and }\pm 1 && 0\text{ and }\pm 1 &2\text{ and }\pm 1 & \\\hline (2,12) & (9,1) && (4,1) & (3,2)\\ (12,2) & (5,3) && & (2,5)\\ (4,10) & (3,7) && & (2,15)\\ (2,32) & && &\\\hline \end{array} $$ By $(6)$ $(a,b)$ is one pair in the table, and the $(c,d)$ realizing the $D$ from $(6)$ is an other one. So we have all the possibilities for $(a,b,c,d)$, which is cyclically the same as $(c,d,a,b)$. Moreover, by $(2)$, the pairs $(a,b)$ and $(c,d)$ are taken either from the first two columns, or from the last two columns. And the two pairs come from different columns.

  • We exclude that $(a,b)=(4,1)$ and $(c,d)$ are taken from the last two columns, seeing that $(c,d)=(2,?)$ is not an option, because in $(4,1,2,?)$ the even values are not consecutive, contradicting $(2)$, and in the remained case $(a,b,c,d)=(4,1,3,2)$ the $L$-value is too small. Or by looking at $N(d,a)=N(2,4)=1\cdot 5+1=6=2\cdot 3$ with an alien factor.
  • It remains the case when $(a,b)$ comes from the first column, and $(c,d)$ from the second one. I found it easy to check the $L$-values. In the first column the $L$-values are $L(2,12)=L(12,2)=2\cdot 3\cdot 12\cdot 13=936$, $L(4,10)=4\cdot 5\cdot 10\cdot 11=2200$, $L(2,32)=2\cdot 3\cdot 32\cdot 33=6336$. In the second column $L(9,1)=180$, $L(5,3)=360$, $L(3,7)=672$. So the product is $$L(a,b,c,d)=L(a,b)L(c,d)\le L(2,32)L(3,7)<7000\cdot 700=4900000 <2\cdot 2000^2<X\ . $$ This contradicts $(3)$.

This concludes the solution.

$\square$

Related Question