AoPS - Problem

Idio-logy

24.11.2020 19:23

I might have overcomplicated by a lot, but here it is.

The answer is $2\omega(m) + 1$, where $\omega(m)$ is the number of distinct primes dividing $m$. We say that the integer $n$ is $m$-friendly if it satisfies the conditions. Construction for $2\omega(m)$: write $m = p_1^{k_1} p_2^{k_2} \dots p_t^{k_t}$ and $\omega(m) = t$. For every $s = 1, \dots, t$, let $p_s$ divide all of the $a_i$ and $b_i$'s except for $a_{2s-1}$ and $b_{2s}$. Then $x_{2s-1}$ and $x_{2s}$ must both be divisible by $p_s$, so none of the $x_i$'s are coprime to $m$. Proof for $2\omega(m) + 1$: we first prove the following claim: Claim. For a prime $p$ and a positive integer $k$, $n$ is $p$-friendly iff $n$ is $p^k$-friendly. Proof. The reverse implication is obviously true, so we will prove the forward direction. We want to show that $n$ is $p^k$-friendly, so say that we are given $c_1,\dots,c_n$ and $d_1,\dots,d_n$. Induct on $k$, and we split into four cases: Case 1: The vectors $c=(c_1,\dots,c_n)$ and $d=(d_1,\dots,d_n)$ are linearly independent in $\mathbb{F}_p^n$. By inductive hypothesis, we assume that \[\sum_i c_ix_i \equiv ap^{k-1} \pmod{p^k},\ \ \sum_i d_ix_i \equiv bp^{k-1} \pmod{p^k}.\]Because of our assumption, the matrix \[\left[\begin{matrix} c_1 & c_2 & \dots & c_n \\ d_1 & d_2 & \dots & d_n\end{matrix}\right]\]has rank 2, and the vectors $(c_i,d_i)$ span the space $\mathbb{F}_p^2$. Thus, we can also find $y_1,\dots,y_n$ with $\sum_i a_iy_i \equiv a \pmod{p}$ and $\sum_i b_iy_i \equiv b \pmod{p}$. We can then just take $x_i' = x_i - y_ip^{k-1}$, and \[\sum_i c_ix_i' \equiv ap^{k-1} - ap^{k-1} = 0\pmod{p^k},\ \ \sum_i d_ix_i' \equiv bp^{k-1} - bp^{k-1} = 0 \pmod{p^k}.\]Case 2: The vectors $c$ and $d$ are both zero mod $p$. Notice that we can just divide all $c_i$ and $d_i$ by $p$ to reduce to the inductive hypothesis. Case 3: $c$ is the zero vector, and $d$ is not all zero. Suppose that entry $d_1$ is not zero mod $p$, then by inductive hypothesis, there exist $x_i$ such that \[\sum_i (c_i / p)x_i \equiv \sum_i d_ix_i \equiv 0 \pmod{p^{k-1}}.\]We can then just modify $x_1$ by a suitable multiple of $p^{k-1}$. Case 4: $c$ and $d$ are both nonzero, and $d = \lambda c$ for some nonzero element $\lambda \in\mathbb{F}_p$. In this case, suppose $d_i = \lambda c_i + p\ell_i$. We know that there exist $x_i$ (not all divisible by $p$) such that \[\sum_i c_ix_i \equiv \sum_i \ell_ix_i \equiv 0 \pmod{p^{k-1}}\]Also, let $\sum_i c_ix_i \equiv ap^{k-1} \pmod{p^k}$, and we choose $y_i$ such that $\sum_i c_iy_i \equiv a \pmod{p}$ (this is possible since there exists a nonzero $c_i$). Let $x_i' = x_i - y_ip^{k-1}$. Then \[\sum_i c_ix_i' \equiv 0 \pmod{p^k}\]and \[\sum_i d_ix_i' = \sum_i (\lambda c_i + p \ell_i) x_i' = \lambda \sum_i c_i x_i' + p \sum_i \ell_i x_i' \equiv 0 \pmod{p^k}.\] Having listed all cases, the claim has been proven. $\square$ Back to the original problem. We take the equations mod $p^k$ for each $p^k\mid\mid m$, and by the claim above this is equivalent to just taking mod $p$. The matrix \[M = \left[ \begin{matrix} a_1 & a_2 & \dots & a_n \\ b_1 & b_2 & \dots & b_n\end{matrix}\right]\]is a linear map from $\mathbb{F}_{p}^{2t+1}$ to $\mathbb{F}_{p}^2$, so its kernel has dimension at least $2t-1$, which implies that at most $2$ entries have to be zero. Because there are $t = \omega(m)$ primes dividing $m$, at most $2t$ entries don't work, so there exists an entry that could be coprime to $m$ (we used CRT here).

AFO_tony1107

25.11.2020 12:46

I really admire that solution.

topfyfwhoami

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)

