Positive integers $a,b,c$ satisfying the equation $$a^3+4b+c = abc,$$where $a \geq c$ and the number $p = a^2+2a+2$ is a prime. Prove that $p$ divides $a+2b+2$.
Problem
Source: Polish MO 2022 P3
Tags: number theory, prime numbers, modular congruences, Divisibility
13.02.2022 02:21
Interesting. We have $$a\geq c=\frac{a^3+4b}{ab-1}.$$The inequality actually gives us that $a^2b\geq a^3+4b+a>a^3\implies b>a$, which is useful later on. The divisibility gives us that $$ab-1 \mid (a^3+4b)a-4(ab-1)=a^4+4.$$Observe that $p=a^2+2a+2\mid a^4+4$ since $$a^2+2a+2\mid (a^2+2a+2)(a^2-2a+2)=(a^2+2)^2-4a^2=a^4+4.$$Assume that $\gcd(ab-1,p)=1$. Then, we must have $$(ab-1)(a^2+2a+2)\mid a^4+4,$$which cannot be true since $b\geq a+1\implies (ab-1)(a^2+2a+2)\geq a^2(a^2+2a+2)\geq a^4+4$, where equality holds iff $a=1\implies c=1\implies 3b+2=0$, which is absurd. Therefore, $\gcd(ab-1,p)>1\implies p\mid ab-1$. Finally, \begin{align*} p\mid ab-1\implies p\mid (a^2+2a+2)+2(ab-1)=a(a+2b+2). \end{align*}Since $\gcd(a,p)=(a,2)=1$ as $a$ is obviously odd, we conclude that $p\mid a+2b+2$, as desired. $\blacksquare$
13.02.2022 23:04
A bit more straightforward: The equation is equivalent to \[(ab-1)(ac-4)=a^4+4=(a^2-2a+2)(a^2+2a+2)\](classical SFFT+Sophie-Germain). Hence $p \mid ab-1$ or $p \mid ac-4$. However, $0<ac-4<p$ since $c \le a$ whence $p \mid ab-1$. Hence \[p \mid (a^2+2a+2)+2(ab-1)=a(a+2b+2)\]and hence $p \mid a+2b+2$.
31.03.2022 09:13
Nice one Assume $b < a$ then $a^3+4b+c = abc < a^3$ which gives contradiction so $b \ge a$. $a^3+4b+c = abc \implies c(ab-1) = a^3 + 4b \implies c = \frac{a^3+4b}{ab-1} \implies ab-1 \mid a^3 + 4b \implies ab-1 \mid a^4 + 4ab \implies ab-1 \mid a^4 + 4$. Note that $a^4 + 4 = (a^2 + 2a + 2)(a^2 - 2a + 2)$. Now we have $p \mid a^4 + 4$ and $ab-1 \mid a^4 + 4$ so we have $2$ cases : $1) \gcd{(p,ab-1)} = 1$ $(a^2 + 2a + 2)(ab-1) \mid a^4 + 4 \implies a^4 + 2a^3 + 2a^2 \le a^4 + 4 \implies a = 1 \implies c = 1 \implies 4b + 2 = b$ which gives contradiction. $2) \gcd{(p,ab-1)} > 1 \implies p \mid ab-1$ $a^2 + 2a + 2 \mid ab - 1 \implies p \mid a^2 + 2a + 2ab \implies p \mid a(a+2+2b)$ Now assume $p \mid a$ then we have $a^2 + 2a + 2 \ge a$ which gives contradiction so $p \mid a + 2 + 2b$ which is what we want. we're Done.
11.05.2022 20:53
Solved with proxima1681. We first of all start by finding the parity of $a,b,c$. Clearly $a$ must be odd because $p$ is prime. Now one can check that $c$ being odd is forced. The parity of $c$ and $a$ combined gives $b$ even. Rearranging the equation we get \[c(ab-1)=a^3+4b \implies ab-1 \mid a^3+4b\]We now do some algebra do eliminate $b$ from Right-Hand-Side. \begin{align*} ab-1 &\mid a(a^3+4b)-4(ab-1) \\ ab-1 &\mid a^4+4 \\ ab-1 &\mid (a^2+2a+2)(a^2-2a+2) \\ ab-1 &\mid p(a^2-2a+2) \end{align*}We would show that $\gcd(ab-1,p) \ne 1$. Assume for sake of contradiction that $\gcd(ab-1,p) = 1$. Then we get \[ab-1 \mid a^2-2a+2\]We do some more algebra to get \begin{align*} ab-1 &\mid a^2-2a+2 \\ ab-1 &\mid a(a^2-2a+2)-(a^3+4b) \\ ab-1 &\mid -2a^2+2a-4b \end{align*}From here, we divide by 2 on RHS because $ab-1$ is odd. \begin{align*} ab-1 &\mid -a^2+a-2b \\ ab-1 &\mid -a^2+a-2b+(a^2-2a+2) \\ ab-1 &\mid 2b+a-2 \end{align*}Now, one can clearly bound this by $ab-1 \le 2b+a-2 \iff (b-1)(a-2) \le 1$. This restricts $(a,b)$. Only possibilities from this inequality are $(a,b)= (1,b), (3,2)$. Putting $(a,b)=(3,2)$ in original equation yields $c=7$. For $(a,b)=(1,b)$, putting $a=1$ and solving by factoring yields either $(b,c)=(6,5)$ or $(b,c)=(2,9)$. We now write down all solutions. \[(a,b,c)=(1,2,9) \quad (1,6,5) \quad (3,2,7)\]Notice that none of the solutions follow $a \ge c$. This is the desired contradiction. Therefore we now get $\gcd(p,ab-1)=p \implies p \mid ab-1$.The finish is just a little more algebra. \begin{align*} a^2+2a+2 &\mid ab-1 \\ a^2+2a+2 &\mid (a^2+2a+2)+2(ab-1) \\ a^2+2a+2 &\mid a^2+2a+2ab \\ a^2+2a+2 &\mid a(a+2+2b) \end{align*}As $\gcd(a^2+2a+2,a)=1$, we are done. $\blacksquare$
29.10.2024 19:48
Very cool problem. You have to be a bit finicky with the details, hope I didn't mess up anywhere. We start off with the following key claim. Claim : $p$ divides $ab-1$. Proof : We start off by noting that, \begin{align*} a^4 &= (a^2)^2\\ & \equiv (-2a-2)^2 \pmod{p}\\ & = 4(a^2+2a+1)\\ &\equiv -4 \pmod{p} \end{align*}Now, we deal with an important detail. Assume that $p\mid ac-4$. Then, $ac\equiv 4 \pmod{p}$. But if $ac>4$ then \[ac \ge p+4 = a^2+2a+6 > a^2 \ge ac\]which is avery clear contradiction. Thus, if $p\mid ac-4$ we must have $ac=4$. If however, $ac=4$ then, \[a^3+4b+c=abc=4b\]which is a clear contradiction for positive integers $a$ , $b$ and $c$. Thus, $p\nmid ac-4$. Thus, \begin{align*} a^4 & \equiv -4 \pmod{p}\\ a^4 + ac & \equiv ac-4 \pmod{p}\\ a^3 + c & \equiv \frac{ac-4}{a} \pmod{p} \ \ \ \ \ \ (\gcd(a,p)=1 \text{ since } p>2)\\ \frac{a^3+c}{ac-4} & \equiv \frac{1}{a} \pmod{p} \ \ \ \ \ \ \ \ (\gcd(ac-4,p)=1) \end{align*}Further, from $a^3+4b+c=abc$ we also have, \[\frac{a^3+c}{ac-4} = b\]Thus, \[b = \frac{a^3+c}{ac-4} \equiv \frac{1}{a} \pmod{p}\]Thus, $b \equiv \frac{1}{a} \pmod{p}$, which implies the claim. To finish simply note that, \begin{align*} (a+2b+2)a &= a^2+2ab+2a\pmod{p}\\ &\equiv a^2 + 2a\frac{1}{a} + 2a\pmod{p}\\ &\equiv a^2 +2a +1\pmod{p}\\ &\equiv 0 \pmod{p} \end{align*}which since $\gcd(a+1,p)=1$ implies that $p\mid a+2b+2$ as we set out to show.
30.10.2024 16:15
Tintarn wrote: A bit more straightforward: The equation is equivalent to \[(ab-1)(ac-4)=a^4+4=(a^2-2a+2)(a^2+2a+2)\](classical SFFT+Sophie-Germain). Hence $p \mid ab-1$ or $p \mid ac-4$. However, $0<ac-4<p$ since $c \le a$ whence $p \mid ab-1$. Hence \[p \mid (a^2+2a+2)+2(ab-1)=a(a+2b+2)\]and hence $p \mid a+2b+2$. Manipulation seals a great deal for a lot of problems