Use the Chinese Remainder Theorem to find the smallest element of a set

186 Views Asked by At

Use the Chinese Remainder Theorem to find the smallest element of $$\left\{n\in \mathbb{N}: \sqrt{\frac{n}{2}}, \sqrt[3]{\frac{n}{3}}, \sqrt[5]{\frac{n}{5}}\in \mathbb{N}\right\}$$

I have played around it and I have obtained the set of congruences

$$ n\equiv 0 \mod{2k_{1}^{2}}$$ $$ n\equiv 0 \mod{3k_{2}^{3}}$$ $$ n\equiv 0 \mod{5k_{3}^{5}}$$ for some $k_{1}, k_{2}, k_{3}\in \mathbb{N}$. But since they might not be mutually coprime I'm not sure how the Chinese Remainder Theorem can be applied.

1

There are 1 best solutions below

0
On BEST ANSWER

Ok. At least it is clear that our number has to be of the form $2^x3^y5^z$.All we have to do is determine the least $x,y,z$ so that our conditions are satisfied.

i) Note that$2^{x-1}3^y5^z$ is a square number. Hence 2 divides $x-1$, $y$ and $z$.

ii) Note that $2^x3^{y-1}5^z$ is a perfect cube. Hence 3 divides $x$, $y-1$ and $z$.

iii) Note that $2^x3^{y}5^{z-1}$ is a perfect fifth power. Hence 5 divides $x$,$y$ and $z-1$.

So you have the following:

i) $x \equiv 1(2), x\equiv 0(3),x\equiv 0(5)$

ii)$y \equiv 0(2), y\equiv 1(3),y\equiv 0(5)$

iii)$z \equiv 0(2), x\equiv 0(3),x\equiv 1(5)$

Solve for $x,y,z$ using Chinese Remainder theorem. That is your job done. I expect the answer then, to be $2^{15}3^{10}5^{6} = 30233088000000$.