Results 1 to 8 of 8

Math Help - Primes of the form 8n+1, 8n+3

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Primes of the form 8n+1, 8n+3

    Show that primes of the form 8n+1, 8n+3 are of the form x^2+2y^2.

    (Note : since primes of the form 4n+1 are of the form x^2+y^2, the difficulty of Lagrange's four square theorem is thus reduced to primes of the form 8n-1.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Alright, so nobody has answered this problem so I'll give my answer.

    For p=8n+1, both -1,\ 2 are quadratic residues; therefore -2 is a quadratic residue.

    For p=8n+3, neither -1,\ 2 are quadratic residues; therefore -2 is a quadratic residue.

    Therefore we can find n,m \in \mathbb N such that n^2=mp-2, i.e. mp=n^2+2=(n+\sqrt{-2})(n-\sqrt{-2}). Since \mathbb{Z}[\sqrt{-2}] is a unique factorization domain, and since neither factor on the left is divisible by p, we deduce that p is not prime in \mathbb{Z}[\sqrt{-2}], and admits a factorization p=(a+b\sqrt{-2})(c+d\sqrt{-2}). Taking norms we get p^2=(a^2+2b^2)(c^2+2d^2), so p=a^2+2b^2=c^2+2d^2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2005
    From
    Earth
    Posts
    1,599
    Nice problem. Was it meant to be a challenge problem though?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Bruno J. View Post
    Show that primes of the form 8n+1, 8n+3 are of the form x^2+2y^2.

    (Note : since primes of the form 4n+1 are of the form x^2+y^2, the difficulty of Lagrange's four square theorem is thus reduced to primes of the form 8n-1.)
    There is an inequality about congruences that you need to know in order to proof this result. Let a be an integer so that \gcd(a,p)=1 where p is an odd prime. Then you can solve the congruence ax\equiv y(\bmod p) with the inequality such that 0<|x|,|y|<\sqrt{p}.

    Let us prove this congruence inequality. Define n = [\sqrt{p}]+1 and consider ax-y for 0\leq x,y\leq n-1. There are n\cdot n = n^2 >p such choices for x and y, therefore, ax_1 - y_1 \equiv ax_2 - y_2(\bmod p) for x_1\not = x_2 \text{ or }y_1\not = y_2 by pigeonholing modulo p. Thus, a(x_1 - x_2) \equiv (y_1-y_2)(\bmod p). Set x_3=x_1-x_2 \text{ and }y_3=y_1-y_2. Thus, we get that ax_3 \equiv y_3(\bmod p). It must be the case that x_3,y_3\not = 0 because otherwise this would force x_1=x_2\text{ and }y_1=y_2 which would be a contradiction. Thus, |x_3|,|y_3|>0 but they also satisfy |x_3|,|y_3|<n-1<\sqrt{p} by construction. Thus, we have found a solution for ax\equiv y(\bmod p) which satisfies this inequality.

    If p\equiv 1(\bmod 8) then (-2/p) = (-1/p)(2/p) = (1)(1)=1 and if p\equiv 3(\bmod 8) then (-2/p) = (-1/p)(2/p) = (-1)(-1)=1. Thus, in either case there exists a\in \mathbb{Z} such that a^2\equiv -2(\bmod p). By above there exists a solution to ax\equiv y(\bmod p) with 0<|x|,|y|<\sqrt{p}. Then, -2x^2\equiv a^2x^2 = (ax)^2 \equiv y^2 (\bmod p). Thus, 2x^2+y^2\equiv 0(\bmod p). This means, by definition, there exists k\geq 1 such that 2x^2+y^2 = kp. However, 0 < 2x^2+y^2 < 2(\sqrt{p})^2 + (\sqrt{p})^2 = 3p. This forces, k=1,2. If k=1 then 2x^2 + y^2 = p and the proof is complete. Otherwise, 2x^2+y^2 = 2p. But then this forces y to be even, so y=2z. This implies 2x^2 + 4z^2 = 2p \implies x^2 + 2z^2 = p. In either case it is always possible to express p like so.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Jameson View Post
    Nice problem. Was it meant to be a challenge problem though?
    Yes; sorry I didn't specify, will do in the future.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Bruno J. View Post
    Alright, so nobody has answered this problem so I'll give my answer.

    For p=8n+1, both -1,\ 2 are quadratic residues; therefore -2 is a quadratic residue.

    For p=8n+3, neither -1,\ 2 are quadratic residues; therefore -2 is a quadratic residue.

    Therefore we can find n,m \in \mathbb N such that n^2=mp-2, i.e. mp=n^2+2=(n+\sqrt{-2})(n-\sqrt{-2}). Since \mathbb{Z}[\sqrt{-2}] is a unique factorization domain, and since neither factor on the left is divisible by p, we deduce that p is not prime in \mathbb{Z}[\sqrt{-2}], and admits a factorization p=(a+b\sqrt{-2})(c+d\sqrt{-2}). Taking norms we get p^2=(a^2+2b^2)(c^2+2d^2), so p=a^2+2b^2=c^2+2d^2.
    Now argue that p=a^2+2b^2 must be unique if a,b>0.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    It follows from the fact that at most two prime ideals can lie over a prime p\mathbb{Z} in a quadratic extension. Since (a+b\sqrt{-2}),\: (a-b\sqrt{-2}) are two ideals lying over p\mathbb{Z}, there can be no other such ideals. This implies that there can be no other element of norm p : any other such element would generate another principal ideal of norm p, which is impossible.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Bruno J. View Post
    It follows from the fact that at most two prime ideals can lie over a prime p\mathbb{Z} in a quadratic extension. Since (a+b\sqrt{-2}),\: (a-b\sqrt{-2}) are two ideals lying over p\mathbb{Z}, there can be no other such ideals. This implies that there can be no other element of norm p : any other such element would generate another principal ideal of norm p, which is impossible.
    There is just a little bit more work here to be done. First we need to know that (a+b\sqrt{-2})\not = (a-b\sqrt{-2}) but this is easy because otherwise 2a \in (a+b\sqrt{-2}) and so 2a,p\in (a+b\sqrt{-2}) which will force (a+b\sqrt{-2}) = \mathbb{Z}[\sqrt{-2}] because (2a,p) = 1. Also, if p=x^2+2y^2 then (x+y\sqrt{-2}) is a prime ideal and so (x+y\sqrt{-2}) = (a+b\sqrt{-2}) \text{ or }(x+y\sqrt{-2}) = (a-b\sqrt{-2}). Thus, x+y\sqrt{-2} = \pm (a\pm b\sqrt{-2}). So it is still possible to generate the same ideals with different elemetns, it is just that these elements differ by only a multiple of unit. Thus, x=\pm a, y=\pm b.

    I asked the question about uniqueness of expression because I seen lots of people simply say, "uniquness in factorization implies uniquness of expression" but a lot of times this kind of argument is not so easy. I have seen expression problems which do not even have a uniquness up to \pm 1, they were more complicated. Usually, if there are are many units then the express is "less unique".
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prove that there are infinitely many primes in the form 6k+5
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 13th 2011, 10:43 PM
  2. Replies: 2
    Last Post: March 10th 2011, 08:44 AM
  3. Primes of the form 4n+3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 29th 2010, 07:53 AM
  4. infinitely many primes of the form 6k + 5 and 6K + 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2009, 05:25 AM
  5. Infintely many primes of the form:
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 14th 2009, 03:54 PM

Search Tags


/mathhelpforum @mathhelpforum