## Factor Theorem

Expand Messages
• 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
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.