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 - The Fusion of Science and Community**

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

Loading...

Similar Threads for Binary numbers | Date |
---|---|

I Linear mapping of a binary vector based on its decimal value | Mar 23, 2018 |

Proof that all information can be coded in binary? | Aug 15, 2015 |

What are some simple non-associative binary operations? | Jul 28, 2013 |

Is there an example for a binary operation which is commtative and not associative ? | Nov 17, 2012 |

Number theory: Binary Quadratic Forms | Mar 21, 2010 |

**Physics Forums - The Fusion of Science and Community**