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

Factor Theorem

Expand Messages
  • Kermit Rose
    I ve discovered a relationship between factors of a target composite integer, and the factors of a related integer. If z = x y is a composite integer, then
    Message 1 of 1 , Dec 6, 2008
    • 0 Attachment
      I've discovered a relationship between factors of a target composite
      integer,
      and the factors of a related integer.

      If z = x y is a composite integer,

      then there exist at least phi(x) pairs of integers (g,d)

      such that

      x = d + some divisor of ( z - g * d**2 ).


      This might or might not be useful for factoring larger integers.

      The proof is simple.

      Let x = c + d
      Let y = c h + d g

      It will always be possible to choose c and d to be relatively prime,
      and therefore be possible to set y = c h + d g.

      There will be at least phi(x) ways to choose d so that d and x are
      relatively prime.
      For each of these choices of d, there will be at least one choice for g.


      x y = (c + d) (c h + d g) = h c**2 + (h + g) c d + g d**2

      h c**2 + (h + g) c d + g d**2 = z

      h c**2 + (h + g) c d = z - g d**2

      c ( h c + [ h + g ] d ) = z - g d**2

      c is a divisor of z - g d**2

      x = d + c

      x = d + a divisor of ( z - g d**2)

      The divisor might be either positive or negative.


      As an example,

      z = 341

      Require g = 1.

      Test if d = 2**4 = 16

      x = 16 - some divisor of (341 - 16**2 ) = 16 - some divisor of (85)

      Pretend we don't immediately know the factors of 85.

      Try to factor 85 by same method.

      Test if d = 2**3 = 8

      x = 8 - some divisor of (85 - 8 **2 ) = 8 - some divisor of (21)

      Pretend we don't immediately know the factors of 21

      Test if d = 2**2 = 4.

      x = 4 - some factor(21 - 16) = 4 - some factor of 5.

      x = 4 - 1 = 3 divides 21.

      Back to factors of 85.

      x = 8 - some divisor of 21.
      x = 8 - 3.

      Back to factors of 341.


      x = 16 - some divisor of (85)

      x = 16 - 5 = 11


      Kermit Rose
    Your message has been successfully submitted and would be delivered to recipients shortly.