Register to reply

Binary numbers and gcd/lcm

by bobsmiters
Tags: binary, gcd or lcm, numbers
Share this thread:
bobsmiters
#1
Oct24-05, 01:15 AM
P: 12
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?

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)
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
Esmil
#2
Oct24-05, 08:48 AM
P: 1
I think the first question should be understood as
"How many integers are there with k digits in its binary representation?".

Disregarding the special case n = 0, the first digit in the binary representation of a number n with k digits must always be 1. The rest however can be either 0 or 1. That gives us exactly
2k-1 = 2k/2 different numbers.
shmoe
#3
Oct24-05, 11:39 AM
Sci Advisor
HW Helper
P: 1,994
Quote Quote by bobsmiters
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)
If [tex]c=p_1^{\min(m_1,n_1)}\ldots p_k^{\min(m_k, n_k)}[/tex] you have a couple of things to show. First show that c divides both a and b. This should be easy.

Next, if d divides both a and b, you want to show d divides c. Consider the prime factorization of d, and use the assumption that it divides both a and b here.

The lcm one is similar.


Register to reply

Related Discussions
Binary numbers (fundamental) question General Math 1
Digital circuit: multiplying 2 binary numbers Electrical Engineering 2
Binary to decimal confusion signed numbers! Engineering, Comp Sci, & Technology Homework 1
Question on binary stars & binary stars Introductory Physics Homework 1