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 --
wyznaczyć cyfre jednosci ,dziesiątek, setek
-
- Użytkownik
- Posty: 218
- Rejestracja: 12 sty 2011, o 17:05
- Płeć: Kobieta
- Lokalizacja: Polska
- SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
wyznaczyć cyfre jednosci ,dziesiątek, setek
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}\).
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}\).
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
wyznaczyć cyfre jednosci ,dziesiątek, setek
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.
\(\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.