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.
Równania modularne
- Medea 2
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Równania modularne
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?
-
- Użytkownik
- Posty: 1017
- Rejestracja: 21 mar 2009, o 11:11
- Płeć: Mężczyzna
- Podziękował: 167 razy
- Pomógł: 152 razy
Równania modularne
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ą?
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
- Użytkownik
- Posty: 2491
- Rejestracja: 30 lis 2014, o 11:03
- Płeć: Kobieta
- Podziękował: 23 razy
- Pomógł: 479 razy
Równania modularne
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}\).
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}\).