Prime Numbers in Binary

[Dekan]

I was wondering, how does the concept of "Prime Numbers" work, in the Binary system.

 

The definition of a Prime Number is - a number that can only be divided by itself, or by 1. That definition leads to quick results in the Decimal system. For example, we find that "29" is Prime - because it can't be exactly divided by any of the other smaller digits - 2, 3, 4, 5, 6, 7, 8 or 9.

 

But In Binary, there aren't any other "smaller" digits. There's just two digits available: "1", and "0". And since division by "0" isn't a permissible mathematical operation, then you can only divide by "1".

 

Does that mean that all Binary numbers are Prime? That can't be right. Yet, how can we recognise when a Binary number isn't Prime?

 

Such recognition is facilitated in Decimal. If a number ends in "0", "2", "4", "6" or "8", we know it's divisible by 2. So, it's not Prime. And if it ends in "5", we know it's divisible by 5. So again, not Prime.

The only numbers that can be Prime in Decimal, are those ending in "1", "3" ,"7" or "9". Which at least narrows down the range of possibilities.

 

Whereas in Binary, there's no way of telling?

[Strange]

The definition of a Prime Number is - a number that can only be divided by itself, or by 1. That definition leads to quick results in the Decimal system. For example, we find that "29" is Prime - because it can't be exactly divided by any of the other smaller digits - 2, 3, 4, 5, 6, 7, 8 or 9.

 

It isn't enough to just check single digit numbers. For example, by your test 362881 would be prime as it is not (I don't think!) divisible by 2, 3, 4, 5, 6, 7, 8, or 9. But it is divisible by 19.

 

Prime numbers are exactly the same in binary as in any other base. In fact, when computers do arithmetic, including a prime number test, they do it in binary.

[Sensei]

I was wondering, how does the concept of "Prime Numbers" work, in the Binary system.

It works the same way as in any other system..

 

Binary, decimal, hexadecimal etc, are just visualization method.

 

Number remain the same.

 

The definition of a Prime Number is - a number that can only be divided by itself, or by 1. That definition leads to quick results in the Decimal system. For example, we find that "29" is Prime - because it can't be exactly divided by any of the other smaller digits - 2, 3, 4, 5, 6, 7, 8 or 9.

 

But In Binary, there aren't any other "smaller" digits. There's just two digits available: "1", and "0". And since division by "0" isn't a permissible mathematical operation, then you can only divide by "1".

You're mixing up definition of digit, with definition of number..

 

That's correct that in binary you have just 0 and 1 digits,

and in decimal are only 0...9

and in hexadecimal are 0...9, A-F (10-15).

 

Your example 29 ALSO exceeds 10 digit boundary of decimal system nearly 3 times!

 

In binary example:

 

%110 is not prime because it's dividable by %10 and by %11.

 

 

Does that mean that all Binary numbers are Prime? That can't be right. Yet, how can we recognise when a Binary number isn't Prime?

 

Such recognition is facilitated in Decimal. If a number ends in "0", "2", "4", "6" or "8", we know it's divisible by 2. So, it's not Prime. And if it ends in "5", we know it's divisible by 5. So again, not Prime.

The only numbers that can be Prime in Decimal, are those ending in "1", "3" ,"7" or "9". Which at least narrows down the range of possibilities.

 

Whereas in Binary, there's no way of telling?

Any prime number in binary system must end up with %1 (except %10)

it's equivalent of ending with 1,3,5,7,9 in decimal.

But that's not the only condition!

 

I can also write fraction using binary, see:

 

%111.1011

 

It means:

1*2^2+

1*2^1+

1*2^0+

1*2^-1+

0*2^-2+

1*2^-3+

1*2^-4=

7.6875

Edited August 24, 2014 by Sensei

[Dekan]

Many thanks, Strange and Sensei, for your posts.

 

I understand that numbers are written in notation. And that the notation we use, can't change the intrinsic property of a "number".

For example, suppose we represent number "7" by "I I I I I I I I ", or "VII", or a letter of the Greek alphabet, or a Chinese logogram That makes no difference to its "mathematical" properties. Only how we "visual it", as Sensei points out.

 

I was only wondering, how prime numbers can be determined in Binary, if all Binary numbers can only be divided by "1"

 

I still don't quite get it, but am content to dumbly accept Sensei's explanation. Thanks again!

[Fuzzwood]

You can or cannot divide them by 11 as well. It's not the fact of prime numbers you don't grasp but the binary counting method.

[Curiatron]

Hi Dekan,

 

In reading your original question, and subsequent follow up response, I see a few misunderstandings that, if cleared up, would help answer your question. The above posters have corrected you regarding your understanding of how to determine a prime number:

 

That definition leads to quick results in the Decimal system. For example, we find that "29" is Prime - because it can't be exactly divided by any of the other smaller digits - 2, 3, 4, 5, 6, 7, 8 or 9.

 

