Binary numbers and gcd/lcm

  • Thread starter bobsmiters
  • Start date
  • #1
12
0
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)
 

Answers and Replies

  • #2
1
0
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.
 
  • #3
shmoe
Science Advisor
Homework Helper
1,992
1
bobsmiters said:
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.
 

Related Threads on Binary numbers and gcd/lcm

  • Last Post
3
Replies
59
Views
11K
  • Last Post
Replies
3
Views
10K
Replies
2
Views
4K
Replies
6
Views
9K
Replies
2
Views
2K
Replies
21
Views
5K
Replies
7
Views
4K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
3
Views
3K
Top