Iloczyn reszt

[Thingoln]

Witajcie!
Czy jeśli są takie liczby \(\displaystyle{ m, n \in \mathbb{N}}\), że \(\displaystyle{ mn \equiv -1 \pmod{24}}\), to wynika z tego, że \(\displaystyle{ m \equiv 1 \wedge n \equiv -1 \pmod{24}}\) lub na odwrót? Wiem, że jeśli \(\displaystyle{ a \equiv b \pmod{l} \wedge c \equiv d \pmod{l}}\), to \(\displaystyle{ ac \equiv bd \pmod{l}}\), ale czy działa to także w drugą stronę jak u góry?

[Janusz Tracz]

Nie jest to prawa tak jak prawdą nie jest implikacja \(\displaystyle{ ab=cd \Rightarrow a=c \wedge b=d}\). Przykład (kontr)

\(\displaystyle{ 2 \cdot 3\equiv 1 \cdot 6 \pmod{7} }\)

ale

\(\displaystyle{ 2\not \equiv 1 \pmod{7} }\)


\(\displaystyle{ 3\not \equiv 6 \pmod{7} }\)

[Dasio11]

Co więcej: jeśli \(\displaystyle{ n \in \NN}\) i \(\displaystyle{ a \in \{ 0, 1, \ldots, n-1 \}}\) jest względnie pierwsze z \(\displaystyle{ n}\), to dla każdego \(\displaystyle{ y \in \ZZ}\) istnieje \(\displaystyle{ x \in \ZZ}\), takie że

\(\displaystyle{ a \cdot x \equiv y \pmod{n}}\).

W szczególności równanie

\(\displaystyle{ 5 \cdot x \equiv -1 \pmod{24}}\)

ma rozwiązanie, bo \(\displaystyle{ (5, 24) = 1}\). I faktycznie:

\(\displaystyle{ 5 \cdot 19 \equiv -1 \pmod{24}}\).

[Thingoln]

Rozumiem, dziękuję bardzo! Zastanawiałem się nad rozwiązaniem tego zadania i w ten sposób otrzymalibyśmy w bardzo szybki sposób tezę. Czy macie jakieś inne propozycje na rozwiązanie tego zadania (tak, widziałem wiadomości innych użytkowników w tym temacie)? Byłbym wdzięczny za jakieś ciekawe pomysły, zawsze świetnie poznać także inne metody.

[Dasio11]

Wiemy, że

\(\displaystyle{ mn \equiv -1 \pmod{24}}\)

a chcemy pokazać, że

\(\displaystyle{ m \equiv -n \pmod{24}}\).

Skoro tak ma być, to musi również zachodzić

\(\displaystyle{ mn \equiv -n^2 \pmod{24}}\)

co w połączeniu z założeniem daje

\(\displaystyle{ n^2 \equiv 1 \pmod{24}}\).

Spróbuj więc wykazać to ostatnie przystawanie, tym razem nie korzystając z tezy.

[Thingoln]

Udało mi się dojść do czegoś takiego. Czy ktoś mógłby przejrzeć i napisać, czy rozwiązanie jest poprawne?
Całkowite wielokrotności liczby 24 są liczbami parzystymi oraz \(\displaystyle{ 24|mn+1}\). Stąd widzimy, że iloczyn \(\displaystyle{ mn}\) musi być liczbą nieparzystą, a więc zarówno \(\displaystyle{ m}\), jak i \(\displaystyle{ n}\) są liczbami nieparzystymi.
Liczba \(\displaystyle{ n}\) przy dzieleniu przez 8 daje więc resztę równą: 1, 3, 5 lub 7. Z tego wynika, że \(\displaystyle{ n^2}\) przy dzieleniu przez 8 daje resztę równą 1 (prosty rachunek).
Rozważmy teraz resztę z dzielenia \(\displaystyle{ n}\) przez 3. Może być równa: -1, 0 lub 1.

Jeśli \(\displaystyle{ n \equiv 0 \pmod{3}}\), to \(\displaystyle{ n = 3k}\) dla pewnego \(\displaystyle{ k \in \mathbb{Z}}\).
Wówczas, jeśli \(\displaystyle{ 24|mn+1}\), to \(\displaystyle{ mn+1 = 24l}\), a więc
\(\displaystyle{ 24l = mn + 1 = m \cdot 3k + 1 = 3km + 1 \Rightarrow 1 = 24l - 3km = 3(8l-km)}\)
\(\displaystyle{ 8l-km \in \mathbb{Z}}\), a więc nie może być to spełnione, gdyż żadna całkowita wielokrotność trójki nie może się równać 1. Stąd
\(\displaystyle{ n}\) daje resztę z dzielenia przez 3 równą -1 lub 1, a więc
\(\displaystyle{ n^2 \equiv 1 \pmod{3}}\)

Jest więc spełnione
\(\displaystyle{ n^2 \equiv 1 \pmod{8} \wedge n^2 \equiv 1 \pmod{3}}\)
stąd
\(\displaystyle{ n^2 -1 = 8p = 3q}\), gdzie \(\displaystyle{ p, q \in \mathbb{Z}}\)

\(\displaystyle{ 8p = 3q}\) oraz \(\displaystyle{ \mathrm{NWD}(3, 8) = 1}\), z czego wynika, że \(\displaystyle{ 3|p \Rightarrow p = 3t}\), gdzie \(\displaystyle{ t \in \mathbb{Z}}\)

\(\displaystyle{ n^2 -1 = 8p = 8 \cdot 3t = 24t \Rightarrow n^2 = 24t + 1}\), a więc \(\displaystyle{ n^2}\) daje przy dzieleniu przez 24 resztę równą 1, co było do udowodnienia.

Zadanie pewnie dało się zrobić szybciej dzięki skorzystaniu z chińskiego twierdzenia o resztach, ale do tej pory nie udało mi się go poznać, jednak kojarzy mi się z takimi układami kongruencji. Czy to dobry trop na przyszłe próby przy okazji podobnych zadań?

[Dasio11]

Poprawnie. Można też być zauważyć, że skoro \(\displaystyle{ 24 \mid mn+1}\), to \(\displaystyle{ n}\) jest względnie pierwsze z \(\displaystyle{ 24}\) (bo jeśli \(\displaystyle{ d}\) jest wspólnym dzielnikiem \(\displaystyle{ n}\) i \(\displaystyle{ 24}\), to \(\displaystyle{ d \mid 24-mn = 1}\)), zatem \(\displaystyle{ n}\) jest nieparzyste i nie dzieli się przez \(\displaystyle{ 3}\). W związku z tym \(\displaystyle{ n-1}\) lub \(\displaystyle{ n+1}\) musi dzielić się przez \(\displaystyle{ 3}\), a ponadto jedna z tych liczb jest parzysta, a druga podzielna przez \(\displaystyle{ 4}\) - stąd \(\displaystyle{ n^2-1 = (n+1)(n-1)}\) dzieli się przez \(\displaystyle{ 24}\).