Sorry, an error occurred while loading the content.
Browse Groups

• 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.