Teoria Liczb - Zadania!
Teoria Liczb - Zadania!
Witam. Proszę o pomoc w rozwiązaniu zadań:
1. Znaleźć dwie liczby całkowite \(\displaystyle{ x, y}\) oraz NWD takie, że:
a) \(\displaystyle{ 1769x+551y=NWD(1769,551)}\)
b) \(\displaystyle{ 754x+221y=NWD(754,221)}\)
2.Znaleźć resztę z dzielenia:
a) \(\displaystyle{ 16^{231}+550}\) przez \(\displaystyle{ 17}\)
b) \(\displaystyle{ 3 \cdot 18^{18}-500 \cdot 5^{120}}\) przez \(\displaystyle{ 8}\)
3.Znaleźć ostatnią cyfrę liczby:
a) \(\displaystyle{ 7 \cdot 312^{553}-6543}\)
4.Pokazać, że
1) liczba \(\displaystyle{ 2222^{5555}+5555^{2222}}\) jest podzielna przez \(\displaystyle{ 7}\)
1. Znaleźć dwie liczby całkowite \(\displaystyle{ x, y}\) oraz NWD takie, że:
a) \(\displaystyle{ 1769x+551y=NWD(1769,551)}\)
b) \(\displaystyle{ 754x+221y=NWD(754,221)}\)
2.Znaleźć resztę z dzielenia:
a) \(\displaystyle{ 16^{231}+550}\) przez \(\displaystyle{ 17}\)
b) \(\displaystyle{ 3 \cdot 18^{18}-500 \cdot 5^{120}}\) przez \(\displaystyle{ 8}\)
3.Znaleźć ostatnią cyfrę liczby:
a) \(\displaystyle{ 7 \cdot 312^{553}-6543}\)
4.Pokazać, że
1) liczba \(\displaystyle{ 2222^{5555}+5555^{2222}}\) jest podzielna przez \(\displaystyle{ 7}\)
Ostatnio zmieniony 25 gru 2011, o 12:45 przez Anonymous, łącznie zmieniany 2 razy.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .Poprawa wiadomości.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .Poprawa wiadomości.
- 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
Teoria Liczb - Zadania!
1) Oznaczmy \(\displaystyle{ NWD(a,b) = (a,b)}\), wtedy z algorytmu Euklidesa: \(\displaystyle{ (1769 , 551) = (1769 \pmod{551} , 551) = (116 , 551) = (116 , 551 \pmod{116}) = (116 , 87) = (116\pmod{87} , 87) = (29,87) = 29}\)
Mamy więc:
\(\displaystyle{ 1769x + 551y = 29}\)
\(\displaystyle{ 1769x = 29 \pmod{551}}\)
\(\displaystyle{ 116x = 29 \pmod{551} /:29}\)
\(\displaystyle{ 4x = 1 \pmod{19} /\cdot 5}\)
\(\displaystyle{ x = 5\pmod{19} \Leftrightarrow x = 19k+5}\)
Wstawiamy do naszego równania i dostajemy:
\(\displaystyle{ (x,y) = (19k+5 , -61k-16) , k\in \mathbb{Z}}\)
2 przykład analogicznie.
2a) \(\displaystyle{ 16^{231}+550 \equiv (-1)^{231}+6 = -1+6 = 5 \pmod{17}}\)
2b) \(\displaystyle{ 3\cdot 18^{18} - 500\cdot 5^{120} \equiv 3\cdot 2^{18} - 4\cdot 5^{120} \equiv -4\cdot 25^{60} \equiv -4\cdot 1^{60} \equiv -4 \equiv 4\pmod{8}}\)
3) Zauważ, że \(\displaystyle{ 2^{4k+1} \equiv 2 \pmod{10}/:2 \Leftrightarrow 2^{4k} \equiv 1 \pmod{5} \Leftrightarrow 16^k \equiv 1 \pmod{5} \Leftrightarrow 1 \equiv 1\pmod{5}}\)
więc \(\displaystyle{ 7\cdot 312^{553} - 6543 \equiv 7\cdot 2^{553} - 3 \equiv 7\cdot 2^{4\cdot 138 + 1} - 3 \equiv 7\cdot 2-3 \equiv 1 \pmod{10}}\)
4) Zakładam, że tak miało być:
\(\displaystyle{ 2222^{5555} + 5555^{2222} \equiv 3^{5555} + 4^{2222} \equiv 3\cdot 3^{5554} + 16^{1111} \equiv 3\cdot 9^{2777} + 2^{1111} \equiv 3\cdot 2^{2777} + 2^{1111} \equiv 3\cdot 2^2 \cdot 2^{3\cdot 925} + 2\cdot 2^{3\cdot 370} \equiv 12 \cdot 8^{925} + 2\cdot 8^{370} \equiv 12+2 \equiv 14 \equiv 0\pmod{7}}\)
Mamy więc:
\(\displaystyle{ 1769x + 551y = 29}\)
\(\displaystyle{ 1769x = 29 \pmod{551}}\)
\(\displaystyle{ 116x = 29 \pmod{551} /:29}\)
\(\displaystyle{ 4x = 1 \pmod{19} /\cdot 5}\)
\(\displaystyle{ x = 5\pmod{19} \Leftrightarrow x = 19k+5}\)
Wstawiamy do naszego równania i dostajemy:
\(\displaystyle{ (x,y) = (19k+5 , -61k-16) , k\in \mathbb{Z}}\)
2 przykład analogicznie.
2a) \(\displaystyle{ 16^{231}+550 \equiv (-1)^{231}+6 = -1+6 = 5 \pmod{17}}\)
2b) \(\displaystyle{ 3\cdot 18^{18} - 500\cdot 5^{120} \equiv 3\cdot 2^{18} - 4\cdot 5^{120} \equiv -4\cdot 25^{60} \equiv -4\cdot 1^{60} \equiv -4 \equiv 4\pmod{8}}\)
3) Zauważ, że \(\displaystyle{ 2^{4k+1} \equiv 2 \pmod{10}/:2 \Leftrightarrow 2^{4k} \equiv 1 \pmod{5} \Leftrightarrow 16^k \equiv 1 \pmod{5} \Leftrightarrow 1 \equiv 1\pmod{5}}\)
więc \(\displaystyle{ 7\cdot 312^{553} - 6543 \equiv 7\cdot 2^{553} - 3 \equiv 7\cdot 2^{4\cdot 138 + 1} - 3 \equiv 7\cdot 2-3 \equiv 1 \pmod{10}}\)
4) Zakładam, że tak miało być:
\(\displaystyle{ 2222^{5555} + 5555^{2222} \equiv 3^{5555} + 4^{2222} \equiv 3\cdot 3^{5554} + 16^{1111} \equiv 3\cdot 9^{2777} + 2^{1111} \equiv 3\cdot 2^{2777} + 2^{1111} \equiv 3\cdot 2^2 \cdot 2^{3\cdot 925} + 2\cdot 2^{3\cdot 370} \equiv 12 \cdot 8^{925} + 2\cdot 8^{370} \equiv 12+2 \equiv 14 \equiv 0\pmod{7}}\)
Teoria Liczb - Zadania!
Mam pytanie odnosnie zadania 4. Jak toszedles do tego ze z podstawy 2222 zmieniles na 3 i z 5555 na 4 ?
Teoria Liczb - Zadania!
Pewnie stąd, że
\(\displaystyle{ 2222 \equiv 3 \pmod{7}}\) i \(\displaystyle{ 5555\equiv 4 \pmod{7}}\)
\(\displaystyle{ 2222 \equiv 3 \pmod{7}}\) i \(\displaystyle{ 5555\equiv 4 \pmod{7}}\)
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Teoria Liczb - Zadania!
abc666 mam pytanie:
skoro:
2222=3
to:
\(\displaystyle{ 2222^{5555}=5}\)
ale: 55552222=5
i masz: 5+5=10=3 a nie zero no więc??
skoro:
2222=3
to:
\(\displaystyle{ 2222^{5555}=5}\)
ale: 55552222=5
i masz: 5+5=10=3 a nie zero no więc??
Ostatnio zmieniony 25 gru 2011, o 12:34 przez arek1357, łącznie zmieniany 2 razy.
Teoria Liczb - Zadania!
Nie rozumiem twojego pytania. Nigdzie nie pisałem równości, a jeśli to miały być przystawania to i tak są błędne.
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Teoria Liczb - Zadania!
przepraszam pomyliłem się ale poprawiłem ale dalej mi nie wychodzi podzielność
a pytanie było retoryczne.
Teraz się już wszystko zgadza
a pytanie było retoryczne.
Teraz się już wszystko zgadza
Ostatnio zmieniony 25 gru 2011, o 13:17 przez arek1357, łącznie zmieniany 2 razy.
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Teoria Liczb - Zadania!
W kongruencji modulo \(\displaystyle{ n}\) nie jest prawdą, że \(\displaystyle{ b\equiv c \mbox{ (mod n)} \Rightarrow a^b\equiv a^c\mbox{ (mod n)}}\)
Prawdą jest natomiast \(\displaystyle{ b\equiv c \mbox{ (mod }\phi (n)) \Rightarrow a^b\equiv a^c\mbox{ (mod n)}}\)
Prawdą jest natomiast \(\displaystyle{ b\equiv c \mbox{ (mod }\phi (n)) \Rightarrow a^b\equiv a^c\mbox{ (mod n)}}\)
Teoria Liczb - Zadania!
\(\displaystyle{ 2222^{5555}\equiv 5 \pmod{7}\\arek1357 pisze: skoro:
2222=3
to:
\(\displaystyle{ 2222^{5555}=3}\)
ale: 55552222=5
i masz: 3+5=8=1 a nie zero no więc??
5555^{2222}\equiv 2 \pmod{7}}\)
Zresztą Vax napisał już rozwiązanie.
- arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Teoria Liczb - Zadania!
oj tak poprawiłem z tym pierwszym ale tam nie było 5555 do potęgi 2222
tylko 55552222
zamotałem sie-- 25 grudnia 2011, 12:40 --i w pierwszym w rachunkach się pomyliłem a drugie przeliczyłem dobrze adekwatnie do zapisu stąd całe zamieszanie
tylko 55552222
zamotałem sie-- 25 grudnia 2011, 12:40 --i w pierwszym w rachunkach się pomyliłem a drugie przeliczyłem dobrze adekwatnie do zapisu stąd całe zamieszanie