Podzielnośc

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

Post autor: mol_ksiazkowy »

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}\)
Awatar użytkownika
Tristan
Użytkownik
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

Post autor: Tristan »

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 .
Ostatnio zmieniony 7 wrz 2006, o 17:16 przez Tristan, łącznie zmieniany 1 raz.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
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

Post autor: mol_ksiazkowy »

ok, ale moznaby całkiem elementarnie to pokazać....?!
Awatar użytkownika
Tristan
Użytkownik
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

Post autor: Tristan »

Pewnie można... spójrz na dowód twierdzenia Eulera i spróbuj może z tego coś wykombinować.
Awatar użytkownika
juzef
Użytkownik
Użytkownik
Posty: 890
Rejestracja: 29 cze 2005, o 22:42
Płeć: Mężczyzna
Lokalizacja: Koszalin
Pomógł: 66 razy

Podzielnośc

Post autor: juzef »

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_{+}}}\).
Nie wiem za bardzo czy o to Ci chodziło, ale to nie są wszystkie liczby n, które daną kongruencję spełniają.

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}\).
Awatar użytkownika
Tristan
Użytkownik
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

Post autor: Tristan »

Juzef - rzeczywiście nieprecyzyjnie się wyraziłem i już poprawiam posta.
ODPOWIEDZ