Teoria Liczb - Zadania!

[elo2434]

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}\)

[Natasha]

1. tutaj można algorytmem Euklidesa.

[Vax]

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}}\)

[Dexous]

Mam pytanie odnosnie zadania 4. Jak toszedles do tego ze z podstawy 2222 zmieniles na 3 i z 5555 na 4 ?

[abc666]

Pewnie stąd, że
\(\displaystyle{ 2222 \equiv 3 \pmod{7}}\) i \(\displaystyle{ 5555\equiv 4 \pmod{7}}\)

[arek1357]

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??

[abc666]

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]

przepraszam pomyliłem się ale poprawiłem ale dalej mi nie wychodzi podzielność
a pytanie było retoryczne.
Teraz się już wszystko zgadza

[Zordon]

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)}}\)

[abc666]

skoro:

2222=3
to:

\(\displaystyle{ 2222^{5555}=3}\)

ale: 55552222=5

i masz: 3+5=8=1 a nie zero no więc??

\(\displaystyle{ 2222^{5555}\equiv 5 \pmod{7}\\
5555^{2222}\equiv 2 \pmod{7}}\)
Zresztą Vax napisał już rozwiązanie.

[arek1357]

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