Liczby pierwsze i podzielnosc

Matma / Liczby pierwsze i podzielnosc

Autor	Wiadomość
Pawel F. Gora	Posted: 21 Lut 2000 11:17:11 Mam taki oto problem: Niech n bezie liczbą naturalną n = 2 i niech k będzie liczbą pierwszą. Wykazać, że (1) n^k - n dzieli się bez reszty przez k Łatwo umiem to zrobić dla k = 2,3,5,7; dla wyższych, ale _konkretnych_ k, też się pewnie da rozpatrując poszczególne przypadki (wystarczy dla n=2,3,4,...,k-2), nie wiem jednak, jak zrobić to w przypadku ogólnym. Myślałem o indukcji ze względu na n. Krok indukcyjny n - (n+1) jest prosty, ale nie wiem jak dla dowolnej liczby pierwszej k wykazać, że (2) 2^k - 2 dzieli się bez reszty przez k Być może (1) lub (2) są dobrze znanymi faktami - jeśli tak, proszę o jakąs referencję. Być może - co by mnie szczerze zmartwiło - (1) i (2) w ogólności nie zachodzą (kontrprzykład?). Może to w ogóle jest typowe zadanie dla studentów - proszę mnie wówczas potraktować jak kiepskiego studenta i mi pomóc. (W moim przypadku to nie jest zadanie domowe :-) Paweł Góra Institute of Physics, Jagellonian University, Cracow, Poland A physical entity does not do what it does because it is what it is, but is what it is because it does what it does.
Pawel K	Posted: 21 Lut 2000 12:51:19 -----Wiadomość oryginalna----- Grupy dyskusyjne: pl.sci.matematyka Data: 21 lutego 2000 12:17 Temat: Liczby pierwsze i podzielnosc Mam taki oto problem: Niech n bezie liczbą naturalną n = 2 i niech k będzie liczbą pierwszą. Wykazać, że (1) n^k - n dzieli się bez reszty przez k (...) Zapiszemy badane wyrażenie w postaci n*(n^(k-1) - 1). Jeżeli k\|n to po kłopocie. Jeżeli nie, to korzystając z małego tw. Fermata jeżeli p-liczba pierwsza, zaś a - liczba naturalna niepodzielna przez p, to liczba a^(p-1) przy dzieleniu przez p daje resztę 1) wyrażenie w nawiasie jest podzielne przez k. I już. Pozdrawia Paweł Kwiatkowski
Pawel F. Gora	Posted: 21 Lut 2000 13:14:59 Zapiszemy badane wyrażenie w postaci n*(n^(k-1) - 1). Jeżeli k\|n to po kłopocie. Jeżeli nie, to korzystając z małego tw. Fermata jeżeli p-liczba pierwsza, zaś a - liczba naturalna niepodzielna przez p, to liczba a^(p-1) przy dzieleniu przez p daje resztę 1) wyrażenie w nawiasie jest podzielne przez k. I już. Miałem nadzieje, że dla matematyków to jest bardzo proste - i nie zawiodłem się. Dzięki! Paweł Góra Institute of Physics, Jagellonian University, Cracow, Poland A physical entity does not do what it does because it is what it is, but is what it is because it does what it does.
Wojciech Kluba	Posted: 22 Lut 2000 07:45:20 Mam taki oto problem: Niech n bedzie liczbą naturalną n = 2 i niech k będzie liczbą pierwszą. Wykazać, że (1) n^k - n dzieli się bez reszty przez k Mozna i tak (ksiazka H. Pawlowskiego): Malujemy kolo fortuny o k polach n roznymi kolorami. Chcemy obliczyc, ile jest roznych sposobow pokolorowania tego kola (zakladamy, ze pokolorowania powstale przez obrot kola sa identyczne). Otrzymujemy: (n^k - n)/k. Liczba sposobow jest liczba naturalna, czyli n^k-n dzieli sie przez k. Pozdrowienia Wojtek P.S. Ile bedzie sposobow, gdy k jest liczba zlozona?
jacek k2312	Posted: 22 Lut 2000 15:44:12 Mam taki oto problem: Niech n bezie liczbą naturalną n = 2 i niech k będzie liczbą pierwszą. Wykazać, że (1) n^k - n dzieli się bez reszty przez k Łatwo umiem to zrobić dla k = 2,3,5,7; dla wyższych, ale _konkretnych_ k, też się pewnie da rozpatrując poszczególne przypadki (wystarczy dla n=2,3,4,...,k-2), nie wiem jednak, jak zrobić to w przypadku ogólnym. Myślałem o indukcji ze względu na n. Krok indukcyjny n - (n+1) jest prosty, ale nie wiem jak dla dowolnej liczby pierwszej k wykazać, że Zadanie jest w istocie tzw. malym twierdzeniem Femata, które mozna stosunkowo prosto udowodnic indukcyjnie. Dla kazdej liczby naturalnej n i dla kazdej liczby pierwszej p: p dzieli n^p - n. Dla n = 1 mamy 1^p - 1 = 0 i p dzieli 0, bowiem zero jest wielokrotnoscia kazdej liczby calkowitej. Niech teraz wzór zachodzi dla pewnego n 1. (Zalozenie indukcyjne). Wtedy (n + 1)^p - (n + 1) = (n + 1)^p - n - 1 [teza indukcyjna] Ze wzoru dwumianowego Newtona mamy (n + 1)^p = suma(i=0..p; n^i * C(p,i)), gdzie C(p,i) jest wspólczynnikiem dwumiennym Newtona. Dalej, suma(i=0..p; n^i * C(p,i)) = 1 + suma(i=1..p-1; n^i * C(p,i)) + n^p [wylaczamy z sumy skladniki pierwszy i ostatni]. C(p,i)= p!/((p-i)!i!) Dla 0 < i < p liczba pierwsza p dzieli licznik [p!] ale nie dzieli mianownika [(p-i)!i!], bowiem jest wieksza zarówno od p-i jak i od i, a ponadto nie ma zadnych dzielników poza 1 i p (bo jest liczba pierwsza :-). Dlatego p dzieli C(p,i) dla 0 < i < p-1. Przepisujac teze indukcyjna mamy (n+1)^p - (n+1) = 1 + n^p + suma(i=1..p-1; n^i * C(p,i)) - n - 1 = = n^p - n + suma(i=1..p-1; n^i * C(p,i)) = A + B gdzie A = n^p - n i B = suma(i=1..p-1; n^i * C(p,i)). p dzieli A na podstawie zalozenia indukcyjnego. p dzieli B, bowiem B jest suma skladników, z których kazdy jest podzielny przez p. Dlatego p dzieli A + B i teza indukcyjna zostala udowodniona. Jacek K. Sent via Deja.com http://www.deja.com/ Before you buy.
jacek k2312	Posted: 22 Lut 2000 16:26:10 Zapiszemy badane wyrażenie w postaci n*(n^(k-1) - 1). Jeżeli k\|n to po kłopocie. Jeżeli nie, to korzystając z małego tw. Fermata jeżeli p-liczba pierwsza, zaś a - liczba naturalna niepodzielna przez p, to liczba a^(p-1) przy dzieleniu przez p daje resztę 1) wyrażenie w nawiasie jest podzielne przez k. I już. Fakt, iz p \| n^p - n dla kazdej liczby nanturalnej n i kazdej liczby pierwszej p, jest równowazny malemu twierdzeniu Fermata, zapisanemu zwyczajowo w postaci [ n^(p-1) = 1 (mod p), gdzie p - liczba pierwsza, n liczba naturalna taka, ze NWD(p,n) = 1 ]. Bowiem: Jesli prawdziwe jest tw. Fermata, to prawdziwa jest kongruencja n^(p-1) = 1 (mod p) dla NWD(n,p) = 1 i liczby pierwszej p. Mnozac strony tej kongruencji przez n otrzymujemy n^p = n (mod p) lub inaczej n^p - n = 0 (mod p), dla NWD(p,n) = 1. Ale ostatnia kongruencja jest tez prawdziwa, gdy p \| n. Zatem z definicji kongruencji mamy p \| n^p - n dla kazdego n naturalnego i dla kazdej liczby pierwszej p. Odwrotnie, jesli p jest liczba pierwsza i n - liczba naturalna oraz p \| n^p - n, to z definicji prawdziwa jest kongruencja p^n - n = 0 (mod p). Poniewaz jest ona prawdziwa dla dowolnych n naturalnych, to jest prawdziwa takze dla n takich, ze NWP(p,n) = 1. Mozemy zatem podzielic stronami ostatnia kongruencje przez n i otrzymujemy n^(p-1) - 1 = 0 (mod p) lub inaczej n^(p-1) = 1 (mod p), czyli male twierdzenie Fermata. Jacek K. Sent via Deja.com http://www.deja.com/ Before you buy.


° Forum ° Odpowiedz ° Rejestracja ° Szukaj °