Lemma Let $p$ be a prime number and $\alpha$ be a positive integer. Then, for any $a_1,a_2,a_3,b_1,b_2,b_3\in\mathbb{Z}$, there exists $x_1,x_2,x_3\in\mathbb{Z}$ which can't all be divided by $p$ and $a_1x_1+a_2x_2+a_3x_3\equiv b_1x_1+b_2x_2+b_3x_3\equiv0\ ({\rm mod}\ p^\alpha)$. Proof If all $a_i,b_i\equiv0\ ({\rm mod}\ p)$, then we can divide them all by $p$, so that it turns into the situation of $p^{\alpha-1}$. Thus, we can assume that $a_3\not\equiv0\ ({\rm mod}\ p)$. We can let $x_1,x_2$ be a nontrivial solution to $(a_1b_3-a_3b_1)x_1+(a_2b_3-a_3b_2)x_2\equiv0\ ({\rm mod}\ p^\alpha)$ and $x_3$ be a solution to $a_3x_3\equiv-a_1x_1-a_2x_2\ ({\rm mod}\ p^\alpha)$. Obviously, the first equation does have a nontrivial solution and as $a_3\not\equiv0\ ({\rm mod}\ p)$, the second one must have a solution. Then, we have $x_1,x_2,x_3$ that fits the requirements. Proof! Now, I announce that for $m=\prod_{i=1}^{\omega(m)}{p_i^{\alpha_i}}$, $n_{min}=2\omega(m)+1$. We divide the proposition into two parts: Part1 Prove that $n\ge2\omega(m)+1$. Proof Assume that $n=2\omega(m)$. Let $a_j\equiv b_j\equiv0\ ({\rm mod}\ p_i^{\alpha_i})$ and $a_{2i-1}b_{2i}\not\equiv a_{2i}b_{2i-1}\ ({\rm mod}\ p)$ where $j\ne 2i-1,2i$ for $i=1,2,\cdots,\omega(m)$. According to $CRT$, there exist such numbers. Then, obviously, $x_{2i-1}\equiv x_{2i}\equiv0\ ({\rm mod}\ p_i^{\alpha_i})$, which leads to each $x_i$ not relatively prime with $m$, contradiction. So $n\ge2\omega(m)+1$. Proof! Part2 Prove that there exists ${x_n}$ that fits $n=2\omega(m)+1$. Proof We would prove it by first proving the following lemma. For each $1\le i\le n$, such {x_n} exists that no more than two of the numbers are multiples of $p_i$. The proof is simple. If there are more than three, written as $j,k,l$, we can use the lemma we proved at first to obtain three corresponding numbers $j^*,k^*,l^*$ and replace $j,k,l$ with $j+j^*,k+k^*,l+l^*$. Thus, at least of the three numbers became relatively prime with $p_i$ and the numbers still fit the requirements. Through this operation, we can finally obtain ${x_n}$ with no more than two of them which are nultiples of $p_i$. So, as there are only $\omega(m)$ $i$s, no more than $2\omega(m)$ of ${x_n}$ are not relatively prime with $m$, so proof!

jj_ca888

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.

RodSalgDomPort

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.

nhatminhzzz

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

Dennis1208

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)

Lemma Let $p$ be a prime number and $\alpha$ be a positive integer. Then, for any $a_1,a_2,a_3,b_1,b_2,b_3\in\mathbb{Z}$, there exists $x_1,x_2,x_3\in\mathbb{Z}$ which can't all be divided by $p$ and $a_1x_1+a_2x_2+a_3x_3\equiv b_1x_1+b_2x_2+b_3x_3\equiv0\ ({\rm mod}\ p^\alpha)$. Proof If all $a_i,b_i\equiv0\ ({\rm mod}\ p)$, then we can divide them all by $p$, so that it turns into the situation of $p^{\alpha-1}$. Thus, we can assume that $a_3\not\equiv0\ ({\rm mod}\ p)$. We can let $x_1,x_2$ be a nontrivial solution to $(a_1b_3-a_3b_1)x_1+(a_2b_3-a_3b_2)x_2\equiv0\ ({\rm mod}\ p^\alpha)$ and $x_3$ be a solution to $a_3x_3\equiv-a_1x_1-a_2x_2\ ({\rm mod}\ p^\alpha)$. Obviously, the first equation does have a nontrivial solution and as $a_3\not\equiv0\ ({\rm mod}\ p)$, the second one must have a solution. Then, we have $x_1,x_2,x_3$ that fits the requirements. Proof! Now, I announce that for $m=\prod_{i=1}^{\omega(m)}{p_i^{\alpha_i}}$, $n_{min}=2\omega(m)+1$. We divide the proposition into two parts: Part1 Prove that $n\ge2\omega(m)+1$. Proof Assume that $n=2\omega(m)$. Let $a_j\equiv b_j\equiv0\ ({\rm mod}\ p_i^{\alpha_i})$ and $a_{2i-1}b_{2i}\not\equiv a_{2i}b_{2i-1}\ ({\rm mod}\ p)$ where $j\ne 2i-1,2i$ for $i=1,2,\cdots,\omega(m)$. According to $CRT$, there exist such numbers. Then, obviously, $x_{2i-1}\equiv x_{2i}\equiv0\ ({\rm mod}\ p_i^{\alpha_i})$, which leads to each $x_i$ not relatively prime with $m$, contradiction. So $n\ge2\omega(m)+1$. Proof! Part2 Prove that there exists ${x_n}$ that fits $n=2\omega(m)+1$. Proof We would prove it by first proving the following lemma. For each $1\le i\le n$, such {x_n} exists that no more than two of the numbers are multiples of $p_i$. The proof is simple. If there are more than three, written as $j,k,l$, we can use the lemma we proved at first to obtain three corresponding numbers $j^*,k^*,l^*$ and replace $j,k,l$ with $j+j^*,k+k^*,l+l^*$. Thus, at least of the three numbers became relatively prime with $p_i$ and the numbers still fit the requirements. Through this operation, we can finally obtain ${x_n}$ with no more than two of them which are nultiples of $p_i$. So, as there are only $\omega(m)$ $i$s, no more than $2\omega(m)$ of ${x_n}$ are not relatively prime with $m$, so proof!

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?