La prueba de que $x^{(n+4)} \mod 10 = x^n \mod 10$

Question

Mientras que para resolver un desafío de programación en la que uno debe computar eficientemente el último dígito de <span class="math-container">$a^b$</span>, me di cuenta de que al parecer lo siguiente lleva a cabo (para <span class="math-container">$n > 0$</span>)

<span class="math-container">$x^{(n+4)} \mod 10 = x^n \mod 10$</span>

¿Cómo puede probar esto?

Answer 1

<span class="math-container">$x^4\equiv1\pmod{10}$</span> <span class="math-container">$x$</span> y <span class="math-container">$10$</span> coprimos, por Teorema de Euler, desde <span class="math-container">$\varphi (10)=4$</span>.

(La prueba <span class="math-container">$x$</span> no coprimo a <span class="math-container">$10$</span> puede encontrarse en algunas de las respuestas aquí).

Answer 2

Considere cómo la diferencia, es decir, $$x^{n + 4} - x^{n} = x^{n} \left( x^4 - 1 \right) = x^{n} \left( x^2 - 1 \right) \left( x^2 + 1 \right)$$ se comporta en todos los casos de $x \mod 10$ de $0$ a $9$, inclusive. Para $x$ ser $0$, el resultado es $0$. Para $x$ siendo un valor positivo, $x^n$ es un múltiplo de 2, mientras que cualquiera de las $x^2 + 1$ o $x^2 - 1$ es un múltiplo de 5, así que juntos son un múltiplo de $10$. Finalmente, para $x$ siendo un valor impar, considere los siguientes casos:

$1$: $x^2 - 1$ es $0$

$3$: $x^2 + 1$ es $10$, es decir, $0 \mod 10$

$5$: $x^n$ es un múltiplo de a$5$ e $x^2 - 1$ es un múltiplo de a$2$, así que juntos se muestra congruente a $0$

$7$: $x^2 + 1$ es $50$

$9$: $x^2 - 1$ es $80$

Esto muestra que el resultado es congruente a $0$ en todos los casos. Las otras respuestas son generalmente más corto y más simple, así que es mejor si usted es capaz de utilizar. Sin embargo, esto es bastante general para comprobar que, básicamente, cualquier congruencia de la operación donde nunca puede ser relativamente fácil de utilizar (por ejemplo, donde el mod divisor no es una variable o demasiado grande).

Answer 3

Esto es cierto debido a la periodicidad de los últimos dígitos de los números elevado a potencias. si usted echa un co $x=2,3,4\ldots n$ verá que después de cada $4$th poder que el último dígito es el mismo, $2^1 = 2$ e $2^5 = 32$ así que el último dígito es el mismo. $x^n \mod 10$ es esencialmente pidiendo el último dígito. Por lo tanto, $$x^{n+4} \mod 10 = x^n \mod 10$$ Algunos números tienen una periodicidad de $2$ cuando se levantó a las facultades que, por ejemplo, $9$ , pero la unidad dígito es el mismo que el primer poder de la primera.

Answer 4

Queremos mostrar que $x^{n+4}-x^n=x^n(x^4-1)$ es un múltiplo de a$10$.

Primero nos aviso que si $x^n$ es impar, a continuación, $x^4-1$ será aún y viceversa. En consecuencia, el producto siempre será incluso.

Si $x$ es divisible por $5$ a continuación, el producto es divisible por $10$ porque tenemos incluso un producto que es divisible por $5$.

Si $x$ no es divisible por $5$ entonces $x=5m+k$ para algunos $m$ e $k$ donde $k\in\{1,2,3,4\}$.

Ahora, $x^4-1=(5m)^4+4(5m)^3k+6(5m)^2k^2+4(5m)k^3+k^4-1$ y cada término es divisible por $5$ con la posible excepción de $k^4-1$.

Pero sólo hay cuatro valores de $k$ y si se quiere elevar a la cuarta potencia y restar $1$ obtener un múltiplo de $5$. Una vez más, esto nos da un número divisible por $5$ que es un múltiplo de a$10$.

Answer 5

Es el caso especial $\,p,q,k = 2,5,4\,$ a continuación.

Lema $\,p\neq q\,$ primos y $\, \color{#c00}{p\!-\!1,\,q\!-\!1\mid k}\ $ $\Rightarrow\, pq\mid\smash[t]{\overbrace{ x^n(x^k\!-\!1)}^{\Large a}}\,$ para todos los $\,x\,$ e $\,n>0$

Prueba de $\ $ $\,p,q\,$ son coprime lo $\,pq\mid a\iff p,q\mid a,\,$ por Euclides / factorización única.

En el caso de $\, p\mid x\,$ entonces $\,p\mid x\mid x^n\mid a\,$ por $\,n>0,\,$ por lo tanto $\,p\mid a\,$ por la transitividad de la divisibilidad,

$ $ más: $\,\ p\nmid x\,$ lo $\!\bmod p\!:\ x\not\equiv 0\,$ lo $\,x^k \equiv (\color{#0a0}{x^{p-1}})^{\smash[t]{\Large\color{#c00}{\frac{k}{p-1}}}}\!\!\equiv\color{#0a0} 1\,$ por $\rm\color{#0a0}{Fermat},\,$ lo $\,p\mid x^k\!-1\mid a$.

Así que en cada caso $\,p\mid a,\,$ lo $\,q\mid a\,$ por $\,p,q\,$ simetría (es decir, la misma prueba que funciona para $q). \ $ QED

---

Comentario $ $ Anterior es un caso especial de esta generalización de Euler-Fermat - que a menudo resulta útil.

Teorema $\ $ Supongamos que $\ m\in \mathbb N\ $ tiene la factorización en primos $\:m = p_1^{e_{\:1}}\cdots\:p_k^{e_k}\ $ y supongo que para todos los $\,i,\,$ $\ e\ge e_i\ $ e $\ \phi(p_i^{e_{\:i}})\mid f.\ $ Entonces $\ m\mid a^e\,(a^f-1)\ $ para todos los $\: a\in \mathbb Z.$

Prueba de $\ $ Aviso que si $\ p_i\mid a\ $ entonces $\:p_i^{e_{\:i}}\ |\ a^e\ $ por $\ e_i \le e.\: $ Else $\:a\:$ es coprime a $\: p_i\:$ por phi de Euler teorema, $\!\bmod q = p_i^{e_{\:i}}\!:\, \ a^{\phi(q)}\equiv 1 \Rightarrow\ a^f\equiv 1\, $ por $\: \phi(q)\mid f.\ $ Ya que todos los $\ p_i^{e_{\:i}}\ |\ a^e\ (a^f - 1)\ $ también lo hace su lcm = producto = $m$.

Ejemplos de $\ $ Usted puede encontrar muchos iluminando ejemplos de preguntas previas, por ejemplo, debajo de

$24\mid a^3(a^2-1)$

$40\mid a^3(a^4-1)$

$88\mid a^5(a^{20}-1)$

$6p\mid a\,b^p - b\,a^p$