The Student Room Group

Prime Number Question

This is the question and how far I've gotten;

With k being a natural number such that p=2k1 p = 2^k - 1 is a prime number (i.e 3, 7, 31) Define and list all positive integers which divide N;

N=2k1p N = 2^{k-1}p


So the positive integers that divide N must divide 2k1 2^{k-1} or p. Now p is prime, so the only thing that can divide it is itself and 1. The only things that can divide 2k1 2^{k-1} are multiples of two.

So divisors of 2k1 2^{k-1} are 2k1,2k2,2k3,2k4...2k(k2),2k(k1),2k(k0) 2^{k-1}, 2^{k-2}, 2^{k-3}, 2^{k-4} ... 2^{k-(k-2)}, 2^{k-(k-1)}, 2^{k-(k-0)}

Thus this tells me the positive integers which divide N (I'm assuming there's an infinite number of possibilities because I'm not sure if there is or isn't) are;

2k1,2k1,2k2,2k3,2k4...2k(k2),2k(k1),2k(k0) 2^{k} -1, 2^{k-1}, 2^{k-2}, 2^{k-3}, 2^{k-4} ... 2^{k-(k-2)}, 2^{k-(k-1)}, 2^{k-(k-0)}


Now it asks prove that the sum of all its divisors (including 1 but not N) is equal to N , this bit I can't do.

It's saying


2k1+2k1+2k2+2k3+2k4+...+2k(k2)+2k(k1)+2k(k0)=(2k1)(2k1) 2^{k} -1 + 2^{k-1} + 2^{k-2} + 2^{k-3} + 2^{k-4} + ... + 2^{k-(k-2)} + 2^{k-(k-1)} + 2^{k-(k-0)} = (2^{k-1})(2^k -1)

Basically simplified (since 2k(k0)=1 2^{k-(k-0)} = 1 )

2k+2k1+2k2+2k3+2k4+...+22+21=(2k1)(2k1) 2^{k} + 2^{k-1} + 2^{k-2} + 2^{k-3} + 2^{k-4} + ... + 2^{2} + 2^{1} = (2^{k-1})(2^k -1)

Now if I take a factor of 2k1 2^{k-1} out I get

(2k1)(21+20+21+22+23+...+23k+22k)=(2k1)(2k1) (2^{k-1})(2^{1} + 2^{0} + 2^{-1} + 2^{-2} + 2^{-3} + ... + 2^{3-k} + 2^{2-k}) = (2^{k-1})(2^k -1)

Which basically means I have to show that

21+20+21+22+23+...+23k+22k=2k1 2^{1} + 2^{0} + 2^{-1} + 2^{-2} + 2^{-3} + ... + 2^{3-k} + 2^{2-k} = 2^k -1


Sorry for the long explanation and I hope you understand. Let me know if I've gone wrong somewhere. I can't do the bolded bit, how exactly do I prove that last statement? Any help/hints appreciated.
(edited 13 years ago)
Reply 1
i=0n12i=2n1\sum_{i=0}^{n-1} {2^i} = 2^{n}-1

It's probably (slightly) easier to try to show that the sum of all the factors, including N, sum to 2N.
Original post by Hopple
i=0n12i=2n1\sum_{i=0}^{n-1} {2^i} = 2^{n}-1

It's probably (slightly) easier to try to show that the sum of all the factors, including N, sum to 2N.


Hey thanks. Is that just a general equation I'm meant to know or something? And I'm not sure if I can do what you proposed as the question says without including N as a divisor.

I'm not exactly sure how I can use your useful piece of information. I know that

2k1+2k1+2k2+2k3+2k4+...+2k(k2)+2k(k1)+2k(k0)=(2k1)(2k1) 2^{k} -1 + 2^{k-1} + 2^{k-2} + 2^{k-3} + 2^{k-4} + ... + 2^{k-(k-2)} + 2^{k-(k-1)} + 2^{k-(k-0)} = (2^{k-1})(2^k -1)

And using what you've said;

2k1+2k2+2k3+2k4+...+2k(k2)+2k(k1)+2k(k0)=2k1 2^{k-1} + 2^{k-2} + 2^{k-3} + 2^{k-4} + ... + 2^{k-(k-2)} + 2^{k-(k-1)} + 2^{k-(k-0)} = 2^{k}-1

But then I just get

2k1+2k1=2k+12=2(2k1) 2^{k} -1 + 2^{k} -1 = 2^{k+1} - 2 = 2(2^{k} -1)

What have I done wrong? :|
Reply 3
Let's take a concrete example: k=3, so p = 2^k - 1 = 7. Then N = 4.7 = 28.

If you list all the factors of 28, you'll see that you've missed (almost) a whole category in your earlier analysis.
Reply 4
Original post by Anti Elephant Mine


Thus this tells me the positive integers which divide N (I'm assuming there's an infinite number of possibilities because I'm not sure if there is or isn't) are;

2k1,2k1,2k2,2k3,2k4...2k(k2),2k(k1),2k(k0) 2^{k} -1, 2^{k-1}, 2^{k-2}, 2^{k-3}, 2^{k-4} ... 2^{k-(k-2)}, 2^{k-(k-1)}, 2^{k-(k-0)}




i think that you have overlooked factors made by combining the powers of 2 with the prime number p...

the bear

dfranklin beat me to it :colondollar::colondollar:
Reply 5
Original post by Anti Elephant Mine
Hey thanks. Is that just a general equation I'm meant to know or something? And I'm not sure if I can do what you proposed as the question says without including N as a divisor.

It'd be handy to know, yes :tongue: I'm sure you can do it that way, as long as you subtract off N at the end.

Does 2p divide N?
Ah my mistake, I've done it now, can't believe I didn't notice that. Thanks for the help, rep for all of you!

Quick Reply

Latest