Let $p$ be prime and $0<a< p$ an integer such that $ \Big({a\over p}\Big) =1$ Then there exists integers $x,y$ such that $p=x^2-ay^2$.

Question

Let $p$ be prime and $0<a< p$ an integer such that $$ \Big({a\over p}\Big) =1$$ Then there exists integers $x,y$ such that $p=x^2-ay^2$.

---

Edit: For which primes is this true? From CalebKoch answer we see this is not true in general. Can you sugest me a literature where I can find a theory of this. I suspect, if it is true, then it has something to do with a Thue theorem. http://mathworld.wolfram.com/ThuesTheorem.html

A found this interesting results:

https://en.m.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

Answer 1

I don't think this is true. Consider the following counter example: let $p=11$ and $a=3$. Then $a$ is a quadratic residue mod $p$ since $3\equiv 5^2\pmod{11}$. Consider then the equation $11=x^2-3y^2$. Taking this modulo 3 gives $2\equiv x^2 \pmod{3}$. No such $x$ exists so the equation cannot be satisfied.

Answer 2

the condition is backwards in any case. To get $p = x^2 - a y^2,$ for each odd prime $q|a,$ we must have $(p|q) = 1.$ In the example, you do have $(3|11) = 1,$ but quadratic reciprocity says $(11|3) = -1.$

Well, here is an example, cleaner than most. First primes up to 1000 given by $x^2 - 5 y^2 \; ,$ then $x^2 - 13 y^2 \; ,$ then $x^2 - 65 y^2 \; .$

jagy@phobeusjunior:~$ ./Conway_Positive_Primes 1 0 -5   1000   65
           1           0          -5   original form 

           1           4          -1   Lagrange-Gauss reduced 



 Represented (positive) primes up to  1000

     5    11    19    29    31    41    59    61    71    79
    89   101   109   131   139   149   151   179   181   191
   199   211   229   239   241   251   269   271   281   311
   331   349   359   379   389   401   409   419   421   431
   439   449   461   479   491   499   509   521   541   569
   571   599   601   619   631   641   659   661   691   701
   709   719   739   751   761   769   809   811   821   829
   839   859   881   911   919   929   941   971   991

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=   
 these are the collection of remainders when dividing by   65

      1      4      5      6      9     11     14     16     19     21
     24     29     31     34     36     41     44     46     49     51
     54     56     59     61     64



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

           1           0          -5   original form 

jagy@phobeusjunior:~$ ./Conway_Positive_Primes 1 0 -13   1000   65
           1           0         -13   original form 

           1           6          -4   Lagrange-Gauss reduced 



 Represented (positive) primes up to  1000

     3    13    17    23    29    43    53    61    79   101
   103   107   113   127   131   139   157   173   179   181
   191   199   211   233   251   257   263   269   277   283
   311   313   337   347   367   373   389   419   433   439
   443   467   491   503   521   523   547   563   569   571
   599   601   607   641   647   653   659   673   677   701
   719   727   751   757   797   809   823   829   857   859
   881   883   887   907   911   919   937   953   971   991
   997

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=   
 these are the collection of remainders when dividing by   65

      1      3      4      9     12     13     14     16     17     22
     23     27     29     36     38     42     43     48     49     51
     53     56     61     62     64



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

           1           0         -13   original form 

jagy@phobeusjunior:~$ ./Conway_Positive_Primes 1 0 -65   1000   65
           1           0         -65   original form 

           1          16          -1   Lagrange-Gauss reduced 



 Represented (positive) primes up to  1000

    29    61    79   101   131   139   179   181   191   199
   211   251   269   311   389   419   439   491   521   569
   571   599   601   641   659   701   719   751   809   829
   859   881   911   919   971   991

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=   
 these are the collection of remainders when dividing by   65

      1      4      9     14     16     29     36     49     51     56
     61     64



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

           1           0         -65   original form 

Answer 3

Your problem is realated to the factorization of primes in the order $\mathbb Z[\sqrt{a}]$ and class fields of real quadratic fields.

I think the following is true but you should check it out as I am not an expert: If $\left({a\over p}\right)=1$ and $z$ is such that $p \mid z^2 -a$ and $p^2\nmid z^2-a$, then consider the ideal $ \mathfrak p = (p,z+\sqrt{a})$, if $\mathfrak p$ is principal then at least one of the equations $$ \pm p = x^2-ay^2 $$ has solution, possibly both. Otherwise none of these equations has solution.

I believe that even determining if a solution with positive sign exists when a solution exists is a very dificult problem.

I also believe that finding a simple characterization of which primes are repreentable is very difficult in general. It mostly depends on $a$, if the real field $Q(\sqrt{a})$ has class number 1 and the norm of it's fundamental unit is $-1$ then every prime with $\left({a\over p}\right)=1$ will be representable in the form $p=x^2-ay^2$.

I think it is easier and better known the parallel problem for imaginary quadratic fields, ie represent primes as $p= x^2+ay^2$ when $\left({-a \over p}\right) = 1$. For this problem I strongly recommend you the wonderful book Primes of the Form $x^2+ny^2$: Fermat, Class Field Theory, and Complex Multiplication By David A. Cox. You'll get a very good idea of what is involved in your problem!