Przystawanie potęg w relacji modulo - dowód.

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
huteusz
Użytkownik
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.

Post autor: huteusz »

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!
Ostatnio zmieniony 10 lis 2013, o 10:53 przez bakala12, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
bakala12
Użytkownik
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.

Post autor: bakala12 »

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ć:
Skoro \(\displaystyle{ b^{a} \equiv 1 \pmod{m}}\) to jak podniesiesz tę kongruencje stronami do potęgi \(\displaystyle{ x}\) to dostaniesz to co oni.
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
Tak, dokładnie tak to działa.
huteusz
Użytkownik
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.

Post autor: huteusz »

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?
ODPOWIEDZ