Demostrar que $x^x\equiv k \mod n$ tiene soluciones del número entero para cada número entero $k$iff $gcd(n,\phi(n))=1$.

Question

Demostrar que <span class="math-container">$x^x\equiv k \mod n$</span> tiene soluciones entero para cada número entero de iff <span class="math-container">$k$</span> <span class="math-container">$gcd(n,\phi(n))=1$</span>.

Sé que si <span class="math-container">$x^x\equiv k \mod n$</span> tiene soluciones del número entero entonces la solución menos positiva es menor que <span class="math-container">$n\phi(n)$</span>.

Answer 1

$x^x ≡ k \mod n$

Un caso particular de la condición de $gcd (n, \phi(n))=1$ es cuando n es primo, porque en este caso $\phi(n)=(n-1)$. Supongamos $x=n-1$, entonces tenemos:

$x^{n-1}≡1 \mod n$ ⇒ $\frac{x^n}{x}≡1 \mod n$.

Multiplicando ambos lados por x obtenemos:

$x^n ≡x \mod n$ ⇒ $x^{x+1} ≡ x \mod n$ ⇒ $x^x ≡ \frac{x}{x} \mod n$ ⇒ $x^x ≡ 1 \mod n≡(1-n) \mod n$

Podemos dejar que $(1-n)=k$ y a la conclusión de que $x^x≡ k \mod n$

En este caso particular, el valor de k es $1-n$, lo que para cualquier $\{k=1-n, x=n-1; n.. prime\}$ se puede escribir una relación como $x^x≡k\mod n$

Este argumento se puede aplicar para cuando $gcd (n. \phi(n))=1$; en este caso n es reemplazado por $\phi(n)$ , y dejamos $x=\phi(n)-1$ y tenemos:

$x^{\phi(n)} ≡x \mod n$ ⇒ $x^{x+1} ≡x \mod n$ ⇒ $x^x ≡1\mod n≡(1-n)\mod n$