Talk:Primes Expressible as x^2 + n y^2 for all n from 1 to 10
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}$
- We simply need to check whether all these combined give the congruence in A139665:
- 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}$
- We end up with the congruences:
- 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)