Results 1 to 3 of 3

Math Help - b +/- x^2 = 0 (mod n) n-1/2 is odd

  1. #1
    Newbie
    Joined
    Jun 2009
    Posts
    5

    b +/- x^2 = 0 (mod n) n-1/2 is odd

    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.
    Last edited by robersi; August 18th 2009 at 03:53 PM. Reason: clarity
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Is this a question?

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2009
    Posts
    5
    I have a better written proof of this now.
    Putting it out there to see if it's been done before.

    Does a proof already exist?
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum