Is this a question?

CB

Results 1 to 3 of 3

- August 18th 2009, 10:18 AM #1

- Joined
- Jun 2009
- Posts
- 5

## b +/- x^2 = 0 (mod n) n-1/2 is odd

For any integer b and odd prime n where b mod n is non-zero

b (mod n) is a member of the set {1,...,(n-1)}

b^2 (mod n) is also a member of the set {1, ...,(n-1)}

(n-x)^2 - x^2 = 0 for any x in the set so for every x > n/2 there will be a y=(n-x)<n/2 such that y^2=x^2(mod n). therefore there will be n-1/2 members of the set where x^2 will belong.

; x^2 - y^2 =0 (mod n)

(x-y)(x+y)=0 (mod n)

then (x-y)=0 and therefore x=y

(x+y) = n and therefore (n-x) = y

no if x^2 -y^2 =0 (mod n)

there is no z not equal to y where

x^2 - z^2 = 0 (mod n)

__________________________________________________ ________

next is to determine whether there is an x^2 and y^2 in the set such that

x^2 + y^2 = 0(mod n).

from Fermat's little theorem x^(n-1) - y^(n-1) = 0 (mod n)

and assume x^2 + y^2 = 0 (mod n)

x^2(x^(n-3)) - y^2(y^(n-3)) = 0 (mod n)

x^2(x^(n-3)) + x^2(y^(n-3)) = 0 (mod n)

(x^(n-3)) + (y^(n-3)) = 0 (mod n)

___________________________________________

x^2(x^(n-5)) + y^2(y^(n-5)) = 0 (mod n)

x^2(x^(n-5)) - x^2(y^(n-5)) = 0 (mod n)

(x^(n-5)) - (y^(n-5)) = 0 (mod n)

___________________________________________

iteration will show

x^(n-1-2c) + y^(n-1-2c) =0 (mod n) c is odd

and

x^(n-1-4d) - y^(n-1-4d)= 0(mod n) d is odd or even

if n-1/2 is odd n-1 = 2f f is odd

x^2 + y^2 = x^(n-1-2c) + y^(n-1-2c)

2=n-1-2c or n-1 = 4g where g is odd or even

but n-1 = 2f =4g where f,g are odd

therefore for n-1/2 odd

x^2 + y^2 (mod n) will never equal 0 (mod n)

__________________________________________________ __________

x,y member of {1, .. ,n-1}

x^2, y^2 members of {1, ... , n-1} has n-1/2 distinct members

for x^2 (mod n) > n/2 can all be folded to n - x^2 without fear of there being a y^2= n- x^2 (mod n) to make a new set

(n- x^2) (mod n) union (y^2 (mod n)) = {1, ... , n-1/2} with n-1/2 members

therfore for any given b there is an x^2 such that

b + x^2 = 0 (mod n) XOR b - x^2 = 0 (mod n) for (n-1)/2 ODD

also because (n-x^2) union (y^2) member of {1,...,n-1/2} with n-1/2 distinct members

then

(n-x^2)^2 union (y^2)^2 equivalent will have n-1/2 distinct members

in {1,...n-1} ; (x^4)>n/2 y^4<n/2.

because as before all members h(mod n) > n/2 h^2 will have one equivalent member y^2, where h^2 = y^2 (mod n) there the set

{1,...,n-1/2} is sufficient for generating all squares.

so

(n-x^(2i) union (y^(2i)) will have n-1/2 distinct member in {1,...,n-1/2}

and for ant given b there is an x such that

b + x^(2i) = 0 (mod n) XOR

b - x^(2i) = 0 (mod n)

wher i is any positive integer.

- August 18th 2009, 09:56 PM #2

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 4

- August 18th 2009, 11:03 PM #3

- Joined
- Jun 2009
- Posts
- 5