LCM of a range of numbers How would one solve this without a brute force method. 
Let $1\le n\le 10^{12}$ and $\text{lcm}(16,n)=16n$, find the number of unique $n$.
 A: $$\text{lcm}(a,b)=ab\iff \gcd(a,b)=1$$
If $\gcd(16,n)=\gcd(2^4,n)=1$, then $n$ is odd.  If $n$ is even, it will not be coprime to $16$.  So all odd $n$, and only odd $n$, satisfy $\text{lcm}(16,n)=16n$.  In $\{1,2,\ldots, 10^{12}\}$, there are $\frac{10^{12}}{2}=5\cdot 10^{11}$ such $n$.
A: $$\text{LCM}(a, b) = \frac {ab} {\text{GCD}(a, b)}$$
You can verify this by writing the prime factorizations of $a$ and $b$, and seeing which factors go into $\text{GCD}$ and which $\text{LCM}$.
Now all you have to do is find all $n$ which have no common divisors with $16$.
A: Noting $16=2^4,$ we know that $n$ is a number which has no prime factor $2$. This means that $n$ is odd. So all you need is to find the number of odd numbers such that $1\le n\le {10}^{12}.$
A: You have to first observe that $\mathrm{lcm}(16,n)=16n$, if and only if $n$ is odd, and the calculate how many odd numbers are between $1$ and $10^{12}$. Answer. $5\cdot 10^{11}$.
A: Hint $\ $ If $n$ is even then $\,16,n\mid 8n\,$ so $\,{\rm lcm}(16,n) \le 8n < 16n.$
Conversely, if $n$ is odd, then $\,(16,n)=1\,$ so $\,{\rm lcm}(16,n) = 16n.$