However, your statement:

 

But In Binary, there aren't any other "smaller" digits. There's just two digits available: "1", and "0". And since division by "0" isn't a permissible mathematical operation, then you can only divide by "1".

lead me to also wonder if you have the correct idea of how the binary number system works? No offense is meant by this questioning - purely trying to help here...

 

In the binary number system, you are correct that there are only two "digits" available to express numeric values - the "0" and the "1". You may be a bit confused because "0" in binary is written the same as "0" in decimal. Likewise, "1" in binary is written the same as "1" in decimal. But, the similarity ends there. In fact, we can express any number we wish using a series of the "0" and "1" digits. So, for example, the value 3 in our normal (i.e. decimal) system is expressed as "11" in binary. The value 4 in decimal system is expressed as "011" in binary. Here is one source for more on decimal-binary number conversion: http://www.binarymath.info/decimal-conversion.php

 

If/once you do have an understanding of how the binary number system works, then I would suggest a review of how division works in the binary number system. Here is a link to one source: http://www.binarymath.info/multiplication-division.php You will see that binary division is not limited to only dividing by "0" and "1" as you stated. Rather, we are allowed to divide by any number we wish! It's just that the number we are dividing by is expressed using binary numbers, and thus a series of "0" and "1" digits.

 

Hope this helps!

 

Oh, and remember: there only 10 types of people in this world - those that understand binary, and those that don't!

[Sensei]

I was only wondering, how prime numbers can be determined in Binary, if all Binary numbers can only be divided by "1"

 

I still don't quite get it, but am content to dumbly accept Sensei's explanation. Thanks again!

 

Can you divide in binary?

 

Then you can check whether some number is prime or not.

 

%110 = 6

 

try divide it by:

 

%001

%010

%011

%100

 

And it's dividable by %10 (2) and %11 (3)

If number in binary has some visible pattern, it'll be for sure dividable by that pattern f.e.

 

%10011001 (153)

It will be dividable by %1001 (9)

 

Can you tell in decimal whether 153 is dividable by 9 from memory? Unlikely unless you're genius or have calculator..

But in binary it's immediately visible.

 

And result will be:

%00010001 (17)

See that "1" is always where is beginning of pattern.

 

 

Is

%100110011001100110011001100110011001

dividable by %1001 ?

 

Is 41231686041 dividable by 9??

 

Of course! It's clearly visible in binary..

 

And result will be:

%100010001000100010001000100010001

4581298449

[Delta1212]

Many thanks, Strange and Sensei, for your posts.

 

I understand that numbers are written in notation. And that the notation we use, can't change the intrinsic property of a "number".

For example, suppose we represent number "7" by "I I I I I I I I ", or "VII", or a letter of the Greek alphabet, or a Chinese logogram That makes no difference to its "mathematical" properties. Only how we "visual it", as Sensei points out.

 

I was only wondering, how prime numbers can be determined in Binary, if all Binary numbers can only be divided by "1"

 

I still don't quite get it, but am content to dumbly accept Sensei's explanation. Thanks again!

121 cannot be divided by 2, 3, 4, 5, 6, 7, 8 or 9. It can, however, be divided by 11, so it is not prime.

 

In binary, 11(3) * 11(3) = 1001(9)

 

1001(9) can be divided by 11(3), therefore 1001(9) is not prime.

 

1011(11) cannot be divided by 10(2), 11(3), 100(4), 101(5),110(6), 111(7), 1000(8), 1001(9) or 1010(10), therefore 1011(11) is prime.

[imatfaal]

 

Can you divide in binary?

 

Then you can check whether some number is prime or not.

 

%110 = 6

 

try divide it by:

 

%001

%010

%011

%100

 

And it's dividable by %10 (2) and %11 (3)

If number in binary has some visible pattern, it'll be for sure dividable by that pattern f.e.

 

%10011001 (153)

It will be dividable by %1001 (9)

 

Can you tell in decimal whether 153 is dividable by 9 from memory? Unlikely unless you're genius or have calculator..

But in binary it's immediately visible.

 

And result will be:

%00010001 (17)

See that "1" is always where is beginning of pattern.

 

 

Is

%100110011001100110011001100110011001

dividable by %1001 ?

 

Is 41231686041 dividable by 9??

 

Of course! It's clearly visible in binary..

 

And result will be:

%100010001000100010001000100010001

4581298449

 

Hi Sensei - nicely put. But surely that applies to any base

 

ie in base x

 

abcdeabcdeabcde must be divisible by at least abcde and (x^10+x^5+1)

 

eg

123451234512345 in decimal is divisible by 12345 and 10000100001

[Sensei]

Yes, of course. I didn't meant that it's binary exclusive feature.