zadanie z teorii liczb
-
- Użytkownik
- Posty: 88
- Rejestracja: 4 lut 2016, o 23:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 24 razy
zadanie z teorii liczb
Mam takie zadanie, nie wiem jak się w ogóle za niego zabrać. Gorąca prośba o nakierowanie, informację jak się to nazywa (?) czego szukać w necie
Dla danej liczby \(\displaystyle{ a}\) znajdź liczbę \(\displaystyle{ a' }\) taką, że \(\displaystyle{ a \cdot a' \equiv 1 \pmod{k} }\) (lub uzasadnij, że nie istnieje) jeżeli:
i) \(\displaystyle{ a = 24, k = 4}\)
Dla danej liczby \(\displaystyle{ a}\) znajdź liczbę \(\displaystyle{ a' }\) taką, że \(\displaystyle{ a \cdot a' \equiv 1 \pmod{k} }\) (lub uzasadnij, że nie istnieje) jeżeli:
i) \(\displaystyle{ a = 24, k = 4}\)
Ostatnio zmieniony 15 gru 2020, o 22:22 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: zadanie z teorii liczb
Żeby dla danych \(\displaystyle{ a,k}\) istniało takie \(\displaystyle{ a'\in \ZZ}\), że \(\displaystyle{ a\cdot a'\equiv 1\pmod{k}}\), potrzeba i wystarcza, by \(\displaystyle{ \NWD(a,k)=1}\) (i jeśli ten warunek jest spełniony, to można takie, oczywiście niejedyne, \(\displaystyle{ a'}\) znaleźć za pomocą rozszerzonego algorytmu Euklidesa). Tutaj tak nie jest, wszakże \(\displaystyle{ \NWD(24, 4)=4}\).
- Janusz Tracz
- Użytkownik
- Posty: 4074
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: zadanie z teorii liczb
Gdy \(\displaystyle{ \NWD\left( a,k\right)=1 }\) to z wynika, że istnieją takie stałe, liczby całkowite \(\displaystyle{ x,y\in \ZZ}\), że \(\displaystyle{ ax+ky=1}\). Zatem biorąc stornami resztę z dzielenia przez \(\displaystyle{ k}\) (to znaczy robimy \(\displaystyle{ \text{mod} \ k}\) stronami) dostajemy \(\displaystyle{ ax+ky=_k ax=_k1}\). Zatem \(\displaystyle{ x}\) jest szukaną wartością \(\displaystyle{ x=a'}\). Zatem \(\displaystyle{ \NWD\left( a,k\right)=1 }\) wystarcza. A to, że \(\displaystyle{ \NWD\left( a,k\right)=1 }\) jest warunkiem konicznym wynika z tego, że lematu Bézouta da się odwrócić i z istnienia liczb całkowitych \(\displaystyle{ x,y}\) takich, że \(\displaystyle{ ax+ky=1}\) wnioskujemy o \(\displaystyle{ \NWD\left( a,k\right)=1 }\).
PS lematu Bézouta jest tu tylko przydatnym narzędziem ale sam w sobie trywialny nie jest trywialny. Więc ostatecznie tak jak pisał Premislav sprawa kręci się wokół rozszerzonego algorytmu Euklidesa.
Tak czy inaczej... jeśli masz \(\displaystyle{ a,k}\) oraz umiesz rozwiązać równanie diofantyczne \(\displaystyle{ ax+ky=1}\) to łatwo już znaleźć takie \(\displaystyle{ a'}\), że \(\displaystyle{ aa'=1\mod k}\)
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/To%C5%BCsamo%C5%9B%C4%87_B%C3%A9zouta
PS lematu Bézouta jest tu tylko przydatnym narzędziem ale sam w sobie trywialny nie jest trywialny. Więc ostatecznie tak jak pisał Premislav sprawa kręci się wokół rozszerzonego algorytmu Euklidesa.
Tak czy inaczej... jeśli masz \(\displaystyle{ a,k}\) oraz umiesz rozwiązać równanie diofantyczne \(\displaystyle{ ax+ky=1}\) to łatwo już znaleźć takie \(\displaystyle{ a'}\), że \(\displaystyle{ aa'=1\mod k}\)
-
- Użytkownik
- Posty: 88
- Rejestracja: 4 lut 2016, o 23:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 24 razy
Re: zadanie z teorii liczb
to mam inny przykład
\(\displaystyle{ a = 8\\
k = 3}\)
\(\displaystyle{ (8,3) = 1}\)
\(\displaystyle{ 1 = 3-1\cdot 2 = 3-1\cdot (8-2\cdot 3) = 3-1\cdot 8+2\cdot 3 = -1\cdot 8 + 3\cdot 3}\)
zatem \(\displaystyle{ ( x_{0}, y_{0} ) = (-1, 3)}\)
@edit
aaaa
Czyli, że
\(\displaystyle{ a\cdot x_{0}\bmod{k} = 1\\
8\cdot (-1)\bmod{3} = 1}\)
czyli \(\displaystyle{ a'}\), które miałem znaleźć to \(\displaystyle{ -1}\)
że o to chodzi?
\(\displaystyle{ a = 8\\
k = 3}\)
\(\displaystyle{ (8,3) = 1}\)
\(\displaystyle{ 1 = 3-1\cdot 2 = 3-1\cdot (8-2\cdot 3) = 3-1\cdot 8+2\cdot 3 = -1\cdot 8 + 3\cdot 3}\)
zatem \(\displaystyle{ ( x_{0}, y_{0} ) = (-1, 3)}\)
@edit
aaaa
Czyli, że
\(\displaystyle{ a\cdot x_{0}\bmod{k} = 1\\
8\cdot (-1)\bmod{3} = 1}\)
czyli \(\displaystyle{ a'}\), które miałem znaleźć to \(\displaystyle{ -1}\)
że o to chodzi?
Ostatnio zmieniony 15 gru 2020, o 23:41 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot. Poprawa wiadomości.
Powód: Symbol mnożenia to \cdot. Poprawa wiadomości.
- Janusz Tracz
- Użytkownik
- Posty: 4074
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1395 razy
Re: zadanie z teorii liczb
Tak mnie więcej o to chodzi. Tylko, że świecie \(\displaystyle{ \text{mod } 3}\) mamy \(\displaystyle{ 8=2}\) oraz \(\displaystyle{ -1=2}\). Zatem Faktycznie pytanie to wyznaczenie takiej liczby \(\displaystyle{ a'}\), że \(\displaystyle{ 2a'=1 \text{mod } 3}\). I to jest \(\displaystyle{ a'=2}\) tak jak zostało to pokazane. Czyli liczba \(\displaystyle{ 2}\) jest odwrotna do samej siebie w świecie \(\displaystyle{ \text{mod } 3}\) co łatwo sprawdzić: \(\displaystyle{ 2 \cdot 2=3+1=1}\).
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: zadanie z teorii liczb
W pierwszym przypadku wielkich twierdzeń nie trzeba: `24a'` jest zawsze podzielne przez `4`, więc nie może dawać reszty `1`.
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: zadanie z teorii liczb
Masz pierścień:
\(\displaystyle{ \left( \ZZ_{k},+, \cdot \right) }\)
Pierścień modulo...
I teraz zbiór elementów odwracalnych w tym pierścieniu tworzy grupę (z mnożeniem modulo) a w grupie każdy element ma swój element odwrotny...
Grupę tworzą takie.:
\(\displaystyle{ x \in \ZZ_{k}}\) , że:
\(\displaystyle{ (x,k)=1}\)
I tyle w tym temacie...
\(\displaystyle{ \left( \ZZ_{k},+, \cdot \right) }\)
Pierścień modulo...
I teraz zbiór elementów odwracalnych w tym pierścieniu tworzy grupę (z mnożeniem modulo) a w grupie każdy element ma swój element odwrotny...
Grupę tworzą takie.:
\(\displaystyle{ x \in \ZZ_{k}}\) , że:
\(\displaystyle{ (x,k)=1}\)
I tyle w tym temacie...