Find all positive integers $n,k,a_1,a_2,...,a_k$ so that $n^{k+1}+1$ is divisible by $(na_1+1)(na_2+1)...(na_k+1)$
Problem
Source: Kazakhstan National 2019 Problem 4
Tags: number theory, Divisibility
rightways
19.03.2019 20:04
Any solution?
Math1Zzang
20.03.2019 05:19
Let $s=\frac{n^{k+1}+1}{(na_1+1)(na_2+1)...(na_k+1)}$, then $s\equiv 1 \pmod n$, but $s<\frac{n^{k+1}+1}{n^{k}}<n+1$.
Therefore $s=1$, and $n^{k+1}+1=\prod_{i=1}^{k}\left(na_{i}+1\right)$.
If $k=1$, we immediately get $a_{1}=n$.
If $k=2$, we get $n^{3}+1=\left(na_{1}+1\right)\left(na_{2}+1\right)$, which is equivalent to $na_{1}a_{2}+a_{1}+a_{2}=n^{2}$.
So $n|a_{1}+a_{2}$ and $a_{1}a_{2}<n$, therefore $\left(a_{1},a_{2}\right)=(1,n-1),(n-1,1)$.
Now we suppose $k\geq 3$.
If $n=1$, then we easily see there are no further solutions.
If $n=2$, then $k<4$, so $k=3$. We easily see that there are no solutions. Now we suppose $n\geq 3$.
We easily see $\left(1+\frac{1}{n}\right)^{n^2}>n$, so $n^{n^{2}+1}<\left(n+1\right)^{n^{2}}$. Therefore $k<n^{2}$.
If there exists $3$ distinct $i$ such that $a_{i}=1$, then $\left(n+1\right)^3|n^{k+1}+1$.
By some nontrivial operations, we get $\left(n+1\right)^2|k+1$, which means $k\geq n^2+2n$. So contradiction!
Therefore there exists at least $k-2$ distinct $i$ such that $a_{i}\geq 2$.
If $k\geq 5$, we easily see that $a_{1}a_{2}\cdots a_{k}\geq a_{1}+a_{2}+\cdots a_{k}$.
When we evaluate both sides of $n^{k+1}+1=\prod_{i=1}^{k}\left(na_{i}+1\right)$, then $n|a_{1}+a_{2}+\cdots a_{k}$.
This means that $a_{1}a_{2}\cdots a_{k}\geq n$.
But then $n^{k+1}+1=\prod_{i=1}^{k}\left(na_{i}+1\right)>n^{k}a_{1}a_{2}\cdots a_{k}+1\geq n^{k+1}+1$, a contradiction.
$n|a_{1}+a_{2}+\cdots a_{k}$ and $a_{1}a_{2}\cdots a_{k}< n$ applies to the remaining cases $k=3$, $k=4$, too.
If $k=3$, then $n+1\not|n^{4}+1$, therefore $a_{i}\geq 2$ for all $i$. So we easily see there is no solution.
If $k=4$, then after some dirty casework, we see there is no solution.
Therefore the solutions are $\boxed{k=1,a_{1}=n}$ and $\boxed{n\geq 2,k=2,\lbrace{a_{1},a_{2}\rbrace}=\lbrace{1,n-1\rbrace}}$
SmartBeagle
23.12.2020 18:09
can we simply consider the number of times a_i is equal to 1, then using LTE lemma yields the solution immediately. (sorry but i am a new user aops won't let me use latex code)