¿Hay algún algoritmo para representar el dado enteros en el formulario $N=x^2-ny^2$, $n>1$, dicen por $n=2$. Como tenemos por cualquier prime, $p$, una de las principales $q$ puede ser escrito como $q=x^2+py^2$,siempre que $q$ es un residuo cuadrático de $p$ llamado cornacchia algoritmo
Respuestas
¿Demasiados anuncios?
Stephan Aßmus
Puntos
16
Las cosas no son tan simples como parecen pensar, incluso de formas positivas. Entre primos con $ (p|23) = 1,$ aproximadamente $1/3$ están íntegramente representado por $x^2 + 23 y^2.$ a Continuación son todos los números primos en cuestión, hasta 1000. Entre los números primos $p \neq 2,3,23,$ $ (p|23) = 1,$ con $p = x^2 + 23 y^2 $ son aquellos para los cuales $x^3 - x + 1$ tiene tres raíces $\pmod p.$ También tenga en cuenta que $x^2 + 23 y^2$ $x^2 + x y + 6 y^2$ representan exactamente el mismo impar de números. A continuación, $ 3x^2 + 2xy + 8 y^2$ $2 x^2 + x y + 3 y^2$ representan exactamente el mismo impar de números. Ver Hudson y Williams, 1991 en http://zakuski.utsa.edu/~jagy/inhom.html
p = x^2 + 23 y^2
p p % 23
----------------------------
23 0
59 13
101 9
167 6
173 12
211 4
223 16
271 18
307 8
317 18
347 2
449 12
463 3
593 18
599 1
607 9
691 1
719 6
809 4
821 16
829 1
853 2
877 3
883 9
991 2
997 8
0 1 2 3 4 6 8 9 12 13 16 18 : mod 23
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
p = 3 x^2 + 2 x y + 8 y^2
p p % 23
----------------------------
3 3
13 13
29 6
31 8
41 18
47 1
71 2
73 4
127 12
131 16
139 1
151 13
163 2
179 18
193 9
197 13
233 3
239 9
257 4
269 16
277 1
311 12
331 9
349 4
353 8
397 6
409 18
439 2
443 6
461 1
487 4
491 8
499 16
509 3
541 12
547 18
577 2
587 12
601 3
647 3
653 9
673 6
683 16
739 3
761 2
811 6
823 18
857 6
859 8
863 12
887 13
929 9
947 4
967 1
1 2 3 4 6 8 9 12 13 16 18 : mod 23
Ejemplo, el primer $p= 159287$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
159287 113296 20146
0 form 159287 113296 20146 delta 2
1 form 20146 -32712 13279 delta -2
2 form 13279 -20404 7838 delta -2
3 form 7838 -10948 3823 delta -2
4 form 3823 -4344 1234 delta -2
5 form 1234 -592 71 delta -5
6 form 71 -118 49 delta -2
7 form 49 -78 31 delta -2
8 form 31 -46 17 delta -2
9 form 17 -22 7 delta -2
10 form 7 -6 1 delta -2
11 form 1 2 -1
85 -101
-239 284
To Return
284 101
239 85
0 form 1 2 -1 delta -2
1 form -1 2 1 delta 2
2 form 1 2 -1
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
El discriminante es $D=8.$ formulario $\langle a,b,c \rangle$ es reducido si $0 < b < \sqrt D$ $\sqrt D - b < 2 |a| < \sqrt D + b.$
TEOREMA. Los siguientes son equivalentes, cuando $D$ es positivo y no un cuadrado, y, por supuesto,$D = b^2 - 4 a c$:
(I) $0 < b < \sqrt D$ $\sqrt D - b < 2 |a| < \sqrt D + b.$
(II) $0 < b < \sqrt D$ $\sqrt D - b < 2 |c| < \sqrt D + b.$
(III) $ac < 0$ $b > |a+c|.$
Si el formulario no se reduce (por cualquiera de las tres pruebas anteriores (I), (II), (III), se puede reducir, a un paso por vez, por la búsqueda de la (única) integrante $\delta$ tal que $$ \sqrt D - 2 |c| < -b + 2 c \delta < \sqrt D. $$ El siguiente formulario se $$\langle c, -b + 2 c \delta, a - b \delta + c \delta^2 \rangle$$ El cambio de las variables de la matriz que lleva a cabo esta sobre el nivel de las bacterias Gram matrices es $$ \left( \begin{array}{cc} 0 & -1 \\ 1 & \delta \end{array}\right) $$
In the example, we get from the original $\langle 159287, 113296, 20146 \rangle$ to the reduced $\langle 1, 2, -1 \rangle$, por medio de la matriz de $$ \left( \begin{array}{cc} 85 & -101 \\ -239 & 284 \end{array}\right) $$ Para llegar desde $\langle 1, 2, -1 \rangle$ a (no reducido) $\langle 1, 0, -2 \rangle$ $$ \left( \begin{array}{cc} 1 & -1 \\ 0 & 1 \end{array}\right) $$ para llegar a $$ \left( \begin{array}{cc} 85 & -186 \\ -239 & 523 \end{array}\right). $$
Inversa $$ \left( \begin{array}{cc} 523 & 186 \\ 239 & 85 \end{array}\right). $$
Así, $$ \left( \begin{array}{cc} 523 & 239 \\ 186 & 85 \end{array}\right) \left( \begin{array}{cc} 1 & 0 \\ 0 & -2 \end{array}\right) \left( \begin{array}{cc} 523 & 186 \\ 239 & 85 \end{array}\right) = \left( \begin{array}{cc} 159287 & 56648 \\ 56648 & 20146 \end{array}\right) $$
So $$ 523^2 - 2 \cdot 239^2 = 159287. $$
NOTE: if $n>0 $ is not a square, and $s_0 = \lfloor \sqrt n \rfloor,$ then $\langle 1, 0, -n \rangle$ is not reduced but $\langle 1, 2 s_0, s_0^2 - n \rangle$ es reducido. La más rápida transformación es sólo $$ \left( \begin{array}{cc} 1 & s_0 \\ 0 & 1 \end{array}\right) $$
Tres libros con parte o la totalidad de estos son : (1929) Introducción a la Teoría de los Números, por Leonard Eugene Dickson; (1989) Binario Cuadráticas Formas, por Duncan A. Buell; (2007) Binario Cuadráticas Formas, por Johannes Buchmann y Ulrich Vollmer.
Stephan Aßmus
Puntos
16
$x^2 - 2 y^2$ es bastante fácil. Tanto en $2$ $-1$ están representados. A continuación, si tenemos un (positivo) prime $p \equiv \pm 1 \pmod 8,$ sabemos $(8|p) = 1.$, por tanto, resolver $$ b^2 \equiv 8 \pmod {4 p}. $$ This is just solving $$ \beta^2 \equiv 8 \pmod p, $$ using TONELLI SHANKS or CIPOLLA, then choosing $p - \beta$ if $\beta$ is odd. So, now we have $$ b^2 - 4 p c = 8 $$ for some integer $c.$ That is, we have an indefinite binary form $$ \langle p,b,c \rangle $$ of discriminant 8. It reduces, by some $P \en SL_2 \mathbb Z,$ to $ \langle 1,0,-2 \rangle. $ So $P^{-1}$ does the reverse process, and the left hand column of $P^{-1}$ shows how to write $p = x^2 - 2 y^2.$ Me gusta la descripción de reducción indefinida formas en Duncan A. Buell, la Formas Cuadráticas Binarias, que es lo que yo uso, pero la versión es en muchos libros.
Finalmente, para la multiplicación, $$ (u^2 - 2 v^2)(x^2 - 2 y^2) = (ux-2vy)^2 - 2 (uy-vx)^2. $$
