Witam.
Mam do rozwiazązania takie dwa zadania:
1. Niech liczba \(\displaystyle{ b}\) będzie względnie pierwsza z liczbą \(\displaystyle{ m}\) i niech \(\displaystyle{ a}\) i \(\displaystyle{ c}\) będą liczbami całkowitymi dodatnimi. Udowodnij że jeśli \(\displaystyle{ b^{a} \equiv 1 \pmod{m}}\), \(\displaystyle{ b^{c} \equiv 1 \pmod{m}}\) oraz \(\displaystyle{ d = NWD(a,c)}\) to \(\displaystyle{ b^{d} \equiv 1 \pmod{m}}\)
I mam rozwiązanie, które rozumiem do pewnego momentu.
\(\displaystyle{ d=xa+yc \\
b^{d} = b ^{xa+yc} = b^{ax}b^{cy}}\)
I dalej w rozwiązaniu mam coś, co nie wiem skąd się wzięło, , tzn, dlaczego \(\displaystyle{ b^{a}^{x}}\) przystaje modulo \(\displaystyle{ 1}\), i jak to uzasadnić:
\(\displaystyle{ b^{ax} \equiv 1 \pmod{m} \\
b^{cy} \equiv 1 \pmod{m}}\)
EDIT: Wnioskuje ze to działa dlatego, że, nie wiem jak to nazwać poprawnie, ale w relacji modulo mnozenie dziala tak samo jak normalnie w zbiorze \(\displaystyle{ R}\), tzn np jezeli:
\(\displaystyle{ 5 = 2 \pmod {3} \ to \ 5 \cdot 5 = 2 \cdot 2 \pmod {3}}\)?
Oraz zadanie nr 2, które w dużej mierze wynika z 1, jednak bez zrozumienia tego 1 nie wiem jak się za to zabrać.
2. Udowodnij, że jeśli \(\displaystyle{ p}\) jest dzielnikiem pierwszym liczby \(\displaystyle{ b^{n} - 1}\), to
a) \(\displaystyle{ p|b^{d}-1}\) dla pewnego właściwego dzielnika d liczby n, lub
b) \(\displaystyle{ p \equiv 1 \pmod{n}}\)
Jeśli \(\displaystyle{ p>2}\) i liczba n jest nieparzysta, to w przypadku b) mamy \(\displaystyle{ b \equivs 1 \pmod{2n}}\)
Z tego co wiem do drugiego przydaje się tw. Fermata.
Z góry dzięki za pomoc!
Przystawanie potęg w relacji modulo - dowód.
-
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Przystawanie potęg w relacji modulo - dowód.
Skoro \(\displaystyle{ b^{a} \equiv 1 \pmod{m}}\) to jak podniesiesz tę kongruencje stronami do potęgi \(\displaystyle{ x}\) to dostaniesz to co oni.I dalej w rozwiązaniu mam coś, co nie wiem skąd się wzięło, , tzn, dlaczego \(\displaystyle{ b^{a}^{x}}\) przystaje modulo \(\displaystyle{ 1}\), i jak to uzasadnić:
Tak, dokładnie tak to działa.EDIT: Wnioskuje ze to działa dlatego, że, nie wiem jak to nazwać poprawnie, ale w relacji modulo mnozenie dziala tak samo jak normalnie w zbiorze \(\displaystyle{ R}\), tzn np jezeli:
5 = 2 mod 3 to 5*5 = 2*2 mod 3
-
- Użytkownik
- Posty: 21
- Rejestracja: 5 lis 2010, o 16:32
- Płeć: Mężczyzna
- Lokalizacja: Kraków Śródmieście
- Podziękował: 8 razy
Przystawanie potęg w relacji modulo - dowód.
Dzięki za odpowiedź.
Nadal jednak nie wiem jak rozwiązać zadanie 2-gie.
Podpunkt a) zdaje się być dosyć podobny do zadania 1-szego, z tą różnicą, że \(\displaystyle{ b ^{de} \equiv 1 \pmod {p}}\)
a potem pierwiastkujemy obie strony przez e. Taki przynajmniej był mój pomysł.
Co natomiast z podpunktem b?
Nadal jednak nie wiem jak rozwiązać zadanie 2-gie.
Podpunkt a) zdaje się być dosyć podobny do zadania 1-szego, z tą różnicą, że \(\displaystyle{ b ^{de} \equiv 1 \pmod {p}}\)
a potem pierwiastkujemy obie strony przez e. Taki przynajmniej był mój pomysł.
Co natomiast z podpunktem b?