- #1

- 3

- 0

I have to test if a binary number is divisible to

2^n - 1 where n is even.

Is there a test available for binary numbers like to test a divisibility by 3.

Thanks in advance...

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter kurtulmehtap
- Start date

- #1

- 3

- 0

I have to test if a binary number is divisible to

2^n - 1 where n is even.

Is there a test available for binary numbers like to test a divisibility by 3.

Thanks in advance...

- #2

- 1,056

- 0

You are talking about what, in general, is studied as Mersenne primes. Even powers are generally not prime. That's not hard to show.

Last edited:

- #3

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

- #4

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

You are talking about what, in general, is studied as Mersenne primes. Even powers are generally not prime. That's not hard to show.

I interpreted the question as "how can I tell if N is divisible by 2^n-1" rather than "how can I tell if N divides 2^n-1".

- #5

- 3

- 0

in my case n is even, not odd or prime

- #6

- 77

- 0

1100101 1-1+0-0+1-0+1=2 not divisible by 3

1100110 1-1+0-0+1-1+0=0 divisible by three.

- #7

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

1100101 1-1+0-0+1-0+1=2 not divisible by 3

1100110 1-1+0-0+1-1+0=0 divisible by three.

3 is a funny number, since it's 2^1 + 1 and 2^2 - 1. You can use either type of test: add digits in blocks of two, or alternately add and subtract digits.

10101011 = 10+10+10+11 = 1001 = 10 + 01 = 11 = 0 (mod 3)

10101011 -> 1-0+1-0+1-0+1-1 = 11 = 0 (mod 3)

The first preserves residues (not just divisibility) mod 3; the second works with smaller numbers (though twice as many).

- #8

- 77

- 0

Share: