Smallest multiplier that reveals a factor of a semiprime Given a semiprime N, find the smallest positive integer m such that the binary representation of one of the two factors of N can be found in the binary representation of N * m.

Example

Let's consider the semiprime N = 9799.

We try different values of m, starting at 1:

 m |  N * m |   N * m in binary
---+--------+------------------
 1 |   9799 |    10011001000111
 2 |  19598 |   100110010001110
 3 |  29397 |   111001011010101
 4 |  39196 |  1001100100011100
 5 |  48995 |  1011111101100011
 6 |  58794 |  1110010110101010
 7 |  68593 | 10000101111110001
 8 |  78392 | 10011001000111000
 9 |  88191 | 10101100001111111
10 |  97990 | 10111111011000110
11 | 107789 | 11010010100001101


We stop here because the binary representation of the last product contains 101001 which is the binary representation of 41, one of the two factors of 9799 (the other one being 239).



So the answer would be 11.

Rules and notes


Trying even values of m is pointless. They were shown in the above example for the sake of completeness.
Your program must support any N for which N * m is within the computing capabilities of your language.
You are allowed to factorize N beforehand rather than trying each possible substring of the binary representation of N * m to see if it turns out to be a factor of N.
As proven by MitchellSpector, m always exists.
This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.


Test cases

The first column is the input. The second column is the expected output.

         N |    m |         N * m |                              N * m in binary | Factor
-----------+------+---------------+----------------------------------------------+-------
         9 |    3 |            27 |                                      [11]011 |      3
        15 |    1 |            15 |                                       [11]11 |      3
        49 |    5 |           245 |                                   [111]10101 |      7
        91 |    1 |            91 |                                    10[1101]1 |     13
       961 |   17 |         16337 |                             [11111]111010001 |     31
      1829 |    5 |          9145 |                             1000[111011]1001 |     59
      9799 |   11 |        107789 |                          1[101001]0100001101 |     41
     19951 |   41 |        817991 |                       1[1000111]101101000111 |     71
    120797 |   27 |       3261519 |                     11000[1110001]0001001111 |    113
   1720861 |  121 |     208224181 |               11000110100[100111111101]10101 |   2557
 444309323 |  743 |  330121826989 |    100110011011100110010[1101010010101011]01 |  54443
 840000701 | 4515 | 3792603165015 | 11011100110000[1000110000111011]000101010111 |  35899
1468255967 |   55 |   80754078185 |      1001011001101010100010[1110001111]01001 |    911
05AB1E, 18 16 15 bytes

-2 bytes thanks to Riley!

-1 byte thanks to Emigna!

[N¹*b¹Ñ¦¨båOiNq


Explanation:

[                   # Infinite loop start
 N                  # Push the amount of times we have iterated
  ¹*               # Multiplied by input
    b              # Convert to binary
     ¹Ñ¦¨b         # Calculate the proper divisors of the input in binary excluding one
          åO       # Check if a substring of N * m in binary is in the divisors
            iNq    # If so, print how many times we have iterated and terminate the program


Try it online!