---
title: "Kombinatoryka, teoria liczb"
lecture_number: 7
has_solutions: false
has_exercises: true
---

```{include} ../_includes/sagecell-loader.md
```

# Teoria liczb, kombinatoryka

## 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$

## Zadania na zajęcia

::::{exercise}
:class: [exercise]

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 .$

::::

::::{exercise}
:class: [exercise]

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.

::::

::::{exercise}
:class: [exercise]

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ę.

::::

::::{exercise}
:class: [exercise]

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?

::::

## Zadania dodatkowe

::::{exercise}
:class: [exercise]

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

::::

::::{exercise}
:class: [exercise]

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

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

Obliczyć $\varphi(1000) .$

::::

```{include} ../_includes/titlepage-info.md
```