If n has k digits in its binary numeral, show that there are at most 2^k/2 numbers n. Can there be exactly 2^k/2?(adsbygoogle = window.adsbygoogle || []).push({});

I tried to understand this question with an example so I took n=36 which has the binary number 100100; k=6 but 2^k/2n gives 2^3 36 but 8 is not less than or equal to 6??? Any help is appreciated for either question.

Also does anyone know how to prove this:

Suppose that p_1, p_2, ..., p_k are all the primes that divide a or b, and that a=p_1^m_1 X p_2^m_2 X...X p_k^m_k, b=p_1^n_1 X p_2^n_2 X...Xp_k^n_k

Deduce that: gcd(a,b) = p_1^min(m_1, n_1)Xp_2^min(m_2,n_2)...Xp_k^min(m_k, n_k),

lcm(a,b) = p_1^max(m_1, n_1)Xp_2^max(m_2,n_2)...Xp_k^max(m_k, n_k)

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Binary numbers and gcd/lcm

**Physics Forums | Science Articles, Homework Help, Discussion**