
a contradiction worth reading (unless a silly mistake was made)
Posted:
Jul 19, 2011 11:39 AM


there exists an i: 1<i<=(n3)/2 when n is prime and (n1)/2 is odd such that:
x^(2^i)=x^2 (mod n)
which leads to x^2 = 1 mod n for all x!=0 mod n

Let S be the set {1,2,...,(n3)/2,(n1)/2}
let x be any member of set S and y be any other member of set S
x^2=y^2 (mod n) implies either: (1) x=y (a contradiction if x!=y) (2) x = y (mod n) (a contradiction) therefore x^2!=y^2 mod n if x!=y
let x^2 = y^2 (mod n) but x^(n1)  y^(n1) = 0 mod n or (x^2)^(n1)/2  (y^2)^(n1)/2 = 0 mod n or (x^2)^(n1)/2 + (x^2)^(n1)/2 = 0 mod n or 2x^(n1)= 0 mod n (a contradiction) therefore x^2!=y^2 mod n for any x and y in S
let x^2 (mod n) make the set S' where x is any member of S because of the above arguement S' will have (n1)/2 distinct members (note: the only way it's a smaller subset of S' is if x^2=y^2 (mod n) x!=y (a condtradiction))
let y^(2^i) mod n be any a member of the set S''={1,...,n1} that is not a member of set of S' (where i>1).
Then because S' has (n1)/2 distict member with no two adding to n. We will have an x^2 in S' such that x^2 + y^(2^i) = 0 mod n (a contradiction).
Therefore x^(2^i) mod n will also make up the same set S' or a subset of S' (i>1)
so again because S' has (n1)/2 members and one of those members is 1 there will be an i: 1<i<=(n3)/2 such that
x^2=x^(2^i) mod n (b)
or in the case of a subset >x!=y and x^(2^i)=y^(2^i) (mod n) (which leads to a contradiction)
EXPANDING THE ORIGINAL SET S let z and g are any member of (the new set) (1,2,...,{n1}) then z^2 mod n will form the same set
S'and hence z^(2^i) mod n will form the same set S' that is z!=g and z^(2^i)=g^(2^i) mod n only if z+g=0 mod n (i>=1) > z^2=g^2 mod n only if z+g=0 mod n
______________________________________________________________________________________________
x^2=x^(2^i) mod n (b)
(x^2)^(2^(i1)) =x^2 mod n (a)
iteration will show
====> (x^2)^(2^(kik))=x^2 mod n k>=1
that is
x^(2^(ki(k1)) =x^2 mod n
let k=i
x^(2^((ii)(i1))=x^2 mod n (1)
multiplying both side by x^(2^(i1)) yields
x^(2^(ii))=x^(2^i) = x^2 mod n (2)
taking (1) and (2) and subrtacting one from the other yields
x^(2^((ii)(i1))(x^(2^(i1)1)=0 mod n
that is
x^(2^(i1))=1 mod n (3)
but (a) says
(x^2)^(2^(i1)) =x^2 mod n (a)
that is
(x^(2^(i1))^2 = x^2 mod n
substituting (3)
+++++> x^2 =1 mod n
how can this be?????

