LinkBack URL
About LinkBacks
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.
