2
$\begingroup$

My problem is:

Which positive integer $n$ can be expressed in the form $x^2-3y^2$?

First I consider the equation $$x^2-3y^2=p$$ with $p>2$ is a prime.

By quadritic residue, notice that $$\left(\frac{3}{p}\right)=(-1)^{\lfloor p/3\rfloor-\lfloor p/6\rfloor}$$ we can conclude that if $p=x^2-3y^2$, then $p=12k\pm 1$. If $p=12k-1$, then $3y^2+p\equiv 2 \pmod 3$, so no solution for $x$. Thus $p=12k+1$.

On the other hand, we need to prove that if $p=12k+1$, then $p$ can be written as $x^2-3y^2$. I tried to follow the proof of the Fermat-Euler theorem (that is, every prime of the form $4k+1$ can be written as the sum of two squares). Since $p=12k+1$, there exists a number $N$ such that $N^2\equiv 3 \pmod p$. Consider all numbers of the form $a+Nb$ with $0\le a,b\le \lfloor p\rfloor$. By the Pingeonhole principle, there exists $(a,b),(a',b')$ such that $a+Nb\equiv a'+Nb' \pmod p$, so $(a-a')^2-3(b-b')^2\equiv 0 \pmod p$. Here's where I got stuck, because $-3p\le (a-a')^2-3(b-b')^2\le p$, we can not conclude $(a-a')^2-3(b-b')^2=p$.

Moreover, I guess that if $p=12k-1$, then $2p$ can always be written as the form $x^2-3y^2$.

Back to the main problem. From all above, the condition of $n$ for which it can be expressed as $x^2-3y^2$ is: every prime factor of the form $12k-1$ has an even exponent; and if $s$ is the number of prime factors of the form $12k-1$, then the exponent of $2$ must be larger or equal to $s$.

Is this a correct conclusion?

$\endgroup$
2
$\begingroup$

I would point to a nice note from Brian Conrad, that you can find here.

$\endgroup$
  • $\begingroup$ Thanks for the nice note. But I'm still wondering of an elementary proof for it, or at least for the statement: "every prime of the form $12k+1$ can be written as $x^2-3y^2$" $\endgroup$ – Tien Kha Pham Jan 12 '15 at 15:44
  • 1
    $\begingroup$ As far as I know, there's no "elementary" proof of this. $\endgroup$ – ujsgeyrr1f0d0d0r0h1h0j0j_juj Jan 12 '15 at 16:27
  • $\begingroup$ @TienKhaPham, depends upon what you mean by elementary. Answer added. $\endgroup$ – Will Jagy Jan 12 '15 at 19:54
  • 1
    $\begingroup$ @TienKhaPham As far as I know, there is no proof of this relying on something less trivial than the quadratic reciprocity law - which is not far fetched to prove, I agree. You can find one in Disquisitiones Arithmeticae from Gauss for sure. Or in Elementary Number Theory from Venkov, as far as I remember, which nicely exposes Gauss's work. $\endgroup$ – ujsgeyrr1f0d0d0r0h1h0j0j_juj Jan 13 '15 at 9:19
1
$\begingroup$

You are a little off on your description of the represented numbers; there are two forms in this genus, $x^2 - 3 y^2$ and $-x^2 + 3 y^2,$ also the discriminant, $12,$ is divisible by both $2$ and $3.$ I will paste output giving factorization of represented (positive) numbers up to 1000, below.

Meanwhile, about the primes, it is elementary once you have quadratic reciprocity; it is not necessary to know anything about algebraic number fields, although that is he main interest these days for related material. Anyway, page 74, Theorem 4.23 in Binary Quadratic Forms by Duncan A. Buell, given an odd prime $p$ with $(12|p)= +1,$ the prime is represented by a (primitive) form of discriminant $12.$ If $p \equiv 1 \pmod {12},$ this means it is represented as $p=x^2 - 3 y^2.$ If $q \equiv 11 \pmod {12},$ this means it is represented by $q= -x^2 + 3 y^2.$

The behavior of this one is very similar to the positive forms $x^2 + 5 y^2$ or $x^2 + 6 y^2.$ That is, there are good primes, $p \equiv 1 \pmod {12},$ no restriction on exponent. Next, there are bad primes, $q \equiv 5,7 \pmod {12},$ the exponent for any one of these must be even. Finally, there are medium primes, in the set $$ M = \{ 2, 3, 11, 23, 47, 59, 71, 83, 107, 131 \ldots \} $$ for which the individual exponents are not restricted, however the total of the exponents for all medium primes must be even. The medium primes are $2,3$ and all $p \equiv 11 \pmod {12},$

Let's see, sources: quadratic reciprocity and the genus of binary forms are treated in detail in Primes of the Form $x^2 + n y^2$ by David A. Cox, a fine book, the only problem (and it is minor) is that he does not explicitly mention indefinite forms.

The relevant theorems are surely somewhere in Binary Quadratic Forms by Buchmann and Vollmer, so far I cannot find them.


ALL represented positive integers up to 1000

       1 =  1 
       4 = 2^2
       6 = 2 * 3
       9 = 3^2
      13 = 13
      16 = 2^4
      22 = 2 * 11
      24 = 2^3 * 3
      25 = 5^2
      33 = 3 * 11
      36 = 2^2 * 3^2
      37 = 37
      46 = 2 * 23
      49 = 7^2
      52 = 2^2 * 13
      54 = 2 * 3^3
      61 = 61
      64 = 2^6
      69 = 3 * 23
      73 = 73
      78 = 2 * 3 * 13
      81 = 3^4
      88 = 2^3 * 11
      94 = 2 * 47
      96 = 2^5 * 3
      97 = 97
     100 = 2^2 * 5^2
     109 = 109
     117 = 3^2 * 13
     118 = 2 * 59
     121 = 11^2
     132 = 2^2 * 3 * 11
     141 = 3 * 47
     142 = 2 * 71
     144 = 2^4 * 3^2
     148 = 2^2 * 37
     150 = 2 * 3 * 5^2
     157 = 157
     166 = 2 * 83
     169 = 13^2
     177 = 3 * 59
     181 = 181
     184 = 2^3 * 23
     193 = 193
     196 = 2^2 * 7^2
     198 = 2 * 3^2 * 11
     208 = 2^4 * 13
     213 = 3 * 71
     214 = 2 * 107
     216 = 2^3 * 3^3
     222 = 2 * 3 * 37
     225 = 3^2 * 5^2
     229 = 229
     241 = 241
     244 = 2^2 * 61
     249 = 3 * 83
     253 = 11 * 23
     256 = 2^8
     262 = 2 * 131
     276 = 2^2 * 3 * 23
     277 = 277
     286 = 2 * 11 * 13
     289 = 17^2
     292 = 2^2 * 73
     294 = 2 * 3 * 7^2
     297 = 3^3 * 11
     312 = 2^3 * 3 * 13
     313 = 313
     321 = 3 * 107
     324 = 2^2 * 3^4
     325 = 5^2 * 13
     333 = 3^2 * 37
     334 = 2 * 167
     337 = 337
     349 = 349
     352 = 2^5 * 11
     358 = 2 * 179
     361 = 19^2
     366 = 2 * 3 * 61
     373 = 373
     376 = 2^3 * 47
     382 = 2 * 191
     384 = 2^7 * 3
     388 = 2^2 * 97
     393 = 3 * 131
     397 = 397
     400 = 2^4 * 5^2
     409 = 409
     414 = 2 * 3^2 * 23
     421 = 421
     429 = 3 * 11 * 13
     433 = 433
     436 = 2^2 * 109
     438 = 2 * 3 * 73
     441 = 3^2 * 7^2
     454 = 2 * 227
     457 = 457
     468 = 2^2 * 3^2 * 13
     472 = 2^3 * 59
     478 = 2 * 239
     481 = 13 * 37
     484 = 2^2 * 11^2
     486 = 2 * 3^5
     501 = 3 * 167
     502 = 2 * 251
     517 = 11 * 47
     526 = 2 * 263
     528 = 2^4 * 3 * 11
     529 = 23^2
     537 = 3 * 179
     541 = 541
     549 = 3^2 * 61
     550 = 2 * 5^2 * 11
     564 = 2^2 * 3 * 47
     568 = 2^3 * 71
     573 = 3 * 191
     576 = 2^6 * 3^2
     577 = 577
     582 = 2 * 3 * 97
     592 = 2^4 * 37
     598 = 2 * 13 * 23
     600 = 2^3 * 3 * 5^2
     601 = 601
     613 = 613
     621 = 3^3 * 23
     622 = 2 * 311
     625 = 5^4
     628 = 2^2 * 157
     637 = 7^2 * 13
     649 = 11 * 59
     654 = 2 * 3 * 109
     657 = 3^2 * 73
     661 = 661
     664 = 2^3 * 83
     673 = 673
     676 = 2^2 * 13^2
     681 = 3 * 227
     694 = 2 * 347
     702 = 2 * 3^3 * 13
     708 = 2^2 * 3 * 59
     709 = 709
     717 = 3 * 239
     718 = 2 * 359
     724 = 2^2 * 181
     726 = 2 * 3 * 11^2
     729 = 3^6
     733 = 733
     736 = 2^5 * 23
     753 = 3 * 251
     757 = 757
     766 = 2 * 383
     769 = 769
     772 = 2^2 * 193
     781 = 11 * 71
     784 = 2^4 * 7^2
     789 = 3 * 263
     792 = 2^3 * 3^2 * 11
     793 = 13 * 61
     814 = 2 * 11 * 37
     825 = 3 * 5^2 * 11
     829 = 829
     832 = 2^6 * 13
     838 = 2 * 419
     841 = 29^2
     846 = 2 * 3^2 * 47
     852 = 2^2 * 3 * 71
     853 = 853
     856 = 2^3 * 107
     862 = 2 * 431
     864 = 2^5 * 3^3
     873 = 3^2 * 97
     877 = 877
     886 = 2 * 443
     888 = 2^3 * 3 * 37
     897 = 3 * 13 * 23
     900 = 2^2 * 3^2 * 5^2
     913 = 11 * 83
     916 = 2^2 * 229
     925 = 5^2 * 37
     933 = 3 * 311
     934 = 2 * 467
     937 = 937
     942 = 2 * 3 * 157
     949 = 13 * 73
     958 = 2 * 479
     961 = 31^2
     964 = 2^2 * 241
     976 = 2^4 * 61
     981 = 3^2 * 109
     982 = 2 * 491
     996 = 2^2 * 3 * 83
     997 = 997

ALL represented positive integers up to 1000


Ummmm. The "medium" primes, as i called them, are simply the (positive) primes represented by $3x^2 - y^2,$


 Represented (positive) primes up to  1000

           2           2
           3           3
          11          11
          23          11
          47          11
          59          11
          71          11
          83          11
         107          11
         131          11
         167          11
         179          11
         191          11
         227          11
         239          11
         251          11
         263          11
         311          11
         347          11
         359          11
         383          11
         419          11
         431          11
         443          11
         467          11
         479          11
         491          11
         503          11
         563          11
         587          11
         599          11
         647          11
         659          11
         683          11
         719          11
         743          11
         827          11
         839          11
         863          11
         887          11
         911          11
         947          11
         971          11
         983          11


      2      3     11



 Represented (positive) primes up to  1000  and value mod    12

           3           0          -1   original form 

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.