Matematyka.pl

Wyzanczyć cyfrę jedności dziesiątek i setek liczby, wykorzystując kongruencje

a) \(\displaystyle{ 2005 ^{2008}}\)
b) \(\displaystyle{ 2008 ^{2007}}\)-- 16 maja 2011, o 20:46 --

Nie mam pojęcia na jakim jesteś poziomie i z czego Ci wolno korzystać, ale ogólnie to jest tak, że chcesz sprawdzić do czego przystają te liczby modulo \(\displaystyle{ 10^k}\) dla \(\displaystyle{ k=1,2,3}\). Wg mnie najprościej sprawdzić do czego przystaje ta liczba modulo \(\displaystyle{ 2^k}\) oraz \(\displaystyle{ 5^k}\) po czym skorzystać z "konstruktywnej wersji" chińskiego twierdzenia o resztach, żeby zbadać do czego przystaje liczba dana w zadaniu modulo iloczyn \(\displaystyle{ 5^k2^k}\).

Jeżeli zaś chińskie twierdzenie o resztach jest Ci nieznane i nie możesz go używać, pozostaje sprawdzać kolejne potęgi aż się zapętli.

Drobna uwaga: niezależnie od tego jak liczysz od razu skorzystaj z \(\displaystyle{ (2000+n)^m\equiv n^m\pmod{10^k}}\) dla \(\displaystyle{ k=1,2,3}\).

Wyznaczając ostatnie 3 cyfry wyznaczymy oczywiście od razu cyfrę setek, dziesiątek i jedności, zauważ, że:

\(\displaystyle{ x \equiv 2005^{2008} \equiv 5^{2008}\pmod{1000}}\)

Teraz rozbijamy daną kongruencje na układ 2 kongruencji:

\(\displaystyle{ \begin{cases} x \equiv 5^{2008} \equiv 25^{1004} \equiv 1\pmod{8}\\ x \equiv 5^{2008} \equiv 0\pmod{125} \end{cases}}\)

Z 1 kongruencji mamy \(\displaystyle{ x = 8a+1}\) wstawiamy do 2: \(\displaystyle{ 8a+1 \equiv 0\pmod{125} \Leftrightarrow 8a \equiv 124\pmod{125} /:4 \Leftrightarrow 2a \equiv 31\pmod{125} /\cdot 63 \Leftrightarrow a \equiv 78\pmod{125} \Leftrightarrow a = 125n+78}\) wstawiamy do wcześniejszego: \(\displaystyle{ x = 8(125n+78)+1 = 1000n+625}\) stąd 3 ostatnie cyfry danej liczby to 625.


2 przykład analogicznie jak powyżej:

\(\displaystyle{ x\equiv 2008^{2007} \equiv 8^{2007}\pmod{1000}}\)

\(\displaystyle{ \begin{cases} x\equiv 8^{2007} \equiv 0\pmod{8}\\ x\equiv 8^{2007}\pmod{125} \end{cases}}\)

W 2 kongruencji korzystamy z twierdzenia Eulera i otrzymujemy:

\(\displaystyle{ 8^{\varphi(5^3)} = 8^{100} \equiv 1\pmod {125} \Rightarrow 8^{2000} \equiv 1\pmod{125}}\)

Czyli kończąc 2 kongruencję:

\(\displaystyle{ x \equiv 8^{2007} \equiv 8^7 \cdot 8^{2000} \equiv 8^7 \equiv 27\pmod{125}}\)

Wobec tego:

\(\displaystyle{ \begin{cases} x \equiv 0\pmod{8}\\ x\equiv 27\pmod{125} \end{cases}}\)

Z 2 mamy \(\displaystyle{ x=125a+27}\) wstawiamy do 1: \(\displaystyle{ 125a+27 \equiv 0\pmod{8} \Leftrightarrow 5a + 3 \equiv 0\pmod{8} \Leftrightarrow 5a \equiv 5\pmod{8}/:5 \Rightarrow a \equiv 1\pmod{8} \Leftrightarrow a = 8n+1}\) wstawiamy:

\(\displaystyle{ x = 125(8n+1)+27 = 1000n+152}\) zatem 3 ostatnie cyfry wynoszą 152.

Pozdrawiam.

Ach, znakomicie Vax, moja szkoła. Rachunków nie sprawdzam, ale wygląda jakby było wporzo