Resolución de un sistema de congruencias lineales

Question

Encontrar todas las soluciones enteras positivas de \begin{align*}x &\equiv -1 \pmod{n} \\ x&\equiv 1 \pmod{n-1}. \end{align*}

Reescribí el sistema como $x = nk_1-1$ y $x = (n-1)k_2+1$ . Así, tenemos $nk_1-1 = (n-1)k_2+1$ y así $n(k_1-k_2) = 2-k_2 \implies n = \frac{2-k_2}{k_1-k_2}$ . ¿Cómo lo resuelvo desde aquí?

Answer 1

Como $n,n-1$ son relativamente primos el Teorema del Resto Chino garantiza una solución única $\pmod {n(n-1)}$ . De hecho lo hemos hecho, $$x\equiv 2n-1 \pmod {n(n-1)}$$

Para ver esto, resuelve la primera congruencia para obtener $x=-1+mn$ . Sustituyendo esto en la segunda se obtiene $$-1+mn\equiv 1 \pmod {n-1}\implies mn\equiv 2 \pmod {n-1}\implies m\equiv 2 \pmod {n-1}$$

Y hemos terminado.

Answer 2

En primer lugar, hay que tener en cuenta que $x_0=2n-1$ es una solución.

Ahora bien, si $x$ es una solución, entonces $x\equiv x_0\pmod n$ y $x\equiv x_0\pmod {n-1}$ . Así, $n|x-x_0$ y $(n-1)|x-x_0$ . Además, como $\gcd(n,n-1)=1$ tenemos $n(n-1)|x-x_0$ .

Además, para todos los enteros no negativos $k$ podemos comprobar que $x=2n-1+kn(n-1)$ es una solución.

Así, todas las soluciones son $x=2n-1+kn(n-1)$ , donde $k\in \mathbb{Z}_{\geqslant 0}$ .

Answer 3

Las dos congruencias son equivalentes a $$\begin{cases}x=nu-1\\x=(n-1)v+1\end{cases}$$ It follows the diophantine equation $$nu-(n-1)v=2$$ which admits the particular solution $(u,v)=(2,2)$ hence the general solution is $$\begin{cases}u=(n-1)t+2\\v=nt+2\end{cases}$$ Finalmente se tiene $$x=n((n-1)t+2)-1$$ donde $t$ es un número entero arbitrario.

( La primera congruencia se verifica claramente; la segunda da $x\equiv 2n-1\equiv 1\pmod{n-1}$ por $2n-1=2(n-1)+1$ )