LICZBY WOKÓŁ NAS

dr Barbara Roszkowska-Lech

Streszczenie wykładu

Celem wykładu było zainteresowanie uczniów teorią liczb jako dziedziną mającą rozliczne intrygujące zastosowania, a z drugiej strony dziedziną w której mamy wiele otwartych problemów. W nauczaniu szkolnym uczniowie często mogą odnieść wrażenie, ze w matematyce wszystko zostało już dawno zrobione i nie ma tu otwartych, fascynujących problemów. Teoria liczb charakteryzuje się tym, że stosunkowo łatwo możemy sformułować w sposób zrozumiały dla ucznia takie otwarte problemy. W trakcie wykładu niektóre takie problemy zostały sformułowane.

Poprzez wieki pojęcie liczby rozwijało się stopniowo w związku z liczeniem i mierzeniem, fascynując i zadziwiając nie tylko matematyków.

Wykład rozpoczyna się od krótkich rozważań na temat filozoficznych poglądów szkoły pitagorejskiej ”liczby rządzą światem”. Pominięto ścisłą (aksjomatyczną) definicję liczby naturalnej opierając się na intuicji.

Podstawowy przykład liczb służących do opisu zjawisk przyrodniczych to liczby Fibonacciego. Na wykładzie omawiamy klasyczny przykład zastosowania tych liczb do idealistycznego modelowania populacji królików oraz kilka zastosowań przyrodniczych. Temat ten został w trakcie wykładu przedstawiony bardzo skrótowo. Niektóre własności liczb Fibonacciego proponuję uczniom w zadaniach.

Następnie przypomniane są znane z programu szkolnego: relacja podzielności w zbiorze liczb całkowitych oraz twierdzenie o dzieleniu z resztą. Twierdzenie o dzieleniu z resztą udowodnione jest graficznie na osi liczbowej.

Kolejny temat to liczby pierwsze i podstawowe twierdzenie arytmetyki o rozkładzie liczb całkowitych na iloczyn liczb pierwszych. Liczbom pierwszym, które porównać możemy do atomów z których zbudowane są cząsteczki poświęcona jest spora cześć wykładu. Mottem, części poświęconej liczbom pierwszym jest wiersz Helen Spalding (cytowany za Martin Gardner, Ostatnie Rozrywki, wyd. Prószyński
i s-ka). Omawiamy następujące zagadnienia związane z liczbami pierwszymi: nieskończoność zbioru liczb pierwszych, algorytmy badające czy liczba jest pierwsza, fascynujące zagadnienie rozmieszczenia liczb pierwszych na osi liczbowej.

Nieskończoność zbioru liczb pierwszych zostaje przywołana trzykrotnie: przedstawiamy klasyczny dowód Euklidesa, twierdzenie o rozbieżności szeregu odwrotności liczb pierwszych w kontekście nieskończonego sumowania oraz dowód oparty na wzajemnej pierwszości liczb Fermata.

Sporo czasu w czasie wykładu poświecono problemowi rozmieszczenia liczb pierwszych (twierdzenie Gaussa). Na wykładzie pokazano dowolnie długi ciąg kolejnych liczb złożonych.

Kolejnym omawianym zagadnieniem są liczby pierwsze w ciągach arytmetycznych. (twierdzenie Dirrichleta i twierdzenie Greena - Tao)

Omawiane są ciekawe ciągi liczb całkowitych (ciągi Mersenna i Fermata) w kontekście badania pierwszości i poszukiwania formuły na liczby pierwsze.

Na koniec formułujemy kilka otwartych problemów z teorii liczb.

Wykład zakończyło zastosowanie kryptograficzne dużych liczb pierwszych: elektroniczna koperta

Komentarze i uzupełnienia materiału z wykładu

1. Wątek liczb Fibonacciego warto rozwinąć w kontekście związków z przyrodą, fizyką, sztuką.... Więcej miejsca warto poświęcić złotej liczbie i różnym zastosowaniom ciągu Fibonacciego. Można uczniom zaproponować projekt związany z poszukiwaniem liczb Fibonacciego w przyrodzie i sztuce. W zadaniach dla uczniów można znaleźć zadania związane z tym tematem (http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/).

