Para
$(x2^9)^2=2^q-1+y^2q^2$, donde $q$ es primo,
¿es posible mostrar que existe sólo una solución única para el par $\{x,y\}$?
Respuesta
¿Demasiados anuncios?
$\newcommand\Z{\mathbf{Z}}$
Si $2^{q} - 1 \equiv 0 \mod p$, $2$ orden $q$ en el grupo $\mathbf{F}^{\times}_p$. Desde el último grupo tiene orden de $p -1$, se sigue que cualquier divisor primo de $2^{q} - 1$$1 \mod q$. Por otra parte, $2$ va a ser un residuo cuadrático módulo $p$, por lo que cualquier factor también será congruente a $\pm 1$ modulo $8$.
Con esto en mente, considere el siguiente lema.
Lema: Considere el $128$ ordenado de elementos (no necesariamente distintos) del grupo abelian $\Z/128 \Z$. A continuación, algunos no trivial subconjunto de estos elementos de sumas a cero.
Prueba: el Fin de la lista como $s_1, \ldots, s_{128}$. Considerar los elementos: $$s_1, \ s_1 + s_2, \ s_1 + s_2 + s_3, \ \ldots $$ Hay $128$ de tales sumas. Si son todas diferentes, una debe ser la identidad. Si los dos son el mismo, la diferencia es también un no-trivial, suma que es igual a cero.
No se puede hacer mejor (a priori) de 128, porque uno puede tener $s_i = 1$ modulo $128$ todos los $i$.
Podemos deducir:
Corolario: Para cualquier $129$ primos $\equiv \pm 1 \mod 8$, no trivial subconjunto de ellos tiene un producto que es $\pm 1 \mod 2^{10}$.
Prueba:: Aplicar el lema anterior para cualquier subconjunto de tamaño $128$ y para el grupo de elementos de la $\pm p_i \equiv 1 \mod 8$. Tenga en cuenta que el grupo $(1 + 8\Z)/(1 + 2^{10} \Z)$ es cíclico de orden $128$.
Corolario: Si $2^{q} - 1$ tiene al menos $129$ primer divisores, entonces hay al menos dos soluciones para
$$2^{q} - 1 = (2^9 x)^2 - y^2 q^2 = (2^9 x + y q)(2^9 x - y q).$$
Prueba: queremos escribir $2^q - 1 = AB$ donde $A$ $B$ tiene la forma requerida, es decir, podemos resolver para la integral de la $x$ $y$ en las ecuaciones:
$$A = 2^9 x + y q,$$ $$B = 2^9 x - y q.$$
Esto equivale a pedir que $A \equiv B \equiv 1 \mod q$,$A$$\equiv \pm 1 \mod 2^{10}$. La solución trivial es$A = 1$$B = 2^{q} - 1$; queremos construir otra solución. Dado que todos los factores primos de a$2^q - 1$$1 \mod q$, la primera condición es automática. Para el segundo, si suponemos que la $2^q - 1$ tiene al menos $129$ factores primos, entonces, por el Lema, se desarrolla un divisor que es $\pm 1 \mod 2^{10}$. Esto le da a la solución deseada.
Sin duda uno espera que los números de $2^{q} - 1$ puede tener un número arbitrariamente grande de factores primos, por lo que uno espera --- por la obvia la generalización del lema anterior --- que no puede existir de manera arbitraria tantas soluciones como $q$ varía. Además, uno puede esperar encontrar un pequeño $q$ con muchos factores, tales que el producto es $\pm 1 \mod 2^{10}$ --- enlazado en el Lexema es fuerte en el peor de los casos, pero en la práctica se espera que muchos menos de $129$ prepara debería ser suficiente. El problema es que $2^q - 1$ es difícil, el factor de $q$ se hace grande. En lugar de eso, uno puede buscar para $q$ que $2^q - 1$ tiene un pequeño factor, digamos de menos de 500.000. Para esos pequeños factores, se tiene (aproximadamente) de una en $256$ de probabilidad de ser $\pm 1 \mod 1024$, dado que son $\pm 1$ modulo $8$. Desde calcular el MCD de a $2^q - 1$ y (dicen) de 500.000! es relativamente barato, no es realista para la búsqueda a través de una amplia gama de $q$. Uno encuentra que:
$$2^{3527} - 1 \equiv 0 \mod p = 63487,$$
y, con $q = 3527$, tenemos
$$p \equiv 1 \mod q, \quad p \equiv -1 \mod 1024.$$
Por lo tanto, si
$$A = p, \quad B = \frac{2^{q} - 1}{p}, \qquad x = \frac{B+A}{2^{10}}, \quad y = \frac{B-A}{2q},$$
entonces
$$(2^9 x)^2 = 2^{q} - 1 + q^2 y^2$$
es una segunda solución (más allá del caso trivial al$A = 1$$B = 2^{q} - 1$). Explícitamente, $x$ es igual a
$$\begin{aligned} & \ 83139985554814564201142265398423940983734084680519373351274507224446764599607 \\ & \ 49451696564934671744653119863727621498244035702529608058476405955664605629948\\ & \ 62838307137784283737806179254649900079974691279735262514980072403875850975080\\ & \ 61957046474191593038928867902487454538277902526798081847840485073702295261112\\ & \ 33113621488853227725892116562645102916296506631441882237602645539576240063083\\ & \ 16542844209980653631941354248232439226396413730532924481168362238086941828118\\ & \ 38308509653785749056465841156627127934624282576692681779074414679440900436490\\ & \ 51748113171730486696573215817843552171786257357981110777970815770070081216602\\ & \ 65313780022194173593463676305763851504432476029971231801801391928524170852121\\ & \ 01902453812880831869001524277687896922188634322634430157407549044529132580919\\ & \ 11569976254856032521966500715204341110750005850922868567006271584961070720322\\ & \ 41598144814720814044682551670392948705627868423019659857466668911286790507132\\ & \ 78061681936258561522605907127622832906278247368600982784494146323005476392476\\ & \ 84876567107301371945802093257368889076102458785927292, \end{aligned}$$
y $y$ es igual a $$\begin{aligned} & \ 12069087781135542067191618906717623414707074385150529956295023447382121767791\\ & \ 05108950564572314129079216719656518913269335491833047724961701119733563391702\\ & \ 21086819748949689048414166084031967349290343616451503943200963161549315480363\\ & \ 27678482504901076165560414053323951438502491095469412505271995564994492535778\\ & \ 14390182648792983440787287689275387778039073262063579162362504824571316958406\\ & \ 17541802164873857289354684824240149952910395188554822039795350571562379987523\\ & \ 84806905852775249083331587942215222427708430019638971667390445227069390706969\\ & \ 98722720142876668326806205415008760621478470021912766860879233817486782416473\\ & \ 08148754003788890524483527720031497581590424646256101696207063415765346038073\\ & \ 70619239113182587444550263802148058753660499226875199387749550640997707933493\\ & \ 22008457000988457230293974586386340416417352706456622825717950397363217524469\\ & \ 82619294058728964216296418047984459806430810499740874921185975186441405369904\\ & \ 16321968004356218741019059951614088587472203757506011677250071708925093255726\\ & \ 72145393353824298961227862701381590929108153926394871.\end{aligned}$$
También hay una segunda solución al $q = 6947$. En este caso, $p= 180623$ $p' = 333457$ son divisores de $2^q - 1$, y
$$A = p p' = 60230003711 \equiv -1 \mod 1024.$$
