Dla jakich \(\displaystyle{ n \geq 2}\) z tego, że \(\displaystyle{ xy \equiv -1 \ (\bmod n)}\) wynika, że \(\displaystyle{ x \equiv -y \ (\bmod n)}\) ?Kongruencje
-
mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Kongruencje
Dla jakich \(\displaystyle{ n \geq 2}\) z tego, że \(\displaystyle{ xy \equiv -1 \ (\bmod n)}\) wynika, że \(\displaystyle{ x \equiv -y \ (\bmod n)}\) ?
Ostatnio zmieniony 13 cze 2022, o 12:35 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Dasio11
- Moderator
- Posty: 10223
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2361 razy
Re: Kongruencje
Łatwo sprawdzić, że \(\displaystyle{ n = 2}\) spełnia warunek. Ustalmy więc dowolne \(\displaystyle{ n \ge 3}\) i rozważmy pierścień \(\displaystyle{ \ZZ_n}\) oraz podzbiór $$K = \{ x^2 \bmod{n} : x \in \ZZ_n^* \},$$ który jak wiadomo jest podgrupą grupy multiplikatywnej \(\displaystyle{ \ZZ_n^*}\) indeksu dwa.
W języku pierścienia \(\displaystyle{ \ZZ_n}\) warunek z treści zapisuje się jako
- Dla dowolnych \(\displaystyle{ x, y \in \ZZ_n}\) jeśli \(\displaystyle{ xy = -1}\), to \(\displaystyle{ x = -y}\).
Ponieważ dla \(\displaystyle{ x \in \ZZ_n \setminus \ZZ_n^*}\) nie istnieje \(\displaystyle{ y \in \ZZ_n}\) spełniający \(\displaystyle{ xy = -1}\), zaś dla \(\displaystyle{ x \in \ZZ_n^*}\) taki igrek istnieje dokładnie jeden i jest nim \(\displaystyle{ -x^{-1}}\), warunek z treści jest równoważny kolejno
- Dla dowolnego \(\displaystyle{ x \in \ZZ_n^*}\) zachodzi \(\displaystyle{ x = x^{-1}}\),
- Dla dowolnego \(\displaystyle{ x \in \ZZ_n^*}\) zachodzi \(\displaystyle{ x^2 = 1}\),
- \(\displaystyle{ K = \{ 1 \}}\),
- \(\displaystyle{ |\ZZ_n^*| = 2}\),
- \(\displaystyle{ \varphi(n) = 2}\),
gdzie \(\displaystyle{ \varphi}\) jest funkcją Eulera. Ostatnią równość spełniają zaś dokładnie \(\displaystyle{ n = 3, 4, 6}\), zatem ostatecznie warunek z treści jest spełniony dla \(\displaystyle{ n \in \{ 2, 3, 4, 6 \}}\).
W języku pierścienia \(\displaystyle{ \ZZ_n}\) warunek z treści zapisuje się jako
- Dla dowolnych \(\displaystyle{ x, y \in \ZZ_n}\) jeśli \(\displaystyle{ xy = -1}\), to \(\displaystyle{ x = -y}\).
Ponieważ dla \(\displaystyle{ x \in \ZZ_n \setminus \ZZ_n^*}\) nie istnieje \(\displaystyle{ y \in \ZZ_n}\) spełniający \(\displaystyle{ xy = -1}\), zaś dla \(\displaystyle{ x \in \ZZ_n^*}\) taki igrek istnieje dokładnie jeden i jest nim \(\displaystyle{ -x^{-1}}\), warunek z treści jest równoważny kolejno
- Dla dowolnego \(\displaystyle{ x \in \ZZ_n^*}\) zachodzi \(\displaystyle{ x = x^{-1}}\),
- Dla dowolnego \(\displaystyle{ x \in \ZZ_n^*}\) zachodzi \(\displaystyle{ x^2 = 1}\),
- \(\displaystyle{ K = \{ 1 \}}\),
- \(\displaystyle{ |\ZZ_n^*| = 2}\),
- \(\displaystyle{ \varphi(n) = 2}\),
gdzie \(\displaystyle{ \varphi}\) jest funkcją Eulera. Ostatnią równość spełniają zaś dokładnie \(\displaystyle{ n = 3, 4, 6}\), zatem ostatecznie warunek z treści jest spełniony dla \(\displaystyle{ n \in \{ 2, 3, 4, 6 \}}\).