Loading ...
Sorry, an error occurred while loading the content.

Factor Theorem and Conjecture

Expand Messages
  • Kermit Rose
    Factor Theorem and Conjecture Let z be a positive odd integer. Define n_z and m_z by 2** n_z
    Message 1 of 1 , Jan 2, 2009
    • 0 Attachment
      Factor Theorem and Conjecture

      Let z be a positive odd integer.

      Define

      n_z and m_z by

      2** n_z < z < 2** (n_z + 1)

      2** m_z < sqrt(z) < 2** (m_z + 1)


      For k = 1,2,3,. . ., define

      d_k = mod( int( z/2**k) , 2)

      The d1,d2, . . . d_n are just the bits in the base 2

      representation of z.

      z = 1 + sum( (k=1 to n) d_k 2**k)

      Define binary variables w1,w2,... w_n.

      Each of the w1,w2, ... w_n are restricted to having only the

      values of zero or one.

      z = 1 + sum( (k = 1 to n) w_k 2**k) implies that
      for each k, w_k = d_k.

      Now define a factor pair (x_z, y_z) in terms of the w_k and d_k

      as follows.

      x_z = 1 + sum( (k = 1 to m) 2**k w_k)

      x_z represents all odd positive integers < sqrt(z).

      y_z = z + sum ( (k = 1 to n) ( 1 - 2 d_k ) 2**k w_k)

      y_z apparently represents all odd positive integers < (z+1).


      However, y_z is closely linked with x_z.

      All pairs of factors of z, x_z, y_z, such that

      x_z * y_z = z are of this form.

      The conjecture part of this post is that

      if we set

      x_z * y_z = z, we can easily solve for the
      w1,w2,... w_m, thus finding the factors of z.

      If this conjecture is true, then we also have an easy prime test.

      z is prime if and only if setting

      x_z * y_z = z enables us to prove that x_z = 1.


      Example 1:

      z = 29.

      29
      14
      7
      3
      1

      d1 = 0, d2 = 1, d3 = 1, d4 = 1

      29 = 1 + 4 + 8 + 16

      x29 = 1 + 2 w1 + 4 w2

      y29 = 29 - 2 w1 + 4 w2 + 8 w3 + 16 w4

      ( 1 + 2 w1 + 4 w2)(29 - 2 w1 + 4 w2 + 8 w3 + 16 w4) = 29
      implies

      29 -2 w1 + 4 w2 + 8 w3 + 16 w4
      + 58 w1 - 4 w1 + 8 w1 w2 + 16 w1 w3 + 32 w1 w4
      + 116 w2 - 8 w1 w2 + 16 w2 + 32 w2 w3 + 64 w2 w4 = 29

      (-2 + 58 - 4) w1 + (4 + 116 + 16) w2 + 8 w3 + 16 w4
      + 16 w1 w3 + 32 w1 w4 + 32 w2 w3 + 64 w2 w4 = 0

      52 w1 + 136 w2 + 8 w3 + 16 w4
      + 16 w1 w3 + 32 w1 w4 + 32 w2 w3 + 64 w2 w4 = 0

      Divide by 4.

      13 w1 + 34 w2 + 2 w3 + 4 w4
      + 4 w1 w3 + 8 w1 w4 + 8 w2 w3 + 16 w2 w4 = 0

      w1 = 0

      24 w2 + 2 w3 + 4 w4 + 8 w2 w3 + 16 w2 w4 = 0

      Divide by 2

      12 w2 + w3 + 2 w4 + 4 w2 w3 + 8 w2 w4 = 0

      w3 = 0

      12 w2 + 2 w4 + 8 w2 w4 = 0

      Divide by 2

      6 w2 + w4 + 4 w2 w4 = 0

      w4 = 0

      6 w2 = 0

      w2 = 0

      29 is prime.

      Example 2:

      z = 35

      35
      17
      8
      4
      2
      1

      d1 = 1, d2 = 0, d3 = 0, d4 = 0, d5 = 1

      35 = 1 + 2 + 32

      x35 = 1 + 2 w1 + 4 w2

      y35 = 35 - 2 w1 + 4 w2 + 8 w3 + 16 w4 - 32 w5

      (1 + 2 w1 + 4 w2) * (35 - 2w1 + 4w2 + 8w3 + 16w4 -32w5) = 35


      35 - 2w1 + 4w2 + 8 w3 + 16 w4 - 32 w5
      + 70 w1 - 4 w1 + 8 w1 w2 + 16 w1 w3 + 32 w1 w4 - 64 w1 w5
      + 140 w2 - 8 w1 w2 + 16 w2 + 32 w2 w3 + 64 w2 w4 - 128 w2 w5
      = 35

      (-2 + 70 - 4) w1 + (4 + 140 + 16) w2 + 8 w3 + 16 w4 - 32 w5
      + 16 w1 w3 + 32 w1 w4 - 64 w1 w5 + 32 w2 w3 + 64 w2 w4
      - 128 w2 w5 = 0

      64 w1 + 160 w2 + 8 w3 + 16 w4 - 32 w5
      + 16 w1 w3 + 32 w1 w4 - 64 w1 w5 + 32 w2 w3 + 64 w2 w4
      - 128 w2 w5 = 0

      divide by 8

      8 w1 + 20 w2 + w3 + 2 w4 - 4 w5
      + 2 w1 w3 + 4 w1 w4 - 8 w1 w5 + 4 w2 w3 + 8 w2 w4
      - 16 w2 w5 = 0

      w3 = 0

      8 w1 + 20 w2 + 2 w4 - 4 w5
      + 4 w1 w4 - 8 w1 w5 + 8 w2 w4
      - 16 w2 w5 = 0

      divide by 2

      4 w1 + 10 w2 + w4 - 2 w5
      + 2 w1 w4 - 4 w1 w5 + 4 w2 w4
      - 8 w2 w5 = 0

      w4 = 0

      4 w1 + 10 w2 - 2 w5
      - 4 w1 w5
      - 8 w2 w5 = 0

      divide by 2

      2 w1 + 5 w2 - w5 - 2 w1 w5 - 4 w2 w5 = 0

      w5 = w2

      2 w1 + 5 w2 - w2 - 2 w1 w2 - 4 w2 w2 = 0

      2 w1 - 2 w1 w2 = 0

      Divide by 2

      w1 - w1 w2 = 0

      w1 (1 - w2) = 0

      w5 = 0, w4 = 0, w3 = 0, w1 (1 - w2) = 0

      w1 = 0 implies that x35 = 1 + 2 w1 + 4 w2 = 1 + 4 w2
      = 1 or 5.

      w1 = 1 implies that (1 - w2) = 0 implies w2 = 1
      implies
      x_35 = 1 + 2 w1 + 4 w2 = 1 + 2 + 4 = 7.
    Your message has been successfully submitted and would be delivered to recipients shortly.