Let $A$ be a finite set made up of prime numbers. Determine if there exists an infinite set $B$ that satisfies the following conditions: $(i)$ the prime factors of any element of $B$ are in $A$; $(ii)$ no term of $B$ divides another element of this set.
Problem
Source: Brazil EGMO TST2 2023 #2
Tags: number theory, Sets, prime numbers
30.01.2024 02:23
YLG_123 wrote: $(ii)$ no term of $B$ divides another element of this set. which set does this refer to
30.01.2024 05:32
jasperE3 wrote: YLG_123 wrote: $(ii)$ no term of $B$ divides another element of this set. which set does this refer to to B
30.01.2024 12:07
Such $B$ doesn't exist. It's just an instance of DiŃkson lemma.
30.01.2024 15:33
I believe it can be solved instantly by using induction .
30.01.2024 15:58
To elaborate on #4, Let $\lvert A \rvert=n$. Then, an element in B with the prime factorisation $p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_n^{e_n}$ can be expressed as the $n$-tuple $(e_1,e_2,\cdots, e_n)$. These tuples may be given a pointwise order, in which $(a_1,a_2,\cdots, a_n) \leq (b_1,b_2,\cdots, b_n)$ iff $a_i \leq b_i$ for all $i$. The lemma states that for every infinite sequence of $n$-tuples of natural numbers, there exist two indices $i<j$ such that $x_i \leq x_j$ in the pointwise order, i.e. the element of B denoted by $x_i$ is divisible by the element of B denoted by $x_j$.