zadanie z teorii liczb

[marpus]

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

[Premislav]

Ż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]

Gdy \(\displaystyle{ \NWD\left( a,k\right)=1 }\) to z

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/To%C5%BCsamo%C5%9B%C4%87_B%C3%A9zouta

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

[marpus]

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?

[Janusz Tracz]

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

[a4karo]

W pierwszym przypadku wielkich twierdzeń nie trzeba: `24a'` jest zawsze podzielne przez `4`, więc nie może dawać reszty `1`.

[marpus]

Teraz to już nie rozumiem

[arek1357]

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