The other day I was browsing through Riesel and opened it at Appendix

3, Legendre’s symbol,

x^2 º a mod p; a thought came into my mind from where who knows!!

It was just silly, that it was equivalent to N = pq.

Conjecture

An odd p < s (s the integer square root) will be a factor of N a

composite odd number if and only if

s^2 = - (N - s^2) mod p .

I can prove the main part but not that p can be either a prime or a

composite.

Proof

N = pq

s = flr(sqr( N))

Redefine p and q as follows:-

p = s - t ( t is an integer - 0 < t < s )

q = s + t + k ( k is an integer and will always be of the form of

either (0 mod 4) or (2 mod 4) depending on N

Substituting the redefined p and q , back into N = pq

N = ( s - t)( s + t + k)

N = s^2 + ks - kt - t^2 (the st values cancel out)

Solve for t^2

t^2 = k(s - t) - (N - s^2)

Taking the modulus of both sides using (s - t) gives

t^2 = 0 - ( N - s^2) (mod ( s - t))

t^2 mod(s - t) = s^2 mod ( s- t) (any difference is a multiple of ( s

- t))

This gives

s^2 = - ( N - s^2) mod p.

QED

Example

I will use a number from Riesel (page 147 of my edition)

N = 13199

s = 114

p = 67

(114^2) mod 67 = 65

(N - s^2) = 203 => 203 mod 67 = 2

This is 67 - 2 = 65

I have looked at some of the RSA numbers that have been solved and they

also confirm the above.

A number that shows that p can be composite is 1617

N = 1617

s = 40

p = 33

(40^2) mod 33 = 16

N - s^2 = 1617 - 1600 = 17

p - 17 = 33 - 17 = 16

If the residues to a number N, are found using the N and then (N-s^2)

they give 2 different sets; example using 12007001

Residues for N =? (-1 2 3 5 7 11 13 23 29 37 43 71 73 89 97)

Residues for (N - s^2) => (-1 2 5 23 31 43 53 59 61 67 71 89 97)

Intersection of the 2 sets gives (-1 2 5 23 43 71 89 97)

I am not sure that this will be of any real benefit, but who knows.

Ron