Given positive integers $m$, $a$, $b$, $(a,b)=1$. $A$ is a non-empty subset of the set of all positive integers, so that for every positive integer $n$ there is $an \in A$ and $bn \in A$. For all $A$ that satisfy the above condition, find the minimum of the value of $\left| A \cap \{ 1,2, \cdots,m \} \right|$
Problem
Source: China TST 2006
Tags: number theory unsolved, number theory
iura
20.06.2006 13:07
Let $a<b$. We can suppose $S$ contains all numbers greater than $m$. Then if $x>\frac mb$ the condition is already fulfilled. Let $H$ be the set of all elements less than $\frac mb$ that are divisible by an even power of $b$ (i.e. either not divisible by $b$ or divisible by $b^2$ and not $b^3$ and so on). Then for each $x\in H$ either $ax$ or $bx$ is in $S$. Moreover we can't have $ax=by$ for $x,y$ in $H$ because then the powers of $b$ in $x,y$ would differ by $1$ so one would be odd. Hence $|S\bigcap \{1,2,\ldots,m\}|\geq |H|$. However te condition is satisfied by $S=bH\bigcup \{m+1,m+2,\ldots\}$: if $x\leq \frac mb$ then if $x \in H$ then $bx \in S$ otherwise $\frac{ax}b \in H$ so $ax$ in $S$. Finally $|H|$ can be computed to be $[\frac mb]-[\frac m{b^2}]+[\frac m{b^3}]+\ldots$
M@re
20.06.2006 22:09
I am not sure that I understood this problem right... If I am right numbers in $A$ are all positive integers that are divisible with $a$ or $b$, and only those? Then $|A\cap \{1,2,...,m\}|=[\frac{m}a]+[\frac{m}b]-[\frac{m}{lcm(ab)}]$. Do I make mistake somewhere?