Euler Teoremini kullanarak son basamağı bulma

Question

Bu soruna biraz sıkışıp kaldım, umarım yardımcı olabilirsiniz. Euler teoremini kullanarak bir güç kulesinin son rakamını bulmak istiyorum:\begin{align} q &= 10, \\ \varphi(q) &= 4, \\ \varphi(\varphi(q)) &= 2, \\\varphi(\varphi(\varphi(q))) &= 1. \end{align} \begin{align} 625703 ^{\displaystyle 43898 ^{\displaystyle 614961 ^{\displaystyle 448629}}} &\equiv (625703 \bmod 10)^{\displaystyle (43898 \bmod \varphi(10))^{\displaystyle (614961 \bmod \varphi(\varphi(10)))^{\displaystyle (448629 \bmod \varphi(\varphi(\varphi(10))))}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1^{\displaystyle 0}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1}} \mod 10 \\ &\equiv 3^{\displaystyle 2} \mod 10 \\ &\equiv 9 \mod 10 \end{align}Bu yaklaşıma göre, güç kulesinin son rakamı 9 olmalıdır. Ancak, doğru çözüm 1'dir ( buraya bakın ) - neyi yanlış yapıyorum?

Bu yaklaşım aşağıdaki iki cevaba dayanmaktadır

bilgi işlem ${{27^{27}}^{27}}^{27}\pmod {10}$

İç içe geçmiş bir üstelin son rakamını bulmak için genel bir algoritma / teknik nedir?

Answer 1

Neyi yanlış yapıyorum?

Euler'in teoremi , baz ve modülün nispeten asal olduğunu varsayar.

Senin sorununuzda durum bu değil: $43898$ göreceli olarak asal değildir $4$.

Aslında, $43898^n\equiv0\pmod4$ için $n\ge2$.

Şimdi çözebilir misin?

Answer 2

İpucu: $ $ dikkat edin: $\ n\ge 2\,\Rightarrow\, \color{#c00}{(2k)^n\bmod 4 \,\equiv\, 0}\ $ böylece $ $ modüler sipariş azaltma

$\!\!\bmod 10\!:\ 3^{\large \color{#c00}4}\equiv 1 \Rightarrow\ 3^{\large \color{}{(2k)^{\large n}}}\!\!\!\equiv 3^{\large \color{#c00}{(2k)^{\large n}\bmod 4}}\!\equiv 3^{\:\!\large\color{#c00} 0}\equiv 1,\ $ ve

$\!\!\bmod 10\!:\ 625703\equiv 3\Rightarrow 625703^N\!\equiv 3^N\,$tarafından Uyumu Güç Kuralı .

Açıklama $ $ Gözetim: Euler'in teoremi $\,a^{\phi(m)}\equiv 1\pmod{\!m}\,$ hipotezi var $\,\gcd(a,m)= 1\,$ bu yüzden geçerli değil $\,(2k)^n\pmod{\! 4}.\,$ Bu gibi durumlarda gcd'yi çıkarabiliriz $\,a^N$ ve $\,m\,$Mod Dağıtım Yasası'nı kullanarak, Euler'in uygulandığı coprime durumuna indirgemek, örneğin buraya bakın . Bu durumda aşırılık olsa da, ortak faktörü dışarıda bırakmak için yukarıda uygulayabiliriz.$2^2$ aşağıdaki gibi

$$\quad\ \color{#0a0}{n\ge 2}\,\Rightarrow\,\color{#c00}{(2k)^{\large n}\!\bmod 4} \,=\, 2^2 (k^2 (2k)^{\large \color{#0a0}{n-2}}\!\bmod 1) \:\!=\:\! 2^2(0) \:\!=\:\! 0$$

Answer 3

\begin{align} 625703^{43898^{\scriptstyle614961^{\scriptstyle448629}}}\mkern-18mu\bmod 10&= (625703\bmod 10)^{43898^{\scriptstyle614961^{\scriptstyle448629}}\bmod\varphi(10)}\\ &= 3^{43898^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^{2^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^0. \end{align}