|
|
Re: a contradiction worth reading (unless a silly mistake was made)
Posted:
Jul 19, 2011 4:25 PM
|
|
On Jul 19, 3:08 pm, Simon Roberts <2ass...@gmail.com> wrote:
> On Jul 19, 11:39 am, Simon Roberts <2ass...@gmail.com> wrote:
>
>
>
> > 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)
>
> should read x^2 = (x^2)^(2^i)
> or
> x^2 = x^(2^(i+1))
>
> but this still doesn't take away the counter example of x=2 n=7;
> 2^5-2^2=0 mod 7;5>(n-1)/2
oh yes it does. x^2=x^(2^j) 1<j<(n+1)/2
thanks again!
>
> unless bounds are changed to 1<i<=(n-1)/2 no. that still doesn't help
>
> 5 = n-2 = (n +3)/2????
>
>
>
>
>
> > 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- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
|
|
