## Factor Theorem and Conjecture

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