0
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.