# Smallest positive $n$ divisible by $2$ and $3$, and which is an $n$th power and $m$th power, is $2^{\mathrm{lcm}(n,m)}3^{\mathrm{lcm}(n,m)}$

What is the smallest positive integer divisible both by 2 and 3 which is both a perfect square and a sixth power?

Answer: $2^6 3^6$

More generally, what is the smallest positive integer $x$ divisible by both $2$ and $3$ which is both an $n$th power and an $m$th power, where $n,m \geq 2$?

Answer: $2^{[n,m]} 3^{[n,m]}$

How would you I prove the last statement?

• Working backwards from the answer, I'm assuming that $[n,m]$ is the LCM of $n$ and $m$. Is this correct? Jun 12 '13 at 7:01
• yes it is the lcm Jun 12 '13 at 7:05

Any positive integer $x$ can be uniquely expressed as a product $$x=2^{a_1}3^{a_2}\cdots p_k^{a_k}\cdots$$ where $p_k$ denotes the $k$th prime number, the exponents $a_k$ are all $\geq 0$, and all but finitely many of the exponents $a_k$ are equal to $0$.

• $x$ is divisible by $2$ $\iff$ $a_1\geq 1$

• $x$ is divisible by $3$ $\iff$ $a_2\geq 1$

• $x$ is an $n$th power $\iff$ every $a_k$ is divisible by $n$

• $x$ is an $m$th power $\iff$ every $a_k$ is divisible by $m$

• an integer is divisible by both $n$ and $m$ $\iff$ it is divisible by $\mathrm{lcm}(n,m)$

Thus, the numbers that are divisible by $2$ and $3$, and are both $n$th powers and $m$th powers, are precisely those $x$'s of the form $$x=2^{\mathrm{lcm}(n,m)b_1}3^{\mathrm{lcm}(n,m)b_2}\cdots p_k^{\mathrm{lcm}(n,m)b_k}$$ where $b_1,b_2\geq 1$ and all but finitely many $b_k$'s are equal to $0$. Minimizing everything given these constraints tells us to choose $b_1=b_2=1$ and every other $b_k=0$. Because $$2^{\mathrm{lcm}(n,m)}3^{\mathrm{lcm}(n,m)}$$ will divide any other positive integer with the desired properties, it will be $\leq$ any other positive integer with the desired properties, and it has the desired properties itself, so we can conclude that it is the smallest.