¿Cuál es la mejor manera de computar los últimos tres dígitos de $23^{320}$? Sé que es una forma a partir de $23^2$ y la búsqueda de los tres últimos dígitos, luego cuadratura (cálculo $23^4 \pmod {1000}$) y conseguir los tres últimos dígitos y así sucesivamente hasta llegar a $23^{320}$. ¿Hay cualquier método más fácil?
Respuestas
¿Demasiados anuncios?
Leon Katsnelson
Puntos
274
$201$ (Usando "23 ** 320" Python3.)
O un giro ligeramente diferente que no implique totients (directamente, por lo menos):
Desde $320 = 5 \cdot 2^6$, tenemos
$23^5 = 343 \mod 1000$
$343^2 = 649 \mod 1000$
$649^2 = 201 \mod 1000$
Ahora Observe que $(200n+1)^2 = 200(2n)+1 \mod 1000$, por lo tanto, $(200n+1)^{2^4} = 200(16)+1 = 201\mod 1000$.
user64684
Puntos
1
Algunas ideas:
Desde $10^3=5^3\times 2^3$, podemos tratar de trabajar de forma independiente. Y utilizar el teorema del resto Chino
El totient función de $125$ es fácilmente visto a $100$, por lo que según el teorema de Euler tiene que $23^{100} \equiv 1 \pmod{125}$, y por lo tanto $23^{300}\equiv1 \pmod{125}$. Adicional cálculo muestra que $23^{320}\equiv 76 \pmod{125}$. Set $a_1=76$.
El otro caso es tal vez más fácil, ya que $\phi(8)=4$,$23^4 \equiv 1 \pmod{8}$. Desde $4$ divide $320$, entonces usted tiene que $23^{320}\equiv 1 \pmod{8}$. Set $a_2=1$.
El último paso sería el uso de la Chine Teorema del Resto para recuperar toda la respuesta. Tenemos que resolver dos congruencias para aplicar este teorema para obtener los números de $b_1$$b_2$. $$ 8x \equiv 1 \pmod{125}$$ $$ 125x \equiv 1 \pmod{8}$$ Las soluciones se $47$ en el primer caso y $5$ en el segundo caso. A partir de aquí podemos obtener la siguiente expresión (es sólo la receta de el teorema del resto Chino) $$x\equiv 8*a_1*b_1 +125*a_2*b_2 = 8*76*47+125*5= 29201 \equiv 201 \pmod{1000}$$
Esto no parece lo suficientemente simple, aunque. Pero es otro enfoque. Esta respuesta es correcta. He verificado.
Farkhod Gaziev
Puntos
6
Como $1000=2^3\cdot5^3$ donde $(2,5)=1$
Ahora, tenemos $23^2\equiv1\pmod{ 2^3}\implies 23^{320}=(23^2)^{160}\equiv1^{160}\pmod{ 2^3}$ $\implies 23^2\equiv1\pmod8\ \ \ \ (1)$
y como $23=25-2$ $\implies 23^{320}=(25-2)^{320}=(2-25)^{320}=2^{320}-320\cdot2\cdot25+25^2(\cdots)\equiv2^{320}\pmod{125}$
Como $(2,125)=1$ $\phi(125)=100, 2^{100}\equiv1\pmod{ 125}\implies 2^{320}\equiv2^{20}\pmod{125}$
De nuevo, $2^{10}=1024\equiv24\pmod{125}\implies 2^{20}\equiv24^2\pmod{125}\equiv76$
$\implies23^{320}\equiv2^{320}\equiv2^{20}\equiv76\pmod{125}\ \ \ \ (2)$
Método de$1:$ Aplicar CRT en $(1),(2)$
Método de $2:$
De $(1)$ $(2)$ tenemos $x=8a+1$ $x=125b+76$ respectivamente, donde $a,b$ son enteros
$\implies 8a+1=125b+76\iff 8a=125b+75\iff 8a=25(5b+3)\ \ \ \ (3)$
$\displaystyle\iff\frac{8a}{25}=5b+3$ que es un entero
$\displaystyle\implies25$ divide $8a\implies 25|a$ $(25,8)=1$
$a=25c$(por ejemplo) donde $c$ es un número entero
$(3)$ reduce a $8c=5b+3\iff 8(c-1)=5(b-1)\iff \frac{5(b-1)}8=c-1$ que es un entero
Como $(5,8)=1,8$ debe dividir $b-1\implies b-1=8d$ para algunos entero $d$
$\implies x=125b+76=125(8d+1)+76\equiv201\pmod{1000}$
El período de $1000$ en cualquier base es el $\operatorname{lcm}(\varphi(125)\varphi(8))$ donde $\varphi()$ es el de Euler totient función, y $125$ $8$ son los principales poderes que se multiplican a $1000$. Esto es, a continuación,$\varphi(125)=100$, e $\varphi(8)=4$, pero en realidad, las potencias de 2 contiene una ortogonal del elemento, por lo que es en realidad 2.
Esto significa que los tres últimos dígitos decimales de cualquier $x^n$ es periódica en más de 100 lugares.
Por eso, $320 = 20 \pmod{100}$. Por lo $23^{320}$ termina en el mismo tres dígitos como $23^{20}$.
Vemos que $23=-1 \pmod 8$, lo $23^{2n}=1 \pmod 8$. Para $5$, tenemos que acercarnos con cuidado. $23^2 = 529$, $529^2 = 841 \pmod{1000}$ , de ser el cuarto poder.
Se calcula ahora la quinta potencia de este, no directamente, pero por la regla de
$$(x+1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x^1 + 1$$
Al $x=840$, entonces todo lo $x^2$ y el mayor se reduce a $0 \pmod {1000}$. Todo lo que necesitamos para encontrar aquí es $5x+1 = 201 \pmod{1000}$.
El proceso es mucho más fácil para encontrar $a^n \pmod{b^2}$, porque si uno encuentra algo de $a^x$ en la forma$cb+1$,$a^{xy}= (cy)b+1$. Por ejemplo, para encontrar los últimos cuatro dígitos de $7^{23}$, ayuda a saber que $7^4=24\;01$, y, por tanto,$7^{4x}=24x\;01$. Aquí, se puede usar $x=5$$5\times24 = 1\;20$, para obtener el $7^{20} = 20\;01$ es directa para multiplicar este por $343$ conseguir $63\;43$ como los últimos cuatro dígitos de ese número.
Por ejemplo, los últimos cuatro dígitos de $23^{320}$, va como esta.
$23 ^ 2 = 529$, $529^2 = 500^2 + 2\cdot 500 \cdot 29 + 29^2 \pmod{10000}$, Esto se reduce a $0 + 9000 + 841 = 9841 \pmod {10000}$. para la cuarta potencia.
Ahora utilizamos $(x+1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1$,$x=9840$. La mayoría de estos son múltiplos de $10,000$, por lo que sólo necesitamos considerar $10x^2 + 5x + 1$
El primer término da $4^2 = (1)6$ da $6000$. El segundo término da $5\times 9840$, da $4\;9200$. El tercer término es $1$, el total es de $52\;01$, el 20 de alimentación.
El que ahora se encuentra desde $52\times 16$ da $32$, y para los últimos cuatro dígitos es $3201$. Nada más complejo que la aritmética mental, de verdad.
