# Positive integers $n$ which can be written as $x^2-3y^2$

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?

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

• 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$" – Tien Kha Pham Jan 12 '15 at 15:44
• As far as I know, there's no "elementary" proof of this. – ujsgeyrr1f0d0d0r0h1h0j0j_juj Jan 12 '15 at 16:27
• @TienKhaPham, depends upon what you mean by elementary. Answer added. – Will Jagy Jan 12 '15 at 19:54
• @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. – ujsgeyrr1f0d0d0r0h1h0j0j_juj Jan 13 '15 at 9:19

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