dwa zadania z teorii liczb

[malgosia270000]

Witam,mam do rozwiązania 2 zadania za które nie wiem jak mam się zabrać..

zad.1. znajdź trzy ostatnie cyfry największej znanej liczby pierwszej czyli \(\displaystyle{ 2^{43112609}-1}\)
(wskazówka. rozpatrz dwie kongruencje mod125 i mod8)

zad.2. znajdź dwie ostatnie cyfry liczby \(\displaystyle{ 9^{ 9^{ 9^{9} } }}\)

dziękuję za jakąkolwiek pomoc i wyjaśnienia.

[bosa_Nike]

1.:    

Dla każdego \(\displaystyle{ n\ge 3}\) mamy \(\displaystyle{ 2^n\equiv 0\pmod 8}\), więc \(\displaystyle{ 2^{43112609}-1\equiv 7\pmod 8}\), prawda? Dalej mamy:

\(\displaystyle{ 2^{43112609}-1=2^9\cdot\left(2^{100}\right)^{431126}-1=2^9\cdot\left(2^{\varphi\left(5^3\right)}\right)^{431126}-1\equiv\\ 2^9-1=128\cdot 4-1\equiv11\pmod {5^3}}\)

No to masz układ kongruencji liniowych, gdzie \(\displaystyle{ x=2^{43112609}-1}\):

\(\displaystyle{ \begin{cases}x\equiv 7\pmod 8\\ x\equiv 11\pmod {125}\end{cases}}\)

Masz policzyć \(\displaystyle{ x\bmod {1000}}\). Dalej sama.

2.:    

Dla każdego \(\displaystyle{ n}\) masz \(\displaystyle{ 9^n\equiv 1\pmod 4}\). Z tego wynika w szczególności, że \(\displaystyle{ 9^{9^{9^{9}}}\equiv 1\pmod 4}\) oraz że \(\displaystyle{ 9^9=4m+1}\) dla pewnego \(\displaystyle{ m}\). Stąd \(\displaystyle{ 9^{9^{9}}=9^{4m+1}\equiv 9\cdot (-1)^{4m}\equiv 4\pmod 5}\). Dodatkowo oczywiście \(\displaystyle{ 9^{9^{9}}\equiv 1\pmod 2}\), więc \(\displaystyle{ 9^{9^{9}}\equiv9\pmod {10}}\), czyli \(\displaystyle{ 9^{9^{9}}=10t+9}\) dla pewnego \(\displaystyle{ t}\). Stąd mamy:

\(\displaystyle{ 9^{9^{9^{9}}}=9^{10t+9}=9\cdot 81^4\cdot \left( 9^{10}\right)^t\equiv 9\cdot 6^2\cdot 6^2\cdot \left(9\cdot 9^9\right)^t\equiv 9\cdot 11^2\cdot \left(9\cdot 9^9\right)^t\equiv\\ 9\cdot (-4)\cdot \left(81\cdot (-4)\right)^t\equiv 9\cdot (-4)\cdot \left(6\cdot (-4)\right)^t\equiv 14\pmod {25}}\)

Znów masz układ kongruencji liniowych, gdzie \(\displaystyle{ x=9\uparrow\uparrow 4}\):

\(\displaystyle{ \begin{cases}x\equiv 1\pmod 4\\ x\equiv 14\pmod {25}\end{cases}}\)

Masz policzyć \(\displaystyle{ x\bmod {100}}\).

Mam nadzieję, że się nie pomyliłam...