PDA

View Full Version : fun proof


mike
March 2nd, 2002, 18:24
OK, this doesn't have to do with crypto per se, but it does relate to factoring and it's fun if you haven't seen it before.

Prove that if n is composite (i.e. not prime) then (2^n)-1 is also composite.

I'll give hints if they're needed, but I doubt this crowd will have much trouble.

tony b.
March 4th, 2002, 08:03
spoiler (?)

Let n = pq, p>1, q>1.
Then 2^pq - 1 = (2^q - 1)(2^q[p-1] + 2^q[p-2] + ... + 2^q + 1).
(This is obtained by long division.)

regards,

tony