rownowaznosc kongruencji
-
photoshopek
- Użytkownik
- Posty: 1
- Rejestracja: 24 lut 2013, o 13:01
- Płeć: Kobieta
- Lokalizacja: Toruń
rownowaznosc kongruencji
\(\displaystyle{ 2^n \equiv 2^m \ \pmod{9}}\) jest równoważne \(\displaystyle{ m-n \equiv 0 \ \pmod{6}}\). Dlaczego?
Ostatnio zmieniony 24 lut 2013, o 14:53 przez Vardamir, łącznie zmieniany 2 razy.
Powód: Modulo zapisujemy \pmod{n} .
Powód: Modulo zapisujemy \pmod{n} .
-
Piotr Rutkowski
- Użytkownik
- Posty: 2234
- Rejestracja: 26 paź 2006, o 18:08
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 390 razy
rownowaznosc kongruencji
Zauważ, że \(\displaystyle{ 2^{3}\equiv -1 \ (mod9)}\), a \(\displaystyle{ 2^{6}\equiv 1 \ (mod9)}\)
Stąd wynika, że \(\displaystyle{ \forall_{k,l\in \mathbb{N}}2^{6k+l}\equiv 2^{l} \ (mod 9) \ (*)}\) skąd masz implikację w lewą stronę. Implikacja w prawo jest równie prosta:
WLOG założymy, że \(\displaystyle{ n\geq m}\), wtedy
\(\displaystyle{ 2^{n}-2^{m}=2^{m}(2^{n-m}-1)}\)
Oczywiście \(\displaystyle{ (9\not | 2^{m})}\) zatem \(\displaystyle{ 9|2^{n-m}-1}\)
Korzystając z \(\displaystyle{ (*) \ 2^{n-m}-1\equiv 2^{(n-m) (mod6)}-1\equiv 0 \ (mod9)}\) skąd widzimy, że \(\displaystyle{ n\equiv m \ (mod6)}\), bo \(\displaystyle{ (n-m)(mod6)\in \{0,1,2,3,4,5\}}\).
Pozdrawiam
Stąd wynika, że \(\displaystyle{ \forall_{k,l\in \mathbb{N}}2^{6k+l}\equiv 2^{l} \ (mod 9) \ (*)}\) skąd masz implikację w lewą stronę. Implikacja w prawo jest równie prosta:
WLOG założymy, że \(\displaystyle{ n\geq m}\), wtedy
\(\displaystyle{ 2^{n}-2^{m}=2^{m}(2^{n-m}-1)}\)
Oczywiście \(\displaystyle{ (9\not | 2^{m})}\) zatem \(\displaystyle{ 9|2^{n-m}-1}\)
Korzystając z \(\displaystyle{ (*) \ 2^{n-m}-1\equiv 2^{(n-m) (mod6)}-1\equiv 0 \ (mod9)}\) skąd widzimy, że \(\displaystyle{ n\equiv m \ (mod6)}\), bo \(\displaystyle{ (n-m)(mod6)\in \{0,1,2,3,4,5\}}\).
Pozdrawiam