Podzielnośc
- mol_ksiazkowy
- Użytkownik
- Posty: 11265
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3143 razy
- Pomógł: 747 razy
Podzielnośc
Wykaz fakt: jeśli \(\displaystyle{ a}\) i \(\displaystyle{ m}\) są liczbami naturalnymi względnie pierwszymi, to istnieje wtedy taka liczba nuturalna \(\displaystyle{ n}\), że \(\displaystyle{ a^n-1}\) jest podzielna przez \(\displaystyle{ m}\)
- Tristan
- Użytkownik
- Posty: 2353
- Rejestracja: 24 kwie 2005, o 14:28
- Płeć: Mężczyzna
- Podziękował: 27 razy
- Pomógł: 557 razy
Podzielnośc
Wynika to wprost z tw.Eulera postaci:
Jeżeli liczby naturalne a i m są względnie pierwsze, to zachodzi podzielność \(\displaystyle{ m | a^{\phi(m)} -1}\).
Wynika z tego, że istnieje taka liczba n, ponieważ każda liczba postaci \(\displaystyle{ n=k \phi(m)}\), gdzie \(\displaystyle{ k \mathbb{N_{+}}}\)spełnia warunek zadania. Więcej o funkcji Eulera .
Jeżeli liczby naturalne a i m są względnie pierwsze, to zachodzi podzielność \(\displaystyle{ m | a^{\phi(m)} -1}\).
Wynika z tego, że istnieje taka liczba n, ponieważ każda liczba postaci \(\displaystyle{ n=k \phi(m)}\), gdzie \(\displaystyle{ k \mathbb{N_{+}}}\)spełnia warunek zadania. Więcej o funkcji Eulera .
Ostatnio zmieniony 7 wrz 2006, o 17:16 przez Tristan, łącznie zmieniany 1 raz.
- mol_ksiazkowy
- Użytkownik
- Posty: 11265
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3143 razy
- Pomógł: 747 razy
- juzef
- Użytkownik
- Posty: 890
- Rejestracja: 29 cze 2005, o 22:42
- Płeć: Mężczyzna
- Lokalizacja: Koszalin
- Pomógł: 66 razy
Podzielnośc
Nie wiem za bardzo czy o to Ci chodziło, ale to nie są wszystkie liczby n, które daną kongruencję spełniają.Tristan pisze:Wynika z tego, że istnieje taka liczba n i jest ona postaci \(\displaystyle{ n=k \cdot \phi(m)}\), gdzie \(\displaystyle{ k \in \mathbb{N_{+}}}\).
Mamy m różnych reszt z dzielenia przez m, więc spośród liczb \(\displaystyle{ a, a^2, a^3,..., a^{m+1}}\) można wybrać takie dwie, które dają tą samą resztę. Niech będą to \(\displaystyle{ a^k}\) oraz \(\displaystyle{ a^l}\), gdzie k>l.
\(\displaystyle{ a^k \equiv a^l od m\\ a^k-a^l \equiv 0 od m \\a^l(a^{k-l}-1) \equiv 0 od m}\).
Ale \(\displaystyle{ (a,m)=1}\), więc \(\displaystyle{ (a^l,m)=1}\). Zatem \(\displaystyle{ a^{k-l}\equiv 1 od m}\).