Question about relations between two numbers

Question

Is there is any relation between numbers' bits when one is divisible by another? What is the relation between the bits of 36 and the bit sequences of 9 or 4 or 12, or between 10 (1010) and 5 (101), or 21 (10101) and 7 (00111)?

Thanks. I am sorry if some sentence is not correct, but I hope you understand what I want.

Answer 1

Let's take the example of 36.

36 = 0010 0100

36 is 4 * 9, that is

 4 = 0100
 9 = 1001

If you multiply them (like you would on a normal multiplication) you'll have

    0100 x
    1001
 --------
    0100
   0000
  0000
 0100
 -------
 0100100

So essentially 0100 x 1001 = 0010 0100 (you can repeat the same for any other pair of divisors of course)

Now, is there any special relation that will allow you to get all the divisors of 36 just by looking at its bits? The answer, alas, is no :)

EDIT: there is no KNOWN relation at least but, who knows, in the future maybe some smart mathematician will find one. As of today, the answer is still no.

Answer 2

I know this is not exactly what you're asking, but it may be helpful. There are many tricks for establishing binary number divisibility by manipulation of bits. For example a binary number is divisible by three if the sum of its even binary bits minus the sum of its odd binary bits all modulus 3 is zero. Here's a link discussing binary divisibility.

Answer 3

The easiest to see is the number of consecutive 0 in the least significant digits designates the largest power of two that is a factor of your number n. There are apparently other tests, as DonnyD pointed out (I hadn't known that one) but I expect they're not going scale very well. If they did, public key cryptography, as it's generally implemented, would quickly become a thing of the past.

That's not to say that such methods can't be discovered / invented. For instance it's been shown that arbitrarily large numbers can be easily factored using quantum methods, but nobody's ever been actually able to implement a working system.

The bottom line is that we've entrusted our online financial system and national security apparatus to PKI based methods primarily because we assume that factoring numbers is hard for arbitrarily large numbers. But as Moron seemed to be implying in his answer, you're welcome to give it a whirl.

Answer 4

So you want to know if you can 'quickly' do Integer Factorization by just looking at the bits?

Good luck with that!

Answer 5

Obviously, that a is a multiple of b can be recognized given the binary representions of a and b (it's what the hardware does when executing the following code

boolean isMultiple = a % b == 0;

) and hence there is such a relationship.

Ask a more specific question to get a more specific response ...