¿A qué divisores$a$ de$n$ se puede generalizar el teorema de Euler multiplicado por$a$, es decir, cuándo es$a^{\phi(n)+1}\equiv a \pmod n$?

Question

El Teorema de Euler $$a^{\phi(n)}\equiv 1\pmod n,$$ que sólo es válido el fib $a$ $n$ son coprime, puede ser "generalizado" un poco a $$a^{\phi(n)+1}\equiv a\pmod n, (*)$$ donde algunos de cero divisores de $n$ son también admisibles para $a$, por ejemplo, $$2^4\equiv 2\pmod{10},$$ aunque lo que me gustaría llamar la cero-raíces^$\dagger$ $n$ fallar: $$6^4\equiv 0\pmod{12}$$

Pero aparte de estos, no la generalización $(*)$ mantener por todos los no-cero-raíces de $n$?

---

$\dagger$ $a$ es un cero de la raíz de $n$ $\Leftrightarrow$ $\exists k:a^k\equiv0\pmod n$ - este es el caso de la fib todos los factores primos de a $a$ $n$ son los mismos

Answer 1

La congruencia

$$a^{\varphi(n)+1} \equiv a \pmod{n},$$

o, para el caso,

$$a^{\lambda(n)+1} \equiv a \pmod{n},$$

vale si y sólo si para todos los números primos $p$ dividiendo $n$ tenemos $p \nmid a$ o $v_p(a) \geqslant v_p(n)$ (donde $v_p(k)$ es la multiplicidad de $p$ en el primer factorización de $k$, lo $p^{v_p(k)} \mid k$, pero $p^{v_p(k)+1} \nmid k$).

A ver que, considere la posibilidad de un primer $p$ dividiendo $n$, y deje $k = v_p(n)$. A continuación, $\varphi(p^k) = (p-1)p^{k-1}$ divide $\lambda(n)$ y, a fortiori,$\varphi(n)$. Ahora vamos a $a$ arbitrarias. Si $p \nmid a$,$a^{\lambda(n)} \equiv a^{\varphi(n)} \equiv 1 \pmod{p^k}$, e $a^{\lambda(n)+1} \equiv a^{\varphi(n)+1} \equiv a \pmod{p^k}$. Y si $p\mid a$, luego

$$v_p(a^{\lambda(n)}) \stackrel{\varphi(p^k)\mid\lambda(n)}\geqslant v_p(a^{\varphi(p^k)}) \stackrel{p\mid a}\geqslant \varphi(p^k) = p^{k-1}(p-1) \geqslant p^{k-1} \geqslant k,$$

por lo $a^{\lambda(n)} \equiv 0 \pmod{p^k}$, y a fortiori $a^{\lambda(n)+1} \equiv 0 \pmod{p^k}$$a^{\varphi(n)+1}\equiv 0 \pmod{p^k}$. Así que si $p \mid a$, $a^{\lambda(n)+1} \equiv a \pmod{p^k} \iff a \equiv 0 \pmod{p^k}$ (y lo mismo para el $\varphi(n)$).

Desde $a^e \equiv a \pmod{n}$ si y sólo si $a^e \equiv a \pmod{p^{v_p(n)}}$ para todos los números primos dividiendo $n$ (última condición no es necesaria, si $p \nmid n$, $a^e \equiv a \pmod{p^0}$ independientemente), el resultado de la siguiente manera.

Answer 2

Se mantiene al menos para squarefree$n$ (lo que explica su excepción de mod 12). Esto ya es válido para la función Carmichael$\lambda(n)$, consulte http://en.wikipedia.org/wiki/Carmichael_function#Exponential_cycle_length

Answer 3

De otra manera:

$$\begin{align} a^{\phi(n)+1} &\equiv a \pmod n \quad(*) \\\Leftrightarrow a^{\phi(n)} &\equiv 1 \pmod{n/\gcd(n,a)} \end{align}$$

Si $a$ $n$ son coprime (es decir,$\gcd(n,a)=1$), esto es simplemente el Teorema de Euler y, por tanto, verdadera. De lo contrario, ya que $$ \phi(a\cdot b) = \phi(a)\phi(b)\frac{\gcd(a,b)}{\phi(\gcd(a,b))},$$

deje $g:=\gcd(n,a)$ $m:=n/g$ obtener

$$\begin{align} \phi(n) &= \phi(m\cdot g) \\ &= \phi(m)\cdot\underbrace{\frac{\phi(g)\gcd(m,g)}{\phi(\gcd(m,g))}}_{=:k} \end{align}$$

y por lo tanto $$(*)\Leftrightarrow \left(a^k\right)^{\phi(m)} \equiv 1\pmod m$$ que es de nuevo el teorema de Euler que tiene iff $a^k$ $m$ son coprime donde$k=\phi(n)/\phi(m)$$m=n/\gcd(n,a)$.

Voy a tratar de correlacionar esto a Daniel Fischer requisitos más tarde...