Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Replies: 73   Last Post: Jul 24, 2011 8:55 PM

 Messages: [ Previous | Next ]
 Simon Roberts Posts: 67 Registered: 7/7/11
Posted: Jul 19, 2011 11:39 AM

there exists an i: 1<i<=(n-3)/2 when n is prime and (n-1)/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,...,(n-3)/2,(n-1)/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^(n-1) - y^(n-1) = 0 mod n
or
(x^2)^(n-1)/2 - (y^2)^(n-1)/2 = 0 mod n
or
(x^2)^(n-1)/2 + (x^2)^(n-1)/2 = 0 mod n
or
2x^(n-1)= 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 (n-1)/2 distinct members
(note: the only way it's a smaller subset of S' is if x^2=y^2 (mod n)

let y^(2^i) mod n be any a member of the set S''={1,...,n-1} that is
not a member of set of S'
(where i>1).

Then because S' has (n-1)/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 (n-1)/2 members and one of those members is 1
there will be an
i: 1<i<=(n-3)/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

EXPANDING THE ORIGINAL SET S
let z and g are any member of (the new set) (1,2,...,{n-1}) 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^(i-1)) =x^2 mod n (a)

iteration will show

====> (x^2)^(2^(ki-k))=x^2 mod n k>=1

that is

x^(2^(ki-(k-1)) =x^2 mod n

let k=i

x^(2^((ii)-(i-1))=x^2 mod n (1)

multiplying both side by x^(2^(i-1)) 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)-(i-1))(x^(2^(i-1)-1)=0 mod n

that is

x^(2^(i-1))=1 mod n (3)

but (a) says

(x^2)^(2^(i-1)) =x^2 mod n (a)

that is

(x^(2^(i-1))^2 = x^2 mod n

substituting (3)

+++++> x^2 =1 mod n

how can this be?????

Date Subject Author
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 byron
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 quasi
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/19/11 Simon Roberts
7/20/11 quasi
7/20/11 quasi
7/20/11 Simon Roberts
7/20/11 quasi
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 tommyrjensen@gmail.com
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/20/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 quasi
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 quasi
7/22/11 quasi
7/22/11 quasi
7/22/11 quasi
7/24/11 quasi
7/22/11 Simon Roberts
7/22/11 quasi
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 Simon Roberts
7/22/11 quasi
7/23/11 Simon Roberts
7/23/11 quasi
7/23/11 Simon Roberts
7/23/11 Simon Roberts
7/23/11 quasi
7/23/11 Simon Roberts
7/23/11 Simon Roberts
7/23/11 Simon Roberts
7/23/11 quasi
7/24/11 Bill Dubuque
7/24/11 Brian Q. Hutchings
7/23/11 quasi
7/24/11 quasi
7/22/11 quasi