, 2011

Number theory Difficulty 4.0 AIME Prove it Romania

Find all positive integers $a, b$ for which there exists sets $A, B$ of positive integers so that $A \cap B = \emptyset$ , $A \cup B = \mathbb{N}^*$ and $aA = bB$ (if $x$ is a number and $M$ is a set of numbers, $xM = \{xm \mid m \in M\}$ ).

Solution

We can assume that $1 \in A$ . Then $a \in bB$ , hence there exists $p \in B$ such that $a = pb$ . Moreover, $p \ge 2$ , because $1 \in A$ .

Every pair $(pb, b)$ , with $b \in \mathbb{N}^*$ , is a solution: we use the partition

$A = \{p^{2n}q \mid n \in \mathbb{N}, q \in \mathbb{N}^*, p \nmid q\}$
$B = \{p^{2n+1}q \mid n \in \mathbb{N}, q \in \mathbb{N}^*, p \nmid q\}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.