Find all positive integers $k$ satisfying: there is only a finite number of positive integers $n$, such that the positive integer solution $x$ of $xn+1\mid n^2+kn+1$ is not unique.
Problem
Source: IMOC 2023 N1
Tags: number theory
09.09.2023 22:13
I claim the answer are all $k\ne 2$. Define the sets $S_{n,k}=\{x:xn+1\mid n^2+kn+1\}$ and $P_k = \{n:|S_{n,k}|\ge 2\}$. I prove that $P_k$ is finite for all $k\ne 2$. Case 1: $k=2$. In this case, we easily see that $1,n+2\in S_{n,2}$ for any $n$. So, $k\ne 2$. Case 2: $k\ne 2$. I now prove that $P_k$ is finite for any $k\ne 1$. Suppose the contrary that there is a $k_0$ for which $|P_{k_0}|=\infty$. We first inspect when $1\in S_{n,k_0}$. We have $n+1\mid n^2+nk_0+1 \Rightarrow n+1\mid 2-k_0$. As $k_0\ne 2$, the number of all such $n$ is finite. That is, there is a $P_{k_0}'\subseteq P_{k_0}$ with $|P_{k_0}'|=\infty$ such that for every $n\in P_{k_0}'$, $1\notin S_{n,k_0}$ and $|S_{n,k_0}|\ge 2$. Note that $xn+1\mid n^2+k_0n+1\Rightarrow xn+1\mid n(n+k_0-x)$, that is $xn+1\mid n+k_0-x$. If $x>n+k_0$ then $xn+1\le x-n-k_0$, a clear contradiction. Next, $n+k_0\in S_{n,k_0}$ clearly. So, suppose $x<n+k_0$. Then, $xn+1\le n+k_0-x$, that is $n(x-1)+x+1\le k_0$. As $1\notin S_{n,k_0}$ and $|S_{n,k_0}|\ge 2$, we have $x\ge 2$ so $n<k_0$ for any such $n$. But as $k_0$ is fixed, this is clearly impossible since $|P_{k_0}'|=\infty$.
13.10.2024 13:30
We wish to find all $k$ such that there are finitely many $n$ for which $n^2+kn+1$ has a divisor, different from $1$ and itself, of the form $xn+1$. (In particular, $1\leq x \leq n+k-1$.) For $k=2$: $n^2+kn+1 = (n+1)^2$ is divisible by $n+1$ for all $n$. Let $k\neq 2$. The main divisibility is equivalent to $xn+1 \mid n^2+kn - xn$ and so (as $xn+1$ and $n$ are coprime) to $xn+1 \mid n+k-x$. The right-hand side is positive, so necessarily $xn+1 \leq n+k-x$, i.e. $n(x-1) \leq k-x-1$. Hence the number of $n$, for which there is a possible $x\geq 2$, is finite, as the left-hand side of the latter is at least $n$, while the right-hand side is at most $k$. For $x=1$ we want $n+1 \mid n+k-1$, i.e. $n+1 \mid k-2$, and for $k\neq 2$ the right-hand side has finitely many divisors, so the amount of possible $n$ is also finite. (As a bonus, we actually showed that for $k\neq 2$ any working $n$ must not exceed $k$.)