Set $M$ contains $n \ge 2$ positive integers. It's known that for any two different $a, b \in M$, $a^2+1$ is divisible by $b$. What is the largest possible value of $n$? Proposed by Oleksiy Masalitin
Problem
Source: Ukrainian Mathematical Olympiad 2023. Day 1, Problem 11.1
Tags: number theory, Divisibility
05.04.2023 06:36
$n\geq 3$ fails. Obviously, they are all coprime. $a_1^2+1$ must then be multiple of $a_{2}\dots a_{n}$. If $a_1$ is smallest, then $a_2\dots a_n \geq (a_1+1)^{n-1}>a_1^2+1$ if $n\geq 3$. Thus, it fails. Then, we must need $n=2$, which works by $(2,5)$.
05.04.2023 15:35
LLL2019 wrote: $n\geq 3$ fails. Obviously, they are all coprime. $a_1^2+1$ must then be multiple of $a_{2}\dots a_{n}$. If $a_1$ is smallest, then $a_2\dots a_n \geq (a_1+1)^{n-1}>a_1^2+1$ if $n\geq 3$. Thus, it fails. Then, we must need $n=2$, which works by $(2,5)$. why do you assume that $a_1^2+1$ is a multiple of $a_2...a_n$. the problem states that if $a,b \in M$ it doesn't specify the order.
05.04.2023 15:51
qwertyboyfromalotoftime wrote: LLL2019 wrote: $n\geq 3$ fails. Obviously, they are all coprime. $a_1^2+1$ must then be multiple of $a_{2}\dots a_{n}$. If $a_1$ is smallest, then $a_2\dots a_n \geq (a_1+1)^{n-1}>a_1^2+1$ if $n\geq 3$. Thus, it fails. Then, we must need $n=2$, which works by $(2,5)$. why do you assume that $a_1^2+1$ is a multiple of $a_2...a_n$. the problem states that if $a,b \in M$ it doesn't specify the order. Ofiicial solution assumes that.
06.04.2023 03:57
qwertyboyfromalotoftime wrote: LLL2019 wrote: $n\geq 3$ fails. Obviously, they are all coprime. $a_1^2+1$ must then be multiple of $a_{2}\dots a_{n}$. If $a_1$ is smallest, then $a_2\dots a_n \geq (a_1+1)^{n-1}>a_1^2+1$ if $n\geq 3$. Thus, it fails. Then, we must need $n=2$, which works by $(2,5)$. why do you assume that $a_1^2+1$ is a multiple of $a_2...a_n$. the problem states that if $a,b \in M$ it doesn't specify the order. They are all coprime since $a_i^2+1$ must be multiple of $a_j$, so they cannot both have a common factor $d$. Then, just use the condition for $a_1$ and $a_i$ for each $2\leq i\leq n$ separately and combine.