Find all positive integers, such that there exist positive integers $a, b, c$, satisfying $\gcd(a, b, c)=1$ and $n=\gcd(ab+c, ac-b)=a+b+c$.
Problem
Source: BMO SL 2023 N2
Tags: number theory
03.05.2024 15:25
05.05.2024 22:03
The answer is all odd $n>1$ that don't have a $3\pmod 4$ prime factor. First we show these work. Let $a$ be some even positive integer less than $n$ satisfying $a^2 \equiv -1 \pmod n$. To see this exists notice that since $n > 1$ and $n$ has only $1\pmod 4$ prime factors, there exists an integer $x$ with $x^2 \equiv -1 \pmod n$. Now we can clearly add or subtract $x$ by $n$ as many times as we want, so we can assume $0 < x \le n$ and equality won't hold since $n > 1$. Now if $x$ was odd, we could just take $n - x$ instead. Now let $b = \frac{n + 1 - a}{2}$ and $c = \frac{n - a - 1}{2} = b - 1$. Since $a$ can't equal $n - 1$, $b,c$ are both positive integers. Clearly $a + b + c =n$. Since $b, c$ have difference $1$, $\gcd(a,b,c) = 1$. Now,\[ab + c = (a+1) b - 1 = \frac{n(a+1) - (a^2 + 1)}{2}\]and\[ac - b = (a-1) c - 1 = \frac{n(a-1) - (a^2 + 1)}{2}\]Notice that since $n$ divides $a^2 + 1$, $n$ divides $ab + c$ and $ac - b$. However, $ab + c - (ac - b) = n$, so $\gcd(ab + c, ac - b) = n = a + b + c$, as desired. Now we prove everything else fails. Clearly $n = 1$ fails as you can't find $a,b,c$ where $a +b + c = 1$. Assume $n > 1$. Claim: No $3\pmod 4$ prime divides $n$. Proof: Suppose otherwise. Let $p$ be a $3\pmod 4$ prime dividing $n = a + b+ c$. We have $c \equiv -(a+b)\pmod p$ and $p$ divides both $ab + c$ and $ac - b$. This implies that $ab \equiv a + b \pmod p$ and $a(a+b)\equiv -b \pmod p$. Hence $a \cdot (ab) \equiv -b \pmod p$, so $a^2 b \equiv -b \pmod p$. Notice that if $p$ divided $b$, then $p$ divides $c$, so $p$ also divides $a$, contradicting the fact that $\gcd(a,b,c) = 1$. Hence $a^2 \equiv -1 \pmod p$, which is impossible as $p\equiv 3\pmod 4$. $\square$ Claim: $n$ is odd. Proof: If $n$ was even, then since $a, b, c$ aren't all even, two of them are odd and the other is even. Also, $ab + c$ and $ac - b$ must be even. However if $a$ or $b$ is even, then $ab + c$ is odd and if $c$ is even, then $ac - b$ is odd. $\square$
06.05.2024 20:19