Results 1 to 6 of 6

Math Help - number theory proof

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    8

    number theory proof

    quadratic residue...

    1. Prove that is x^2 = a(mod n), then (n-x)^2 = a(mod n)

    2. If p is a prime number and both a and b are quadratic residues mod p, prove that ab(mod p) is also a quadratic residue mod p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,935
    Thanks
    337
    Awards
    1
    Quote Originally Posted by memb3rme View Post
    quadratic residue...

    1. Prove that is x^2 = a(mod n), then (n-x)^2 = a(mod n)
    (n - x)^2 \equiv n^2 - 2nx + x^2~\text{(mod n)}

    \equiv 0^2 - 2 \cdot 0 \cdot x + a~\text{(mod n)}

    \equiv a~\text{(mod n)}

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    2. x^2\equiv{a}(\bmod.p)for some natural number x and y^2\equiv{b}(\bmod.p)for some natural number y (a and b are quadratic residues modp)

    Multiplying: x^2\cdot{y^2}=(x\cdot{y})^2\equiv{a\cdot{b}}(\bmod  .p)

    Thus ab must be a quadratic residue
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2008
    Posts
    8
    Quote:

    1. Prove that is x^2 = a(mod n), then (n-x)^2 = a(mod n)








    Ummm.... I don't understand where does the zero comes from......
    SO assume that n is zero?..
    some clarification here plz...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    n \equiv 0 (mod \ n)

    Is it clearer ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by memb3rme View Post
    Quote:
    Ummm.... I don't understand where does the zero comes from......
    SO assume that n is zero?..
    some clarification here plz...
    It is not that n is 0!
    But n belongs to the equivalence class of 0. Put in layman terms, when we are seeing only remainders, n leaves the same remainder as 0 when they are divided by n, so they are equivalent.

    To prove that directly from definition(if you are new to congruences)

    n|n(n-2x) \Rightarrow n|(n-x)^2 - x^2 \Rightarrow (n - x)^2 \equiv x^2 ~\text{(mod n)}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] number theory: proof required!
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2011, 02:42 PM
  2. Number Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 12th 2008, 07:07 PM
  3. number theory proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 13th 2008, 05:17 PM
  4. Number Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2008, 03:52 PM
  5. Number theory proof
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 12th 2006, 09:31 AM

Search Tags


/mathhelpforum @mathhelpforum