Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: a contradiction worth reading (unless a silly mistake was made)
Replies: 73   Last Post: Jul 24, 2011 8:55 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Simon Roberts

Posts: 67
Registered: 7/7/11
a contradiction worth reading (unless a silly mistake was made)
Posted: Jul 19, 2011 11:39 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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)
x!=y (a condtradiction))

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
leads to a contradiction)

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
Read a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
byron
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/19/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/20/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/20/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/20/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/20/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/20/11
Read This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
tommyrjensen@gmail.com
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
tommyrjensen@gmail.com
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
tommyrjensen@gmail.com
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
tommyrjensen@gmail.com
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
tommyrjensen@gmail.com
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/20/11
Read Re: This beautiful proof vs. my convoluted one
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/24/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Simon Roberts
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/24/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Bill Dubuque
7/24/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
Brian Q. Hutchings
7/23/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/24/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi
7/22/11
Read Re: a contradiction worth reading (unless a silly mistake was made)
quasi

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.