Does there exist a finite set $A$ of positive integers of at least two elements and an infinite set $B$ of positive integers, such that any two distinct elements in $A+B$ are coprime, and for any coprime positive integers $m,n$, there exists an element $x$ in $A+B$ satisfying $x\equiv n \pmod m$ ? Here $A+B=\{a+b|a\in A, b\in B\}$.
Problem
Source: China TST 2019 Test 2 Day 2 Q4
Tags: modular arithmetic, number theory, China TST
lminsl
11.03.2019 14:27
Are there no more constraints-or had I misread the question? A simple(but not easy to confirm) construction could take $A=\{ 1 \}$ and $B=\{ p-1 \mid p\text{ is a odd prime} \}$.
Hamel
11.03.2019 14:30
lminsl wrote: Are there no more constraints-or had I misread the question? A simple(but not easy to confirm) construction could take $A=\{ 1 \}$ and $B=\{ p-1 \mid \text{p is a odd prime} \}$. Isn't direct by Dirichlet?
Taha1381
11.03.2019 14:44
I think he meant rather non-elementry.
lminsl
11.03.2019 14:45
Hamel wrote: lminsl wrote: Are there no more constraints-or had I misread the question? A simple(but not easy to confirm) construction could take $A=\{ 1 \}$ and $B=\{ p-1 \mid \text{p is a odd prime} \}$. Isn't direct by Dirichlet? Yes; I meant the proof of Dirichlet's is quite complicated
Taha1381
11.03.2019 14:52
Does this work?Let $A=\{1\}$ and we are going to construct $B=\{b_1.b_2,\dots \}$ inductivly and we let $b_1=1$.Assume that we have choosen $b_1,b_2,\dots ,b_i$ and we are going to construct $b_{i+1}$.Take the smallest $m+n$ so that there is no element with $x\equiv n \pmod m$ in $A+B$ if there are more than one of them take one randomly and let $b_{i+1}$ to be a number congurent to $n-1$ mod $m$ and $b_{i+1}+1$ is coprime with all previous elements(This can be done by CRT) and put $b_{i+1}$ in $B$ it is clear that the construction works.
SchuesterCHNones
11.03.2019 18:39
Actually The real problem also mentioned A has at least two elements
Dattier
11.03.2019 19:37
for elementary proof of Dirichlet in this case, look here : https://artofproblemsolving.com/community/c6h1755653_elementary_proof_of_a_part_of_dirichlet_results
K_Mirrorheart
12.03.2019 09:31
Quote: for elementary proof of Dirichlet in this case Even in the previous edition of the problem it would require the full strength of Dirichlet.
Taha1381
12.03.2019 14:31
SchuesterCHNones wrote: Actually The real problem also mentioned A has at least two elements Unless I am missing some thing the same method works in here.Let $A=\{ 0, 10! \}$(You can make things natural by just shifting the numbers.) and we are going to construct $B= \{b_1,b_2 ,\dots \}$ inductivly.Let $b_1=1$ assume that we have chosen $b_1,b_2,\dots ,b_n$ and we are going to find $b_{n+1}$ Take smallest $m+t$ so that there is no integer in $A+B$ that satisfies $x\equiv t \pmod m$ until this point(of course$1\le t \le m-1$ and $t$ is coprime to $m$) if $-10! \equiv t \pmod m$ then take $b_n \equiv -2*10! \pmod m$ otherwise take $b_n \equiv t \pmod m$ and take $b_n$ So that non of $b_n$ or $b_n+10!$ has a prime factor appearing before in the sequence(This can be done by CRT).It is obvious that this sets must satisfy the condition.
Loppukilpailija
12.03.2019 15:34
Let $m = 11k$ for some positive integer $k$, and let $t \equiv 1 \pmod{11}$ be some number satisfying $(t, m) = 1$. In addition, choose $t$ such that $-10! \not\equiv t \pmod{m}$. Now, by the above construction, we would choose $b_n \equiv t \pmod{m}$. But now, we necessarily have $b_n \equiv t \pmod{11}$, that is, $b_n \equiv 1 \pmod{11}$. However, $b_n + 10! \equiv 0 \pmod{11}$. This obviously is a problem.
Here's my solution. If you see mistakes, please point out.
Answer: there does not exist such a pair $(A, B)$.
Proof: Proof by contradiction, and let $(A, B)$ be such sets, with $A = \{a_1, a_2, \ldots , a_k\}$.
First, a fundamental lemma.
Lemma 1.
Assuming $(A, B)$ satisfy the conditions of the problem with $|A| = k$, there exists infinitely many $b \in B$ such that the number $a_i + b$ has at least $k$ distinct prime divisors.
Proof of lemma 1.Let $m_1, m_2, \ldots , m_k$ be pairwise coprime numbers with at least $k$ prime divisors each. Let $m = m_1m_2 \ldots m_k$, and let $n$ be chosen such that $n \equiv a_i - a_{i+1} \pmod{m_i}$ for all $i$ (indices are modulo $k$). Now, since $(A, B)$ satisfies the conditions of the problem, there exists $a_i, b$ such that
$a_i + b \equiv n \pmod{m}$
Therefore, $a_i + b \equiv a_i - a_{i+1} \pmod{m_i}$
Now, $a_{i+1} + b \equiv 0 \pmod{m_i}$, which proves the statement.
Let $b$ be an arbitrarily large number satisfying the condition of lemma 1. WLOG. (after suitable relabeling) let the respective $a_i$ be $a_1$.
Let $p_1, p_2, \ldots, p_k$ be distinct primes dividing $b + a_1$. Choose $m = p_1p_2 \ldots p_k$, and $n$ such that
\begin{align*}
n \equiv a_i - a_{i+1} \pmod{p_i}
\end{align*}
for all $1 \le i \le k$, where indices are considered modulo $k$. By CRT, $n$ corresponds to some residue modulo $m$. By assuming that $p_i$ are large enough (that is, larger than $|a_{i+1} - a_i|$ for all $i$), we can guarantee $(m, n) = 1$. To get $p_i$ large, just increase $b$ if necessary: as the elements of $A+B$ are coprime, only finitely many $b' \in B$ may be such that $b' + a_i$ has a "small" prime divisor dividing $|a_{i+1} - a_i|$ for some $i$.
Now, assume there exists some $c \in B$ such that $x = a_i + c$ ($1 \le i \le n$) satisfies $x \equiv n \pmod{m}$. This, in particular, implies
\begin{align*}
a_i + c \equiv a_i - a_{i+1} \pmod{p_i}
\end{align*}This implies $a_{i+1} + c \equiv 0 \pmod{p_i}$, with $a_{i+1} + c \in A + B$. Since the elements of $A+B$ are pairwise coprime, this implies $c = b$, with the $b$ described as above. Additionally, $a_{i+1} + b \equiv 0 \pmod{p_1}$, and $a_1 + b \equiv 0 \pmod{p_1}$ by definition, so $a_{i+1} = a_1$, and therefore $i \equiv 0 \pmod{k}$. That is, $a_1 + b \equiv n \pmod{m}$. Now, $a_1 + b \equiv n \equiv a_1 - a_2 \pmod{p_1}$, and also $a_1 + b \equiv 0 \pmod{p_1}$. This means that $a_1 \equiv a_2 \pmod{p_1}$, which cannot happen for big enough $p_1$. As explained before, we can force the $p_i$ to be as large as we want. This, finally, is a contradiction.
Crystal.
05.04.2019 07:04
lminsl wrote: Are there no more constraints-or had I misread the question? A simple(but not easy to confirm) construction could take $A=\{ 1 \}$ and $B=\{ p-1 \mid p\text{ is a odd prime} \}$. Note that the set A has at least 2 elements!!!!!!!! In fact the answer is no.
guptaamitu1
03.05.2022 03:14
The answer is NO. Assume contrary. Let $A = \{a_1,a_2,\ldots,a_k\}$ (where $k \ge 2$) and $$S = A-A \setminus \{0\} = \{a_i - a_j : i \ne j \}$$Call a positive integer $n > 1$ good if all its prime factors are $>\max(S)$. Claim: All good numbers cannot be in $A+B$. Proof: If not, then for a large prime $p$, a lot of divisors $p$ will be in $A+B$, contradiction. $\square$ Now fix any good $n$ which is not in $A+B$. Key Claim: Arbitrarily large numbers of set $A+B$ are divisible by some element of $n+S$. Proof: Let $$ \lambda = \text{product of all numbers of set } n + S $$Observe that $$ \gcd(n,\lambda) = 1 $$Now for $t \in \mathbb Z^+$ satisfying $\gcd(t,n) = 1$, we take $$ m = t \lambda$$Now some $x \in A+B$ satisfies $$ x \equiv n \pmod{m} $$So for some $b \in B$ and $a_r \in A$ we have that $$ b+a_r \equiv n \pmod{m} \implies b \equiv n - a_r \pmod{m} $$Now elements $b+a_1,b+a_2,\ldots,b+a_k$ lie in $A+B$, and they are congruent to $$ n + (a_1-a_r), \ldots, n , \ldots, n + (a_k - a_r) \pmod{m} $$As $m$ is divisible by all of $n + (a_1 - a_r),\ldots,n + (a_{r-1} - a_r),n + (a_{r+1} - a_r),\ldots,n + (a_k - a_r)$ (note all these elements lie in set $n+S$), so it follows the elements $$ b+a_1,\ldots,b+a_{r-1},b+a_{r+1},\ldots,b+a_k $$are divisible by some elements of $S$. Lastly, as $n \notin A+B$, so taking $t$ large would force $b$ to be large, and hence those elements can be made arbitrarily large. $\square$ From our above Claim, it is easy to some two elements of $A+B$ are not coprime, our desired contradiction. $\blacksquare$