Let $\mathbb N$ denote the set of all natural numbers. Show that there exists two nonempty subsets $A$ and $B$ of $\mathbb N$ such that $A\cap B=\{1\};$ every number in $\mathbb N$ can be expressed as the product of a number in $A$ and a number in $B$; each prime number is a divisor of some number in $A$ and also some number in $B$; one of the sets $A$ and $B$ has the following property: if the numbers in this set are written as $x_1<x_2<x_3<\cdots$, then for any given positive integer $M$ there exists $k\in \mathbb N$ such that $x_{k+1}-x_k\ge M$. Each set has infinitely many composite numbers.
Problem
Source: India TST 2016 Day 4 Problem 3
Tags: number theory, set, prime numbers
rkm0959
22.07.2016 11:54
I think this works. Let $A$ be the set of squarefree numbers and $1$. Let $B$ be the set of square numbers. I will show that this works. 1. $A \cap B = \{1\}$. This is absolutely trivial. 2. Of course, if $n=\prod p^{e_i}_i$, we can just write it as $( \prod p^{\lfloor \frac{e_i}{2} \rfloor}_i)^2 \cdot \text{squarefree terms}$. 3. Trivial. 4. This on set $B$ is trivial. For set $A$, we can set up $x+i \equiv 0 \pmod{p^2_i}$ and by CRT we are okay. 5. Trivial.
RedRising
22.07.2016 11:56
Wow, it really works! It seems so simple now. The long text discouraged me...
Ankoganit
22.07.2016 12:00
@rkm0959 Point 2 is even more trivial. If $n\in A$, write $n=n\cdot 1$, otherwise $n=1\cdot n$. I don't know how this became the last problem of the last TST.
rkm0959
22.07.2016 12:02
No, because $A \cup B \not= \mathbb{N}$..
Ankoganit
22.07.2016 12:06
Oops, I misread. Actually my construction was: $B=$all perfect squares, $A=$everything else along with $1$. This works as well.
BOBTHEGR8
19.05.2020 18:35
Wow why is this problem a Day 4 P3 Just let $A=\{1,2,2^2-1,2^3-1,...\}$ and $B=\{1\}\cup\{\mathbb{N}-A\}$ Now all properties are trivially true . 1) Trivial 2)Just take that number and $1$ 3)For $p=2$, it's obvious , for odd prime we have $p|2^{p-1}-1\in A$ and $2p \in B$ 4)This trivial on set $A$ as the gap between consecutive numbers increases exponentially 5)For $B$ just take powers of $2$ and for $A$ note that $2^{2k}-1$ is composite for all $k>1$
Loppukilpailija
19.05.2020 19:38
One sees that, informally, a "random" choice of $A$ and $B$ should work: For each integer $n > 1$, flip a coin to decide whether $n \in A$ or $n \in B$, and also let $1 \in A, 1 \in B$. Now claims 1 and 2 hold surely and claims 3, 4 and 5 hold almost surely. As one can set up a probability measure for partitions of $\{2, 3, \ldots \}$ to two subsets, this proof can be made rigorous. Thus, the problem can be solved without actually constructing such $A$ and $B$.