Let $m>1$ be an integer. Find the smallest positive integer $n$, such that for any integers $a_1,a_2,\ldots ,a_n; b_1,b_2,\ldots ,b_n$ there exists integers $x_1,x_2,\ldots ,x_n$ satisfying the following two conditions: i) There exists $i\in \{1,2,\ldots ,n\}$ such that $x_i$ and $m$ are coprime ii) $\sum^n_{i=1} a_ix_i \equiv \sum^n_{i=1} b_ix_i \equiv 0 \pmod m$
Problem
Source: 2021 China Mathematical Olympiad P2
Tags: number theory, China
24.11.2020 19:23
I might have overcomplicated by a lot, but here it is.
25.11.2020 12:46
I really admire that solution.
27.11.2020 14:39
Actually, I think I've got another solution. (English is not my mother tongue, so there might be mistakes in the solution, please accept my apology)
02.12.2020 08:56
sketch Let $f(n)$ denote the number of prime factors of $n$. I claim our answer is $2f(m) + 1$. The construction for $2f(m)$ is easy; if we write $m$ in its prime factorized form $p_1^{e_1}\ldots p_{f(m)}^{e_{f(m)}}$ then we can just choose $a_i, b_i$ divisible by $p^{e_i}$ and having $a_{2i-1}b_{2i}, a_{2i}b_{2i-1}$ distinct residues modulo $p$. These clearly exist by CRT, and this leads to all $x_i$ not being relatively prime to $m$. Next, to prove $n = 2f(m) + 1$ works; we can choose $x_i$ so that no prime divides more than two $x_i$. If we ever have three $x_i, x_j, x_k$ divisible by the same prime $p$, then we can transform them to $y_1, y_2, y_3$ still satisfying the probel conditions for which they aren'y all divisible by $p$, so eventually since there are $f(m)$ terms, at most $2f(m)$ are not relatively prime to $m$ so at least one of them is.
30.06.2021 05:28
Denote $m=\prod_{l=1}^{k}p_l^{\alpha_l}$. I have another solution for the part of proving that there exists $x_1,...,x_{2k+1}$ (this means $n \geq 2k+1$). As commented above, it's enough to be able to provide a solution such that for every prime $p_i$, it only divides at most 2 of the $x$'s. Again, we suppose that in a possible solution for the system, there exists $3$ say $x_1,x_2,x_3$ all multiples of $p_1$. Now we claim that it's that it is possible to swap $x$'s to $y$'s (only these ones) in a way that among $y_1,y_2,y_3$ at least one is not divisible by $p_1$ and the number of multiples of $p_k$ remains constant for the rest. By the Chinese Remainder theorem, it's only necessary to find these $y$'s such that: $\sum_{i=1}^3 a_i x_i \equiv \sum_{i=1}^3 a_i y_i (mod p_1^{\alpha_1})$ and the same for b. But realize if we know the power of prime case to the following more generalized version, we're done: Lemma: Given $a_1,a_2,a_3,b_1,b_2,b_3, A,B, k$ constants then there exists $y_1,y_2,y_3$ such that: $\sum_{i=1}^{3}a_ix_i \equiv A (mod p^{k})$ and $\sum_{i=1}^{3}b_ix_i \equiv B (mod p^{k})$. Proof: Induct on $k$: The base case is obvious since it is a $F_p$ is closed for all basic operations we know (multiplication, addition, division and subtraction). Then suppose it's true for $k$ Now we suppose that $A \equiv r_a + p^{k}q_a (mod p^{k+1})$; and similarly for $B$. We' take the solution $x_1,x_2,x_3$ for: $\sum_{i=1}^{3}a_ix_i \equiv r_a (mod p^{k})$ and $\sum_{i=1}^{3}b_ix_i \equiv r_b (mod p^{k})$. and we claim we may find constants $w_1,w_2,w_3$ such that by the translation: $y_i=x_i+w_i\cdot p^{k}$ we would find a solution for the system $mod p^{k+1}$. By plugging on our desired system we get: $\sum_{i=1}^{3}a_i(x_i+w_ip^k) \equiv r_a + q_ap^k (mod p^{k+1})$ $\sum_{i=1}^{3}b_i(x_i+w_ip^k) \equiv r_b +q_bp^k (mod p^{k+1})$ Which becomes: $\sum_{i=1}^{3}a_iw_ip^k) \equiv (r_a - a_1x_1-a_2x_2-a_3x_3)+ q_ap^k (mod p^{k+1})$ $\sum_{i=1}^{3}b_iw_ip^k) \equiv (r_b -b_1x_1-b_2x_2-b_3x_3)+q_bp^k (mod p^{k+1})$ And finally: $\sum_{i=1}^{3}a_iw_i) \equiv (r_a - a_1x_1-a_2x_2-a_3x_3)/p^k+ q_a (mod p)$ $\sum_{i=1}^{3}b_iw_i) \equiv (r_b - b_1x_1-b_2x_2-b_3x_3)/p^k+ q_b (mod p)$ and these w's can be found by the base case. So, as one of the $x_i$ was already non divisible by $p$, then one of the $x_i+w_ip^k$ that satisfy the system module $p^{k+1}$ will also not be divisible by $p$ and we're done.
26.01.2022 18:45
jj_ca888 wrote: sketch Let $f(n)$ denote the number of prime factors of $n$. I claim our answer is $2f(m) + 1$. The construction for $2f(m)$ is easy; if we write $m$ in its prime factorized form $p_1^{e_1}\ldots p_{f(m)}^{e_{f(m)}}$ then we can just choose $a_i, b_i$ divisible by $p^{e_i}$ and having $a_{2i-1}b_{2i}, a_{2i}b_{2i-1}$ distinct residues modulo $p$. These clearly exist by CRT, and this leads to all $x_i$ not being relatively prime to $m$. Next, to prove $n = 2f(m) + 1$ works; we can choose $x_i$ so that no prime divides more than two $x_i$. If we ever have three $x_i, x_j, x_k$ divisible by the same prime $p$, then we can transform them to $y_1, y_2, y_3$ still satisfying the probel conditions for which they aren'y all divisible by $p$, so eventually since there are $f(m)$ terms, at most $2f(m)$ are not relatively prime to $m$ so at least one of them is. I think if u transform $x_i, x_j, x_k$ -> $y_1, y_2, y_3$ , u can reduce multiple of p but another q can increase
29.10.2022 18:05
topfyfwhoami wrote: Actually, I think I've got another solution. (English is not my mother tongue, so there might be mistakes in the solution, please accept my apology)
Can you please explain in detail the final part "For each $1\le i\le n$, such {x_n} exists that no more than two of the numbers are multiples of $p_i$". How to proof that such $x_{i}$ will satisfy the problem?