2. Warto zwrócić uwagę uczniów na to, że w twierdzeniu o dzieleniu z resztą możemy dopuścić ujemną resztę, ale wtedy iloraz i reszta nie są jednoznacznie wyznaczone. Takie przedstawienie reszty bywa jednak bardzo korzystne w zastosowaniach, szczególnie gdy mamy do czynienia z dużymi liczbami. Dla uproszczenia obliczeń warto mówić o reszcie najmniejszej co do wartości bezwzględnej.

3. Temat dotyczący podzielności można rozszerzyć omawiając cechy podzielności (zad 9 w materiałach dla ucznia). Relację podzielności warto rozwinąć na warsztatach mówiąc o największym wspólnym dzielniku NWD dwóch liczb naturalnych oraz o algorytmie Euklidesa znajdowania tego największego wspólnego podzielnika. Na wykładzie zabrakło na to czasu.

4. Na wykładzie, również z braku czasu, pominięto relację kongruencji. Warto ją zdefiniować i udowodnić własności. Ze względu na zastosowania kryptograficzne ważne jest Małe twierdzenie Fermata.

5. Zwracam uwagę na to, że Podstawowe Twierdzenie Arytmetyki o rozkładzie liczby na iloczyn liczb pierwszych nie mówi jak taki rozkład uzyskać. Problem rozkładu jest trudny. (Mnożenie jest łatwiejsze niż dzielnie) Zagadnienie trudności rozkładu na iloczyn liczb pierwszych trzeba podkreślić w kontekście zastosowań kryptograficznych.

6. Omawiając wzór redukcyjny
   xⁿ -yⁿ = (x-y)(x^n-1 +x^n-2y + …+xy^n-2 +y^n-1)
   warto zastosować go do udowodnienia, że jeśli liczba 2ⁿ -1 jest pierwsza to n musi być liczba pierwszą ( jeśli n=kl, to podstawiając w powyższym wzorze
   x= 2^k, y=1 a n =l otrzymujemy rozkład naszej liczby). Liczby postaci 2^p -1, to omawiane na wykładzie liczby Mersenna.

7. Proponuje zaproponować uczniom zabawę w szyfrowanie. Wcześniej trzeba wprowadzić kongruencje:
   a
   wtedy i tylko wtedy gdy n dzieli a-b.

Używamy alfabetu łacińskiego (26 liter). Każdej literze przyporządkowujemy liczbę {0,1, …25} i wszystkie rachunki wykonujemy modulo 26. Oczywiście możemy alfabet rozszerzyć o polskie litery i znaki przystankowe. Wiadomość szyfrowana M (element zbioru {0,1, …25}), funkcja szyfrująca E, funkcja deszyfrująca D. (Złożenie DE musi być identycznością).

Kryptosystem Cezara z kluczem k, 0 <k<26

szyfrowanie E(M) = M+ k (mod 26),

deszyfrowanie D(C) = C-k (mod 26)

Pytania: Załóżmy, że a, k
{0,1, …25}.

• Kiedy (przy powyższych założeniach) funkcja E(M) = aM (mod26) może być funkcją szyfrującą? Jak wygląda wtedy funkcja deszyfrująca?

• Kiedy E(M) = aM+k jest funkcją szyfrującą? Jak wygląda funkcja deszyfrująca.

Problem: Jak znaleźć funkcje deszyfrującą, czyli jak odwrócić a mod 26? Kiedy można i jak odwrócić a mod dowolna liczba n? Dla dowolnego n, rozwiązanie tego problemu prowadzi do uogólnionego algorytmu Euklidesa.

Podręcznik dla nauczyciela

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

3

Projekt współfinansowany z Europejskiego Funduszu Społecznego w ramach Programu Operacyjnego Kapitał Ludzki

---