Sin utilizar el pequeño Teorema de Fermat, ¿cómo puedo rápidamente resuelve $2014 ^{2015} \pmod {11}$?
Respuestas
¿Demasiados anuncios?
David HAust
Puntos
2696
Este puede ser calculado en un par de segundos de aritmética mental de la siguiente manera. Primero hemos echado $11$'s para calcular los $2014\pmod{11}$ como la alternancia de suma de dígitos:
${\rm mod}\ 11\!:\ \color{#0a0}{10\equiv -1}\,\Rightarrow\, \color{#c00}{2014}\equiv 2(\color{#0a0}{10})^3\!+\!\color{#0a0}{10}\!+\!4\equiv 2(\color{#0a0}{-1})^3\!\color{#0a0}{-\!1}\!+\!4\equiv\color{#c00} 1\ $ [cast $11$'s - ver más abajo]
Por lo tanto, $\ \color{#c00}{2014}^n\equiv \color{#c00}1^n\equiv 1\ $ por la Congruencia de Alimentación de la Regla.
Comentario $\ $ La primera línea es un caso especial de echar fuera onces, el análogo de echar fuera nueves, es decir, $\, \color{#0a0}{10\equiv -1}\,\Rightarrow\,f(\color{#0a0}{10})\equiv f(\color{#0a0}{-1}) = $ la alternancia de suma de dígitos, donde $\,f(x)\,$ es la base decimal polinomio, por ejemplo, por encima de $\, f(x) = 2x^3+x+4,\ f(10) = 2014.\,$ Ver aquí para más discusión.
El hecho fundamental de la aritmética modular es $$ ab \bmod n = (a\bmod n)(b\bmod n)\bmod n $ $ (y el hecho análogo para la adición). Aplicar esta regla a veces 2014 $$ \underbrace{2014\cdot 2014\cdot 2014 \cdots 2014}_{2015\text{ factors}} $ $ (y luego 2014 más veces en sentido contrario para deshacerse del intermedio '$\bmod 11$' s) y te $$ 2014^{2015} \bmod 11 = (2014 \bmod 11)^{2015} \bmod 11 = 1^{2015} \bmod 11 = 1 $ $
Joffan
Puntos
7855
Me gusta Bill Dubuque la respuesta, pero definitivamente yo no uso su enfoque para encontrar $2014 \bmod 11$, sólo utiliza un descartando la versión de la división larga:
$20 \bmod 11 = \color{red}{9} \\ \a \color{red}{9}1 \bmod 11 = \color{verde}{3} \\ \a \color{verde}{3}4 \bmod 11 = 1$
Y luego, por supuesto,$2014^{2015} \equiv 1^{2015} \equiv 1 \bmod 11$.
Si $2014$ había sido un número más alto, probablemente habría utilizado la alternancia de los dígitos de la regla de divisibilidad por $11$, $(0+4)-(2+1) = 1$, porque me habría parado a pensar antes de iniciar el proceso de división :-)
