Talk:Primes Expressible as x^2 + n y^2 for all n from 1 to 10

From ProofWiki
Jump to navigation Jump to search

OEIS

On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008): A139665

This seems to be the same sequence. --Fake Proof (talk contribs) 15:14, 2 April 2022 (UTC)

They seem to match at the start, but it doesn't guarantee that they are the same sequence unless it is proved that they are indeed identical. I haven't looked in detail -- do they indeed? And can we show that $1801$ does indeed have this property? If so, then we can initiate and populate Primes Expressible as x^2 + n y^2 for all n from 1 to 10/Examples/1801, which at the moment we are taking on faith. --prime mover (talk) 16:01, 2 April 2022 (UTC)
There are a bunch a congruences that $p$ must satisfy for each $n$ if $p = x^2 + n y^2$:
1. (OEIS:A007645): $p = x^2 + 3 y^2 \iff p \equiv 0, 1 \pmod 3$
2. (OEIS:A033205): $p = x^2 + 5 y^2 \iff p \equiv 1, 9 \pmod {20}$
3. (OEIS:A033199): $p = x^2 + 6 y^2 \iff p \equiv 1, 7 \pmod {24}$
4. (OEIS:A033207): $p = x^2 + 7 y^2 \iff p \equiv 1, 7, 9, 11, 15, 23, 25 \pmod {28}$
5. (OEIS:A007519): $p = x^2 + 8 y^2 \iff p \equiv 1 \pmod 8 \implies p = x^2 + 2 y^2$
6. (OEIS:A068228): $p = x^2 + 9 y^2 \iff p \equiv 1 \pmod {12} \implies p = x^2 + y^2 \iff p = x^2 + 4 y^2$
7. (OEIS:A033201): $p = x^2 + 10 y^2 \iff p \equiv 1, 9, 11, 19 \pmod {40}$
We simply need to check whether all these combined give the congruence in A139665:
$p \equiv 1, 121, 169, 289, 361, 529 \pmod {840}$
Everything from this point onwards can be justified using Chinese Remainder Theorem:
1,3,5,6 combine to give $p \equiv 1 \pmod {24}$.
2,7 combine to give $p \equiv 1, 9 \pmod {40}$.
Therefore 1,2,3,5,6,7 combine to give $p \equiv 1, 49 \pmod {120}$.
Fermat's Two Squares Theorem and 4 combine to give $p \equiv 1, 9, 25 \pmod {28}$.
We end up with the congruences:
$p \equiv 1 \pmod 4, p \equiv 1, 19 \pmod {30}, p \equiv 1, 2, 4 \pmod 7$.
$\iff p \equiv 1, 49 \pmod {120}, p \equiv 1, 2, 4 \pmod 7$
$\iff p \equiv 1, 121, 169, 289, 361, 529 \pmod {840}$
and bingo. (All that is left is to show all the congruences are true.)
P.S.:
#include <stdio.h>
int main(){int n,x,y;for(n=1;n<11;n++)for(x=1;x<45;x++)for(y=1;y<33;y++)if(x*x+y*y*n==1801)printf("{{eqn | l = 1801\n      | r = %d^2 + %d \\times %d^2\n}}\n",x,n,y);}
\(\ds 1801\) \(=\) \(\ds 35^2 + 1 \times 24^2\)
\(\ds 1801\) \(=\) \(\ds 1^2 + 2 \times 30^2\)
\(\ds 1801\) \(=\) \(\ds 37^2 + 3 \times 12^2\)
\(\ds 1801\) \(=\) \(\ds 35^2 + 4 \times 12^2\)
\(\ds 1801\) \(=\) \(\ds 26^2 + 5 \times 15^2\)
\(\ds 1801\) \(=\) \(\ds 25^2 + 6 \times 14^2\)
\(\ds 1801\) \(=\) \(\ds 3^2 + 7 \times 16^2\)
\(\ds 1801\) \(=\) \(\ds 1^2 + 8 \times 15^2\)
\(\ds 1801\) \(=\) \(\ds 35^2 + 9 \times 8^2\)
\(\ds 1801\) \(=\) \(\ds 19^2 + 10 \times 12^2\)
--RandomUndergrad (talk) 17:24, 2 April 2022 (UTC)
Retrieved from "https://proofwiki.org/w/index.php?title=Talk:Primes_Expressible_as_x%5E2_%2B_n_y%5E2_for_all_n_from_1_to_10&oldid=566331"