Prueba por inducción, utilizando la suposición inductiva

Question

Demuestre que para todo número natural $n$ existen enteros $x,y$ tal que $$4x^2 + 9y^2\equiv 1\pmod{n} $$ El caso base es trivial, ya que 1 divide cualquier cosa. Supongamos que la afirmación se cumple para algún $k\in\mathbb{N}$ debe demostrar que la afirmación es válida para $k+1$ . Debemos encontrar algún $x', y'$ tal que $4x'^2 + 9y'^2\equiv 1\pmod{k+1}$ . Mi idea era utilizar la propiedad: $$\forall t\neq 0 (a\equiv b\pmod{n}\Longleftrightarrow ta\equiv tb\pmod{tn}) $$ Ya que para $k$ la afirmación se mantiene tenemos $$4x^2+9y^2\equiv 1\pmod{k}\Longleftrightarrow (k+1)(4x^2+9y^2)\equiv k+1\pmod{k(k+1)} $$ pero no sé cómo proceder (ni si esto lleva a alguna parte), cómo aplicar mejor el supuesto inductivo.

Para explicarlo mejor: Puedo hacer lo siguiente: $$(4x^2 + 9y^2)k + (4x^2 + 9y^2-1) \equiv k\pmod{k(k+1)}\Longrightarrow 4x^2 + 9y^2 + z\equiv 1\pmod{k+1} $$ el supuesto inductivo establece que $4x^2+9y^2-1$ es divisible por $k$ pero el resultado no es convincente.

Por supuesto, también se aceptan ideas alternativas para construir la prueba en cuestión.

Answer 1

(Esta no es una respuesta completa; sólo algunas observaciones iniciales).

Probablemente te costará inducir en $n$ así. Después de todo, sabiendo que $n \vert m$ (algún número entero $m$ ) no le dice casi nada sobre lo que $n+1$ divide.

Observe que $4x^2 + 9y^2 = ||2x+3y i||^2$ por lo que es necesario y suficiente para poder encontrar $x, y$ tal que $$||2x+3yi||^2 \equiv 1 \pmod{n}$$

Considere $2x+3iy$ y $2\alpha + 3i\beta$ . Si los multiplicamos, obtenemos $$4x\alpha -9y \beta + 6 (\alpha y+\beta x)i$$

Es de la forma $2r + 3is$ si y sólo si $y$ o $\beta$ es par; y en ese caso, $s$ también es par.

Por lo tanto, si podemos encontrar $2x+3iy, 2\alpha + 3 i \beta$ tal que $4x^2+9y^2 \equiv a \pmod{n}$ y $4\alpha^2+9\beta^2 \equiv b \pmod{n}$ con $y$ o $\beta$ incluso, entonces podemos encontrar $4r^2+9s^2 \equiv ab \pmod{n}$ con $s$ incluso.

Este es un tipo de propiedad de cierre que puede ser útil, aunque no sirve de nada en el caso de que $n$ es par, porque entonces el lado izquierdo sería siempre par y el derecho siempre impar, por lo que el "conjunto cerrado" es de hecho vacío.

Resuelve la cuestión en el caso de que $n$ es impar, sin embargo. De hecho, si $n$ es impar, entonces para algunos $c \in \mathbb{N}^{>0}$ tenemos $4^c \equiv 1 \pmod{n}$ . Dejar $x=1, y=0$ produce $4x^2+9y^2 = 4$ y podemos utilizar el resultado del cierre anterior $c$ veces. Aunque después de todo este trabajo, esto equivale simplemente a poner $$x = 2^{c-1}, y=0$$

Del mismo modo, si hay $d$ tal que $9^d \equiv 1 \pmod{n}$ , entonces podemos establecer $$x=0, y=3^{d-1}$$ Esto es así si y sólo si $n \not \equiv 0 \pmod{3}$ .

Por lo tanto, el único caso que queda es cuando $n$ es divisible por $6$ .

Dejar $x=y=1$ obtenemos $13$ , por lo que si hay $c$ tal que $13^c \equiv 1 \pmod{n}$ entonces también hemos terminado. Pero esto sucede si $n \not \equiv 0 \pmod{13}$ .

Por lo tanto, el único caso que queda es cuando $n$ es divisible por $6 \times 13 = 78$ .

Answer 2

Un razonamiento erróneo antes. Intentémoslo de nuevo:
$n=1$ no es interesante, arreglar $n>1$
$2\mid n\land 3\mid n\Longleftrightarrow 6\mid n$ . Por lo tanto, si $\neg (6\mid n)$ entonces $2$ o $3$ son invertibles en $\Bbb{Z}_n$ .
Si $2$ es invertible, entonces $y=0$ y $2x\equiv 1\pmod{n}$ para algunos $x\in\Bbb{Z}_n$ . (Análogo para si $3$ es invertible).

Si ambos $2$ y $3$ son divisores de cero, entonces dejemos que $n=qr$ donde la factorización de los primos se distribuye entre $q$ y $r$ tal que $(q,r)=1$ .
Por el teorema del resto chino tenemos $x\equiv x_1\pmod{q}, x\equiv x_2\pmod{q}$ y $y\equiv y_1\pmod{r}, y\equiv y_2\pmod{r}$ tal que $$ 4x^2 + 9y^2\equiv 4x_1^2 + 9y_1^2\equiv 1\pmod{q}\\4x^2 + 9y^2\equiv 4x_2^2 + 9y_2^2\equiv 1\pmod{r} $$ y entonces también por el lema de Euclides, porque $(q,r)=1$ tenemos $4x^2 + 9y^2\equiv 1\pmod{qr=n}$ .