¿Es el producto de dos números enteros consecutivos $1$ $\pmod n$?

Question

Hay una prueba sencilla para $n$ a determinar si existe un entero $x$ tal que $x$($x+1$) $=$ $1$ $\pmod n$. Por ejemplo, $n$ $=$ $3$ y $n$ $=$ $7$, no hay enteros $x$ tal que $x$($x+1$) $=$ $1$ $\pmod n$. Pero para $n$ $=$ $5$ y $n$ $=$ $11$, existen enteros $x$ tal que $x$($x+1$) $=$ $1$ $\pmod n$. Allí,a saber, de

$x = 2$, $2*3$ $=$ $1$ $\pmod 5$

$x = 7$, $7*8$ $=$ $1$ $\pmod {11}$

Es confuso para averiguar qué números enteros $n$ tienen esta propiedad. Tal vez hay un especial (matemática) de la propiedad de estos números. Se agradece la ayuda. Gracias.

Answer 1

Primero debemos reescribir la congruencia: $$4x(x+1)=4\pmod{4n}\quad\Leftrightarrow\quad (2x+1)^2=5\pmod{4n}\ .$$ Ahora escribo $y=2x+1$ y considerar los diversos casos.

• Si $n$ es incluso entonces lo anterior implica $y^2=5\pmod8$, que no tiene solución.

• Si $5^2\mid n$ entonces tenemos $$\eqalign{y^2=5\pmod{25}\quad &\Rightarrow\quad 5\mid y^2\cr &\Rightarrow\quad 25\mid y^2\cr &\Rightarrow\quad 25\mid 5\cr}$$ y de nuevo no hay ninguna solución.

• Así que para que las soluciones existen, $n$ es un producto de $5$ (posiblemente) y el primer potencias $p^\alpha$ donde $p$ no $2$ o $5$. Hay una solución iff $$y^2=5\pmod{p^\alpha}$$ tiene una solución para cada una de dichas primer poder, el cual puede ser demostrado ser equivalente a $$y^2=5\pmod p$$ tener una solución para cada $p\mid n$ (con la excepción de $p=2,5$). Utilizando el símbolo de Legendre se puede demostrar que esto se reduce a la siguiente.

La congruencia $x(x+1)=1\pmod n$ tiene una solución si y sólo si $n$ es un producto de números primos en el que $5$ se produce sólo una vez (o no), y todos los demás prime es congruente a $1$ o $4$ modulo $5$.

---

Aquí hay una tabla con algunos valores bajos de $n$. He hecho una lista de "ok" si la congruencia tiene una solución, de lo contrario me han dado un "mal" el primer factor de $n$. $$\def\ok{{\rm aceptar}} \matriz{3&5&7&9&11&13&15&17&19&21&23&25&27&29&31&\cdots&55\cr 3&\ok&7&3&\ok&13&3&17&\ok&3&23&5&3&\aceptar&\ok&\cdots&\aceptar\cr}$$ Tenga en cuenta que $p=5$ es "malo" para $n=25$ debido a que se produce dos veces, pero es en "aceptar" para $n=5$$n=55$, ya que sólo ocurre una vez.

Answer 2

Usted está pidiendo cuando el polinomio $x^2+x-1$ tiene una raíz mod $n$. Desde $x(x+1)$ es siempre igual, claramente $n$ debe ser impar para tal $x$ a existir. En ese caso $2$ es invertible mod $n$, y así, por la fórmula cuadrática $x^2+x-1$ tiene una raíz mod $n$ si el discriminante $5$ tiene una raíz cuadrada mod $n$.

Así que usted está preguntando qué números enteros impares $n$ $5$ una plaza de mod $n$. Por el teorema del resto Chino, $5$ es un cuadrado mod $n$ fib es un cuadrado mod $p^k$ para cada potencia principal $p^k$ que aparecen en la descomposición en factores primos de a $n$. Para $p\neq 2,5$, $n$ es una plaza de mod $p^k$ fib $5$ es un cuadrado mod $p$ (por ejemplo, por Hensel del lema). Por la reciprocidad cuadrática, $5$ es un cuadrado mod $p$ por extraño $p$ fib $p$ es un cuadrado mod $5$, es decir, iff $p$ $0,1,$ o $4$ mod $5$. El caso de $p=2$ no importa ya que $n$ debe ser impar, y $5$ es un cuadrado mod $5^k$ fib $k\leq 1$.

Poniendo todo junto, nos encontramos con que $x^2+x-1$ tiene una raíz mod $n$ fib cada factor primo de $n$ $0,1,$ o $4$ mod $5$ $25$ no divide $n$.

Answer 3

Como laboratorio de bhattacharjee escribió (trabajo $\bmod n$), Si $m(m+1) = 1$ entonces $4m^2+4m=4$ o $5 =4m^2+4m+1 =(2m+1)^2 $.

Por lo tanto, si $5$ es una ecuación cuadrática de residuos de mod $n$, hay (al menos) una de las soluciones.

De acuerdo a https://en.wikipedia.org/wiki/Quadratic_residue, para un primer $p$, $5$ es un residuo cuadrático mod $p$ si y sólo si $p \equiv 1, 4 (\bmod 5) $.

Para composite $n$, ver https://en.wikipedia.org/wiki/Jacobi_symbol.

La mesa titulado "Tabla de valores" muestra que $k$ han $5$ como residuos cuadráticos.

Answer 4

Claramente, la condición de $x(x+1)\equiv1\pmod{n}$ no puede mantener si $n$ es incluso (porque $x(x+1)$ es en sí mismo incluso).

Ahora supongamos $n$ es impar.

El OP puede ser reformulada de la siguiente manera : encontrar los números enteros $n\ge2$ tales que la ecuación de $x^2+x-\bar{1}=\bar{0}$ tiene al menos una solución en el ring $\mathbb{Z}/n\mathbb{Z}$.

(Denotamos por a $\bar a$ la congruencia de la clase de $a$ mod. $n$)

Tenga en cuenta que $\bar2$ es invertible en que el anillo (debido a $gcd(2,n)=1$).

El discriminante de esta ecuación cuadrática es $\Delta=\bar5$ y la pregunta es : encuentre los enteros $n\ge2$ tal que $\bar5$ es un cuadrado.

La respuesta es dada por el símbolo de Legendre. Por ejemplo, si $n$ es una extraña primer y $n\neq5$, entonces :

$$\left(\dfrac{5}{n}\right)=(-1)^{\left\lfloor\frac{n+2}5\right\rfloor}$$

En el caso general, podemos utilizar el de la reciprocidad cuadrática de la ley para calcular $\left(\dfrac{5}{n}\right)$ y decidir que es $1* o no