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
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} \}$.
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?
11.03.2019 14:44
I think he meant rather non-elementry.
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
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.
11.03.2019 18:39
Actually The real problem also mentioned A has at least two elements
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
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.
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.
12.03.2019 15:34
Here's my solution. If you see mistakes, please point out.
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.
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$