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
    10
    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
    10
    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
    10
    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, 11:43 PM
  2. Replies: 2
    Last Post: March 10th 2011, 09:44 AM
  3. Primes of the form 4n+3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 29th 2010, 08: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, 06:25 AM
  5. Infintely many primes of the form:
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 14th 2009, 04:54 PM

Search Tags


/mathhelpforum @mathhelpforum