8. Teoria liczb, kombinatoryka

8.1. Sito Eratostenesa - III w. p.n.

Algorytm znajdywania wszystkich liczb pierwszych \(\leq n\)

• Tworzymy listę liczb naturalnych od \(1\) do \(n\)

• Dla liczb pierwszych \(p\leq \sqrt{n}\) wykreślamy wszystkie wielokrotności \(pm\leq n\)

• Liczby, które pozostały są pierwsze \(\leq n\)

8.2. Zadania na zajęcia

Ćwiczenie 8.5

Dane są liczby \(a=2002\) oraz \(b=1628 .\)

1. Na dwa sposoby (algorytm Euklidesa oraz postać kanoniczna liczby) obliczyć \(d=\)NWD\((a,b) .\)

2. Obliczyć NWW\((a,b) .\)

3. Znaleźć liczby \(p,q\in \zz\) takie, że \(d=pa+qb .\)

Ćwiczenie 8.6

Pewna grupa osób wita się, podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się więcej niż jeden raz. Stosując „zasadę szufladkową” pokazać, że w tej grupie muszą być co najmniej dwie osoby, które ściskały taką samą liczbę dłoni. Wyrazić ten rezultat w języku teorii grafów.

Ćwiczenie 8.7

Niech \(\{a_1,a_2,\ldots,a_{10}\}\subseteq \{1,2,\ldots,106\} .\) Pokazać, że istnieją dwa rozłączne podzbiory \(A,B\subset\{a_1,a_2,\ldots,a_{10}\}\) takie, że ich elementy dają taką samą sumę.

Ćwiczenie 8.8

W pewnej grupie jest \(10\) osób znających język angielski, \(15\) znających język francuski i \(12\) znających język rosyjski. Spośród nich \(5\) zna język angielski i francuski, \(4\) znają język francuski i rosyjski, \(3\) znają język angielski i rosyjski, a tylko \(2\) znają wszystkie te języki. Podać ile osób jest w tej grupie?

8.3. Zadania dodatkowe

Ćwiczenie 8.9

Stosując metodę sita Eratostenesa znaleźć wszystkie liczby pierwsze mniejsze niż \(100 .\)

Ćwiczenie 8.10

Niech \(m=p_1^{\alpha_1}\cdot \ldots \cdot p_n^{\alpha_n}\), gdzie \(p_1,\ldots,p_n\) są różnymi liczbami pierwszymi. Korzystając ze wzoru włączeń i wyłączeń pokazać, że

\[\varphi(m)=|Z_m^*|=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\ldots (1-\frac{1}{p_n}).\]

Obliczyć \(\varphi(1000) .\)

Informacja

Materiały na tej stronie przygotowała Agata Pilitowska.

Projekt „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.

Zadanie 7 pn. „Pilotażowa realizacja innowacyjnej ścieżki kształcenia obejmującej znaczny komponent zespołowych zajęć projektowych we wczesnej fazie studiów” realizowane w ramach projektu „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.