Results 1 to 9 of 9

Math Help - Writing p = x^2 + y^2

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Writing p = x^2 + y^2

    We know that for primes p \equiv 1 mod(4), there exists a pair of integers (x,y) such that x^2 + y^2 = p.

    Is there a sufficiently fast method for finding this pair, or is the problem of writing p as a sum of squares considered to be a hard problem like "Integer Factorization"?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    My understanding is it's hard to find  (x,y) .

    This is because in  \mathbb{Z}[i] ,  p=(x+iy)(x-iy) where  x\pm iy are prime.

    So this is a factoring problem like you mentioned.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148

    Exclamation

    Quote Originally Posted by chiph588@ View Post
    My understanding is it's hard to find  (x,y) .

    This is because in  \mathbb{Z}[i] ,  p=(x+iy)(x-iy) where  x\pm iy are prime.

    So this is a factoring problem like you mentioned.
    On the surface of it, I agree. However lets not be too quick to judge.

    I've been thinking about this somewhat and we know that for primes p = 1 + 4 \cdot k we can quickly solve the equation x^2 + 1 \equiv 0 mod(p).

    For instance, if p \equiv 5 mod(8) then x \equiv 2^{\frac{p-1}{4}} mod(p)

    On the other hand, if p = a^2 + b^2 then a \cdot b^{-1} \equiv +x, -x mod(p)

    Rearranging the variables (a,b) if necessary, lets suppose a \cdot b^{-1} \equiv +x mod(p)

    Since we know the value of x, the problem comes down to choosing an integer a < \sqrt{p} such that a \cdot x^{-1} mod(p) is fairly small.

    Having done the above, we have a^2 + b^2 = k \cdot p for some integer k which isn't too large.

    On the other hand using the identity (a_1^{2} + b_1^{2}) \cdot (a_2^{2} + b_2^{2}) = (a_1 \cdot a_2 + b_1 \cdot b_2)^{2} + (a_1 \cdot b_2 - b_1 \cdot a_2)^{2}

    We know there exist values (a_1,b_1) such that a_1^{2} + b_1^{2} = k as k can only be product of primes of the form 3 + 4s to an even exponent (Do you know why?).

    Thus if we can express k as a sum of squares, it will follow from the above identity that p = a_2^{2} + b_2^{2} and the pair (a_2,b_2) can be found by solving the following two linear Diophantine equations:

    a_1 \cdot a_2 + b_1 \cdot b_2 = a and a_1 \cdot b_2 -b_1 \cdot a_2 = b

    I believe solving for the two simultaneous Diophantine equations in this case is trivial, but I'm a little tired to fill in the details at the moment.

    .................................................. ...

    Reflecting back on everything I just wrote, I think the real problem is finding an integer a < \sqrt{p} such that a \cdot x^{-1} mod(p) is fairly small. As I've right now, I'm not sure of any obvious way to do this. If it is a nontrivial problem, then I would echo your line in that this is due to factorization of integers in  \mathbb{Z}[i] to be an intractable problem (ie no fast methods to obtain solutions).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Feb 2009
    From
    Chennai
    Posts
    148
    If  p,c \in \mathbb{Z}[i] are relatively prime and if  x^{2}+y^{2}=cp, then  p=a^{2}+b^{2}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2008
    Posts
    148
    Quote Originally Posted by Chandru1 View Post
    If  p,c \in \mathbb{Z}[i] are relatively prime and if  x^{2}+y^{2}=cp, then  p=a^{2}+b^{2}
    Yeah. In fact even for p,c \in \mathbb{Z} we have that p = a^2 + b^2 if p \cdot c = x^2 + y^2 and gcd(p,c) = 1.

    ........................................

    I think one can solve this problem using a non-deterministic algorithm. If one removes the restriction that a < \sqrt{p} necessarily. I have one kinda worked out on paper, but its messy. I'll post it soon.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Let p be an odd prime. Let x^2 + y^2 \equiv 0 \pmod{p} for any x, y \in \mathbb{Z}/p\mathbb{Z}, that is, x^2 + y^2 - kp = 0.

    Then the solutions are given by x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}
    This can be computed using the Tonelli-Shanks algorithm, a polynomial time algorithm that yields square roots modulo a prime number.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Bacterius View Post
    Let p be an odd prime. Let x^2 + y^2 \equiv 0 \pmod{p} for any x, y \in \mathbb{Z}/p\mathbb{Z}, that is, x^2 + y^2 - kp = 0.

    Then the solutions are given by x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}
    This can be computed using the Tonelli-Shanks algorithm, a polynomial time algorithm that yields square roots modulo a prime number.


    Slightly simpler: x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}=\pm\sqrt{kp-y^2}\!\!\pmod p

    Tonio
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Quote Originally Posted by tonio View Post
    Slightly simpler: x \equiv \frac{\pm \sqrt{4(kp - y^2)}}{2} \pmod{p}=\pm\sqrt{kp-y^2}\!\!\pmod p
    Indeed, I didn't spot that, thanks

    Also, you need kp - y^2 to be a quadratic residue modulo p. But this is not an issue since there are exactly 50% of quadratic residues modulo any odd prime p
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2008
    Posts
    148
    Thanks for the effort, but I wasn't trying to find (x,y) such that x^2 + y^2 \equiv 0. This is trivial once we have solved x^2 + 1 \equiv 0 since for any nonzero element a, if we choose b \equiv a \cdot x^{-1}, it follows that a^2 + b^2 \equiv 0 since x^{-1} \equiv -x.

    The above only applies for primes of the form 1 + 4 \cdot k. These are the primes I'm interested in since p = x^2 + y^2 if and only if p = 1 + 4 \cdot k. Trying to write these primes as sums of squares was what I was trying to accomplish in this thread, alas yet to no avail.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Writing this Equation, need help!
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 28th 2009, 05:46 PM
  2. Writing the equation
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 26th 2009, 04:54 AM
  3. Writing an inequality?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: June 5th 2008, 07:24 AM
  4. Writing a bit pattern
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 25th 2008, 10:49 AM
  5. writing a sequence
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 13th 2008, 05:40 AM

Search Tags


/mathhelpforum @mathhelpforum