Register to reply 
Binary numbers and gcd/lcm 
Share this thread: 
#1
Oct2405, 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) 


#2
Oct2405, 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 2^{k1} = 2^{k}/2 different numbers. 


#3
Oct2405, 11:39 AM

Sci Advisor
HW Helper
P: 1,994

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 