Hace unos años, uno de mis amigos a encontrar ese $\sqrt{p}$ ha periódico continuó fracción con un número impar (resp. incluso) período de iff $p\equiv 1(mod 4)$ (resp. $p\equiv 3(mod 4)$) para un primer $p$. (Se puede observar este de aquí : http://oeis.org/search?q=1%2C2%2C1%2C2%2C4%2C2%2C1%2C2%2C2%2C5%2C4%2C2%2C1%2C2%2C6%2C2&language=english&go=Search). Sin embargo, no conozco ninguna pista para probar esto. Él dijo que puede ser relacionada a la ecuación de Pell. ¿Tienes alguna idea?
Respuesta
¿Demasiados anuncios?
Sí. Si el primer $p \equiv 1 \pmod 4,$ hay tanto (no trivial) soluciones a $x^2 - p y^2 = 1$ $u^2 - p v^2 = -1.$ Si usted guarde la pista de la "convergents" $\frac{a}{b}$ mientras que la búsqueda de la continuación de la fracción, que en realidad encontrar $a^2 - p b^2 = -1$ a lo largo del camino, aproximadamente a la mitad.
13
$$ \pequeño \begin{array}{cccccccccccccccccccccccccccccc} & & 3 & & 1 & & 1 & & 1 & & 1 & & 6 & & 1 & & 1 & & 1 & & 1 & & 6 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{3}{1} & & \frac{4}{1} & & \frac{7}{2} & & \frac{11}{3} & & \frac{18}{5} & & \frac{119}{33} & & \frac{137}{38} & & \frac{256}{71} & & \frac{393}{109} & & \frac{649}{180} & & \frac{4287}{1189} \\ \\ & 1 & & -4 & & 3 & & -3 & & 4 & & -1 & & 4 & & -3 & & 3 & & -4 & & 1 & & -4 \end{array} $$
29
$$ \sqrt {29} $$
$$ \scriptsize \begin{array}{cccccccccccccccccccccccccccccc} & & 5 & & 2 & & 1 & & 1 & & 2 & & 10 & & 2 & & 1 & & 1 & & 2 & & 10 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{5}{1} & & \frac{11}{2} & & \frac{16}{3} & & \frac{27}{5} & & \frac{70}{13} & & \frac{727}{135} & & \frac{1524}{283} & & \frac{2251}{418} & & \frac{3775}{701} & & \frac{9801}{1820} & & \frac{101785}{18901} \\ \\ -29 & 1 & & -4 & & 5 & & -5 & & 4 & & -1 & & 4 & & -5 & & 5 & & -4 & & 1 & & -4 \end{array} $$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
THEOREM 1: With prime $p \equiv 1 \pmod 4,$ there is always a solution to $$ x^2 - p y^2 = -1 $$ in integers. The proof is from Mordell, Diophantine Equations, pages 55-56.
PROOF: Take the smallest integer pair $T>1,U >0$ such that $$ T^2 - p U^2 = 1. $$ Sabemos que $T$ es impar y $U$ es incluso. Por lo tanto, tenemos la ecuación entero $$ \left( \frac{T+1}{2} \right) \left( \frac{T-1}{2} \right) = p \left( \frac{U}{2} \right)^2. $$
We have $$ \gcd \left( \left( \frac{T+1}{2} \right), \left( \frac{T-1}{2} \right) \right) = 1. $$ De hecho, $$ \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1. $$
There are now two cases, by unique factorization in integers:
$$ \mbox{(A):} \; \; \; \left( \frac{T+1}{2} \right) = p a^2, \; \; \left( \frac{T-1}{2} \right) = b^2 $$
$$ \mbox{(B):} \; \; \; \left( \frac{T+1}{2} \right) = a^2, \; \; \left( \frac{T-1}{2} \right) = p b^2 $$
Now, in case (B), we find that $(a,b)$ are smaller than $(T,U),$ but $T \geq 3, a > 1,$ and $a^2 - b p^2 = 1.$ This is a contradiction, as our hypothesis is that $(T,U)$ is minimal.
As a result, case (A) holds, with evident $$p a^2 - b^2 = \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1, $$ así $$ b^2 - p a^2 = -1. $$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$
THEOREM 2: With primes $p \neq q,$ with $p \equiv q \equiv 1 \pmod 4$ and Legendre $(p|q)=(q|p) = -1,$ there is always a solution to $$ x^2 - pq y^2 = -1 $$ in integers. The proof is from Mordell, Diophantine Equations, pages 55-56.
PROOF: Take the smallest integer pair $T>1,U >0$ such that $$ T^2 - pq U^2 = 1. $$ Sabemos que $T$ es impar y $U$ es incluso. Por lo tanto, tenemos la ecuación entero $$ \left( \frac{T+1}{2} \right) \left( \frac{T-1}{2} \right) = pq \left( \frac{U}{2} \right)^2. $$
We have $$ \gcd \left( \left( \frac{T+1}{2} \right), \left( \frac{T-1}{2} \right) \right) = 1. $$
There are now four cases, by unique factorization in integers:
$$ \mbox{(1):} \; \; \; \left( \frac{T+1}{2} \right) = a^2, \; \; \left( \frac{T-1}{2} \right) = pq b^2 $$
$$ \mbox{(2):} \; \; \; \left( \frac{T+1}{2} \right) = p a^2, \; \; \left( \frac{T-1}{2} \right) = q b^2 $$ $$ \mbox{(3):} \; \; \; \left( \frac{T+1}{2} \right) = q a^2, \; \; \left( \frac{T-1}{2} \right) = p b^2 $$ $$ \mbox{(4):} \; \; \; \left( \frac{T+1}{2} \right) = pq a^2, \; \; \left( \frac{T-1}{2} \right) = b^2 $$
Now, in case (1), we find that $(a,b)$ are smaller than $(T,U),$ but $T \geq 3, a > 1,$ and $^2 - pq b^2 = 1.$ This is a contradiction, as our hypothesis is that $(T,U)$ is minimal.
In case $(2),$ tenemos $$ p a^2 - q b^2 = 1. $$ $$ p a^2 \equiv 1 \pmod q, $$ so $un$ is nonzero mod $q$, a continuación, $$ p \equiv \left( \frac{1}{a} \right)^2 \pmod q. $$ Esto contradice la hipótesis de $(p|q) = -1.$
En el caso de $(3),$ hemos $$ q a^2 - p b^2 = 1. $$ $$ q a^2 \equiv 1 \pmod p, $$ so $un$ is nonzero mod $p$ entonces $$ q \equiv \left( \frac{1}{a} \right)^2 \pmod p. $$ Esto contradice la hipótesis de $(q|p) = -1.$
Como resultado, el caso de (4) se mantiene, con evidentes $$pq a^2 - b^2 = \left( \frac{T+1}{2} \right) - \left( \frac{T-1}{2} \right) = 1, $$ así $$ b^2 - pq a^2 = -1. $$
$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$
Caution: With primes $p \neq q,$ with $p \equiv q \equiv 1 \pmod 4$ and Legendre $(p|q)=(q|p) = 1,$ there may not be a solution to $$ x^2 - pq y^2 = -1 $$ Por ejemplo, $205 = 5 \cdot 41$ $221 = 13 \cdot 17.$ a Continuación es el de Lagrange-método de Gauss para la continuación de la fracción. No decimales de precisión es necesaria, no hay memoria utilizada en el equipo.
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 205
0 form 1 28 -9 delta -3
1 form -9 26 4 delta 6
2 form 4 22 -21 delta -1
3 form -21 20 5 delta 4
4 form 5 20 -21 delta -1
5 form -21 22 4 delta 6
6 form 4 26 -9 delta -3
7 form -9 28 1 delta 28
8 form 1 28 -9
==========================================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 221
0 form 1 28 -25 delta -1
1 form -25 22 4 delta 6
2 form 4 26 -13 delta -2
3 form -13 26 4 delta 6
4 form 4 22 -25 delta -1
5 form -25 28 1 delta 28
6 form 1 28 -25
