  |
|
| ° Forum ° Rejestracja ° Szukaj ° | |
| Auto giełda ° wnętrzowe stacje transformatowe |
 |
Matma / liczby pierwsze |
| << . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 . |
| Autor | Wiadomość |
| Rafal Rusin
|
Posted: 5 Kwi 2001 09:59:58 potrzebuje pomocy w rozwiazaniu zadanka: udowodnic, ze istnieje niesk. wiele liczb pierwszych postaci: a) 4n+1 b) 4n+3 z gory dzieki za pomoc. demiurge |
| Posted: 6 Kwi 2001 07:51:52 -- potrzebuje pomocy w rozwiazaniu zadanka:
udowodnic, ze istnieje niesk. wiele liczb pierwszych postaci: a) 4n+1 b) 4n+3 z gory dzieki za pomoc. demiurge To nie sa/ "zadanka" -- jakze niesympatycznie brzmi dla mnie cwaniackie okreslenie "zadanka". To sa proste przypadki slynnego i wspanialego twierdzenia Dirichleta: gdy liczby naturalne a d sa wzglednie pierwsze (i tylko wtedy) nieskonczony postep arytmetyczny a a+d a+2*d ... zawiera nieskonczenie wiele liczb pierwszy. Najprostszy przypadek: a=b=1 udowodnil Euklides. Prosta i piekna metoda Euklidesa pozwala odowodnic nieco wiecej. Niech G(n) bedzie grupa multiplikatywna klas mod n, ktore sa multiplikatywnie odwracalne. Gdy p jest liczba pierwsza, to G(p) = Z/p {[0]} ma p-1 elementow. Ilosc elementow w G(n) to wartosc funkcji Eulera fi(n). Zadanie (dla zaawansowanych uczestnikow listy :-) Jezeli a b n (n1) sa liczbami naturalnymi takimi, ze [a*b] in G(n), to [a] [b] in G(n). Skorzystam z tej wlasnosci ponizej. ===================================================== Twierdzenie (uogolnienie tw. Euklidesa) Niech n 1 bedzie liczba naturalna. Niech A bedzie podgrupa grupy G(n), rozna od G(n). Wtedy istnieje nieskonczenie wiele liczb pierwszych q, takich, ze mod n mamy [q] in G(n) A. ====================================================== Dowod. Niech Q bedzie dowolnym, skonczonym zbiorem liczb pierwszych, ktore nie sa dzielnikami liczby n. Niech P := Prod(Q) bedzie produktem liczb z P. Uwaga: w wypadku zbioru pustego {} mamy: Prod({}) = 1. Niech b bedzie liczba naturalna taka, ze [b+1] nalezy do G(p) A. Istnieje wtedy liczba naturalna k taka, ze [k]*[P] = b Zatem [k*P + 1] = [b+1] nalezy do G(n)A. Zatem wsrod czynnikow pierwszych q liczby k*P + 1 co najmniej jeden jest taki, ze [q] nie nalezy A. Oczywiscie (patrz zadanie :-) [q] in G(n), a wiec [q] in G(n) A. Jasnym jest tez, ze q nie nalezy do Q. Wynika stad natychmiast, ze zaden skonczony zbior liczb pierwszych nie zawiera wszystkich liczb q takich, ze [q] in G(n) A. onnymi slowy, twierdzenie zachodzi, zbior liczb pierwszych q, dla ktorych [q] in G(n) A jest nieskonczony. --------- Dla n=4 A = ( {1} ) natychmiast dostajemy wniosek o nieskonczonosci zbioru liczb pierwszych wystepujacych w postepie 4*n - 1. Grupa G(n) ma dwa elementy tylko dla n = 3 4 6. Dlatego tez tylko dla tych n powyzsze twierdzenie daje czysty, mily wniosek o liczbach piewrwszych w opstepach arytmetyznych. Przy tym przypadki n=3 i n=6 sa w zasdzie tym samym, bowiem postepy arytmetyczne 3*n-1 i 6*n-1 maja dokladnie te same nieparzyste liczby pierwsze (dodatkowo 3*1-1 = 2). Grupy G(n) maja 4 elementy dla n = 5 8 10 12 (i na tym koniec). Otrzymujemy dla nich trzy twierdzenia (mniejsza o n=5 :-): istnieje nieskonczenie wiele liczb pierwszych postaci: (1) 8*n + r, gdzie r=3 lub -3; (2) 10*n + r, gdzie r=3 lub -3; (3) 12*n + r, gdzie r=5 lub -5. ---------- Przypadek postepu 4*n+1 jest nieco mniej elementarny. Korzystamy tym razem z twierdzenia Eulera (znanego juz Fermatowi), o tym, ze rownanie x^2 = -1 mod p nie ma rozwiazania dla zadnej liczby pierwszej p = -1 mod 4 (oraz zawsze ma, gdy p = 1 mod 4). Skorzystajmy. Niech Q bedzie dowolnym, skonczonym zbiorem liczb pierwszych. Niech P := Prod(Q). Wtedy dla dowolnego pierwszego dzielnika q liczby n := (2*P)^2 + 1 istnieje rozwiazanie rownania x^2 = -1 mod q, mianowicie x := n. Taki dzielnik q nie nalezy do Q, a przy tym q = 1 mod 4. Zatem zaden skonczony zbior Q liczb pierwszych nie zawiera wszystkich liczb pierwszych postaci 4*n+1; innymi slowy, zbior wszystkich liczb pierwszych postaci 4*n+1 jest nieskonczony. -------- Jak na zlosc nie widze w tej chwili, jak w podobny sposob pokazac, ze takze postep 6*n+1 zawiera nieskonczenie wiele liczb prostych. Moze (a moze kto inny :) pokaze/ w stylu Eulera-Dirichleta, ze kazdy z postepow 4*n-1 4*n+1 6*n-1 6*n+1 zawiera nieskonczenie wiele liczb pierwszych. Powyzej pokazalem to dla pierwszych trzech wymieniownych postepow , ale metoda Dirichleta daje wiecej, pokazuje, ze kazdy z nich ma asymptotycznie w pewnym sensie tyle samo liczb pierwszych. Zjawisko to zaznacza sie juz w zakresie istniejacych tablic. Pozdrawiam, Wlodek |
|
| Rafal Rusin
|
Posted: 6 Kwi 2001 10:27:09 [...] To nie sa/ "zadanka" -- jakze niesympatycznie brzmi dla mnie
cwaniackie okreslenie "zadanka". jak dla mnie, to jest to zadanko, dokladniej domowe z matematyki dyskretnej. nie mialem pojecia o tym, ze to jest na tyle skomplikowany problem, i w dodatku znany. w kazdym razie dziekuje za odpowiedz. pozdrawiam, demiurge |
| Crytcheck
|
Posted: 9 Kwi 2001 19:09:15 mam dwa pytanka: 1. powszechnie znane sa twierdzenia o podzielnosci liczby przez 2, 3 i 5. kiedys w jakiejs ksiazce widzialem takze o podzielnosci przez 7, 11 i chyba nawet 13 - moglibyscie mi je przypomniec? 2. czy jest jakis prosty sposob, aby sprawdzic, czy jakas duza liczba jest liczba pierwsza? |
| Eugeniusz Jakubas
|
Posted: 10 Kwi 2001 06:18:22 mam dwa pytanka:
1. powszechnie znane sa twierdzenia o podzielnosci liczby przez 2, 3 i 5. kiedys w jakiejs ksiazce widzialem takze o podzielnosci przez 7, 11 i chyba nawet 13 - moglibyscie mi je przypomniec?
2. czy jest jakis prosty sposob, aby sprawdzic, czy jakas duza liczba jest liczba pierwsza? Ad.1. O cechach podzielności zobacz na FAQ Marka Szyjewskiego. Ad.2. Wszystkie powszechnie znane sposoby są proste, chodzi Ci chyba o szybki sposób i takiego nie ma. Najszybciej sprawdza się liczby postaci 2^n-1. Pozdrawiam Eugeniusz J. |
| << . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10 . |