Równania modularne

[squared]

Mam do udowodnienia następujące sformułowania.

1) Jeżeli \(\displaystyle{ a \neq _n 0}\) w \(\displaystyle{ Z_n}\), to \(\displaystyle{ ax=0}\) ma niezerowe rozwiązanie wtedy i tylko wtedy gdy \(\displaystyle{ ax=1}\) nie ma rozwiązań w \(\displaystyle{ Z_n}\)

Rozbiłem to na dwie implikacje. Rozpocząłem od strony prawej do lewej. \(\displaystyle{ ax=1 \Leftrightarrow nk=ax-1 \Leftrightarrow ax+nk_1=1}\). A to ma rozwiązanie, gdy \(\displaystyle{ (a,n)|1 \rightarrow (a,n)=1}\). Zatem zakładamy, że \(\displaystyle{ (a,n) \neq 1}\).

Drugie równanie podobnie przekształcam i mam \(\displaystyle{ n|ax}\). No i jeśli dobrze myślę, to gdy \(\displaystyle{ (a,n)=1}\) to z Lematu Euklidesa mielibyśmy \(\displaystyle{ n|x}\), zatem nie byłoby niezerowego rozwiązania \(\displaystyle{ ax=0}\)? Czy dobrze myślę?

Jak w drugą stronę zrobić?

2) Każda liczba całkowita spełnia minimum jedną z podanych kongruencji:
\(\displaystyle{ x\equiv_2 0,x\equiv_4 1,x\equiv_{12} 3,x\equiv_3 1,x\equiv_8 3,x\equiv_{34} 23}\)
Oczywiście od razu zaprzeczyłem i próbowałem pokazać, że jeśli żadnej kongruencji liczba nie spełnia to jest to niemożliwe. Ale zagubiłem się w tym.

[Medea 2]

W drugim zapolujmy na tę liczbę, która nie spełnia niczego. Z pierwszej, drugiej i piątej kongruencji wynika, że taka liczba jest postaci \(\displaystyle{ 8k+7}\). Zauważ teraz, że trzecia i czwarta dopuszczają tylko liczby postaci \(\displaystyle{ 12l + 7}\). Potrafisz wykorzystać te dwa fakty w połączeniu z ostatnim przystawaniem?

[squared]

Z zaprzeczenia 1, 2 i 5 rzeczywiście wynika, że jest to liczba postaci \(\displaystyle{ 8l+7}\).

Jednak biorąc pod uwagę 3,4 na pewno nie mamy \(\displaystyle{ 12l + 7}\), gdyż \(\displaystyle{ 12l + 7=_3 1}\), a przecież nie chcemy by tak właśnie było.

Zaprzeczając 3,4 i 1 otrzymujemy, że Nasza liczba jest postaci \(\displaystyle{ 12k+5 \vee 12k+11}\)

Została jedynie ta ostatnia. Wiemy, że \(\displaystyle{ x \neq 34m+23}\)


A jakieś wskazówki do zadania 1 są?

[Medea 2]

Zaneguj obie strony: \(\displaystyle{ ax = 1}\) ma rozwiązanie w \(\displaystyle{ \ZZ}\) dokładnie wtedy, kiedy \(\displaystyle{ ay = 0}\) nie ma niezerowego.

Dowód w prawo (przez sprowadzenie do sprzeczności): załóżmy, że jednak \(\displaystyle{ ay = 0}\). Wiemy jednak, że \(\displaystyle{ ax = 1}\), zatem \(\displaystyle{ axy = 0x}\), lub inaczej: \(\displaystyle{ y = 0}\). Sprzeczność z tym, że \(\displaystyle{ y \neq 0}\).

[squared]

Chciałem się zapytać, jeszcze raz o zadanie 2. Bo skomentowałem je bez odzewu i nie wiem, czy ja się pomyliłem, czy poprzednia osoba.