Fermat ' pendiente infinita s para encontrar los cuadrados que suma a un primer

Question

Teorema de Fermat sobre la suma de dos cuadrados unidos de que una extraña prime $p = x^2 + y^2 \iff p \equiv 1 \pmod 4$

La aplicación de la bajada procedimiento que puede llegar a $a^2 + b^2 = pc$ donde $c \in \mathbb{Z} \gt 1$

Quiero $c = 1$, así que ¿cómo debo proceder? ¿Cómo puedo aplicar el procedimiento de forma iterativa?

Ejemplo:

$$ p = 97 $$

$$97 \equiv 1 \pmod 4 \implies \left(\frac{-1}{97}\right) = 1 \implies x^2 \equiv -1 \pmod {97}$$ tiene una solución

$$x^2 + 1 \equiv 0 \pmod {97}$$ $$x^2 + 1 = 97m$$ Nos encontramos con un $x,m$ que resuelve la ecuación. $$x = 75, m = 58$$ Ahora, cogemos una $a,b$ tal que $\frac{-m}{2} \leq a,b \leq \frac{m}{2}$ $$a \equiv x \pmod m = 17$$ $$b \equiv y \pmod m = 1$$

Observaciones:

1. $ a^2 + b^2 \equiv x^2 + 1 \equiv 0 (\mod m)$

2. $ (a^2 + b^2) = mc$

3. $ (x^2 + 1) = mp$

Conectar $a,b,m$ por 2, obtenemos $c = 5$

Por esta identidad, sabemos que

$(a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2$

**$(a^2 + b^2)(x^2 + 1^2) = (ax + b)(a - bx) = m^2pc$

Dividiendo ** $m^2$, $pc = (\frac{ax+b}{m})^2 + (\frac{a-bx}{m})^2$

Conectar $a,b,m,p,c$ tenemos que $22^2 + (-1)^2 = 97*5$

Así que tenemos dos plazas que añadir hasta 5 veces nuestra $p$. ¿Cómo nos dirigimos a las 5 en 1? ¿Cuál es el siguiente paso en el descenso?

Answer 1

Esta es la manera de proceder.

Nos enteramos de que la $22^2+(−1)^2=97∗5$

Aviso que es una suma de cuadrados - lo que vamos a utilizar la ecuación de antes de $x^2 + 1 = 97m$. En general, el $1$ podría ser algo más. En este caso, ya que los $(-1)^2 = 1$, en realidad nada cambia y podemos utilizar la misma ecuación.

En la segunda iteración:
$m = 2$
$x = 22$
$y = 1$ (se puede quitar de forma segura el negativo)

Nuestra $m$ ahora $5$. Así como antes, tenemos que escoger enteros $a,b$ tal que $a,b \in [-m/2,m/2] \implies a,b \in [-2.5, 2.5]$

$a \equiv x \equiv 2 \pmod 5$
$b \equiv y \equiv 1 \pmod 5$

Aplicar el Fibonacci de la identidad de antes:
** $(a^2 + b^2)(x^2 + y^2) = (ax+by)^2 + (ay-bx)^2 = (2*22+1*1)^2 + (2*1-1*22)^2 = (45)^2 + (-20)^2 = m^2pr = 25*97*c$

De nuevo, resolver por $c$. En este caso,$c = 1$.

Impresionante! Esta es la última iteración.

Dividir ** $m^2$, $p =(\frac{45}{5})^2+(\frac{-20}{5})^2 = (9)^2 + (-4)^2$

Por eso, $a=9, b=4$ solucionar $a^2 + b^2 = 97$

Answer 2

$$22^2+1=97\times 5$$

Utilizar la identificación $$(2a+b)^2+(a-2b)^2=5a^2+5b^2$ $

Lo números $a,b$ evidentemente resolver la ecuación de $a^2+b^2=97$, si $$2a+b=22\ ,\ a-2b=1$ $

Para resolver este sistema da $a=9\ ,\ b=4$

Answer 3

Necesitamos saber que el si $q$ es el primer y $q\equiv 3\pmod 4$$q|(x^2+y^2)\to (q|x\land q|y)$. Ahora para el prime $p\equiv 1\pmod 4$ tenemos $c p=a^2+b^2$ donde $p/2>a>0<b<p/2$. Esto implica $0<c<p$. Pedimos el más pequeño posible positivos $c$. Nos muestran que si $c>1$ $c$ no es el mínimo. En primer lugar,si $q$ es el primer y $q|c$ donde$q\equiv 3\pmod 4$,$q|c\to q|(a^2+b^2) \to (q|a\land q|b) \to q^2|c\to (c/q^2)p=(a/q)^2+(b/q)^2$; y $0<c/q^2<c$ $c$ no es el mínimo. En la segunda, supongamos que cada prime $r$ tal que $r<p$ $r\not \equiv 3\pmod 4$ es la suma de dos cuadrados. (Esta es la Hipótesis Inductiva.) Entonces, si el primer $r$ divide $c$ $r\not \equiv 3\pmod 4$ $r=(s^2+t^2) $ para algunos enteros positivos $s,t,$....Recordemos que $r$ también se divide $a^2+b^2$. Deje $s\equiv i t\pmod r$ $a\equiv j b\pmod r$ donde $i^2\equiv j^2\equiv -1\pmod r$ $j\equiv \pm i\pmod r. $ En el caso de $j\equiv i\pmod r$, con $c'=c/r,$ $$ p c' r^2=p c r=c'(a^2+b^2)(s^2+t^2)=c'((a s +b t)^2+(a t-b s)^2).$$ Now $(a s +b t)\equiv j i b t+b t\equiv i^2 b t+ b t\equiv 0\pmod r$ and similarly $t-b s\equiv 0\pmod r$. Therefore for some $u,v$ we have $$0\ne (r u)^2+(r v)^2=(a s+b t)^2+(a t-b s)^2=p c' r^2$$ from which $$0\ne p c'=u^2+v^2$$ Since $0<c'<c$, we see that $c$ is not minimum.....In the case $j\equiv -i\pmod r$ we use the equality $(a^2+b^2)(s^2+t^2)=(s-b t)^2+(t+b s)^2.$