Determine all positive integers $(x_1,x_2,x_3,y_1,y_2,y_3)$ such that $y_1+ny_2^n+n^2y_3^{2n}$ divides $x_1+nx_2^n+n^2x_3^{2n}$ for all positive integer $n$.
Problem
Source: 2022 Korea Winter Program Practice Test
Tags: number theory, Divisibility
28.10.2024 12:34
We'll prove that $(x_1,x_2,x_3) = (y_1,y_2,y_3)$. Claim 1: $x_1 = y_1$. Proof: Because $4y_1-1 >0$, we know that there are infinitely many prime numbers $p$ such that $(\frac{1-4y_1}{p})=1$ therefore we have $\exists n_0: (2n_0+1)^2 \equiv 1-4y_1\mod p \rightarrow {n_0}^2+n_0+y_1 \equiv 0 \mod p$. Now by CRT setting $n \equiv 0 \mod p-1 , n \equiv n_0 \mod p$ we get $y_1 + n{y_2}^n +n^2{y_3}^{2n} \equiv y_1 + n + n^2 \equiv 0 \mod p $ and so we have $p| y_1 + n{y_2}^n +n^2{y_3}^{2n} | x_1 + n{x_2}^n +n^2{x_3}^{2n} \rightarrow 0 \equiv x_1 + n{x_2}^n +n^2{x_3}^{2n} \equiv x_1 + n + n^2 \equiv x_1 + n_0 + {n_0}^2 \equiv x_1 - y_1 \mod p$. Since this is true for infinitely many $p$, we have $x_1 = y_1$. Claim 2: $x_2 = y_2$ , $x_3 = y_3$ Proof: The idea is quite similar. Let $a_i = \frac{{y_2}^i}{2{y_3}^i}$. By picking $i$ large enough we can insure that $\exists b: y_1 \neq {a_b}^2 \rightarrow 4y_1{y_3}^{2b} \neq {y_2}^{2b}$ and so there exists infinitely many prime numbers $p$ such that $(\frac{{y_2}^{2b}-4y_1{y_3}^{2b}}{p})=1 \rightarrow \exists n_b: (2n_b{y_3}^{2b} + {y_2}^{b})^2 \equiv {y_2}^{2b}-4y_1{y_3}^{2b} \mod p \rightarrow {n_b}^2{y_3}^{2b} + n_b{y_2}^b + y_1 \equiv 0 \mod p$. Now by CRT there exists $n$ such that $n \equiv b \mod p-1$ , $n\equiv n_b \mod p$ and so we get that $y_1 + n{y_2}^n +n^2{y_3}^{2n} \equiv {n_b}^2{y_3}^{2b} + n_b{y_2}^b + y_1 \equiv 0 \mod p \rightarrow p|y_1 + n{y_2}^n +n^2{y_3}^{2n}|x_1 + n{x_2}^n +n^2{x_3}^{2n} \rightarrow 0\equiv x_1 + n{x_2}^n +n^2{x_3}^{2n} \equiv x_1 + n{x_2}^b +n^2{x_3}^{2b}$. Let $f(n) = y_1 + n{y_2}^b +n^2{y_3}^{2b}$,$g(n) = x_1 + n{x_2}^b +n^2{x_3}^{2b}$. We've proved that if $p|f(n) \rightarrow p|g(n)$ and since $f(x)$ isn't a perfect square, it has the same two roots with $g(x)$. hence we have $\exists c: cf(x) \equiv g(x) \mod p$ but $x_1 = y_1$ so $c\equiv 1 \mod p$ and so $f(x) \equiv g(x) \mod p \rightarrow {y_2}^b \equiv {x_2}^b \mod p , {x_3}^{2b} \equiv {y_3}^{2b} \mod p$ and this is true for infinitely many $p$ therefore ${x_2}^b = {y_2}^b \rightarrow x_2 = y_2$ and ${x_3}^{2b} = {y_3}^{2b} \rightarrow x_3 = y_3$.