Sito Eratosteresa

2,3,4,5,6….N

Usuwamy z naszego ciągu wszystkie liczby od p

1

= 2 i podzielne przez p

1

=2

Pierwszą nieusuniętą liczbą z naszego ciągu jest liczba p

2

= 3

Usuniemy z naszego ciągu liczby > p

2

= 3 będące wielokrotnościami 3.

Pierwszą nieusuniętą liczbą z naszego ciągu niepodzielną przez 2 i 3 jest teraz p

3

= 5. Mamy

teraz ciąg

2,3,5,7,11,13,17….

Postępowanie kontynuujemy i za n-tym razem otrzymujemy n-tą liczbę p

n

Usuniemy z naszego ciągu wszystkie wielokrotności liczby p

n

większe od p

n

Pierwszą nieusuniętą liczbą w naszym ciągu jest liczba pierwsza p

n + 1

Jeżeli ciąg jest skończony to postępowanie możemy zakończyć po otrzymaniu największej liczby
pierwszej p

k

≤ √. Wszystkie liczby większe od tej liczby p

k

pozostałe są liczbami pierwszymi.

równanie diofantyczne

– rozwiązań poszukujemy w liczbach całkowitych

4. Równania nieoznaczone

Twierdzenie 4.1

Niech a1,a2,..an oraz b ϵ ℤ, a12 + a22 + …an2 > 0

Na to by równanie a1x1 + a2x2 + anxn = b
miało rozwiązanie potrzeba i wystarcza by największy wspólny dzielnik a1 a2 … an dzielił b
czyli (a1,a2,…an)|b

Przykład 2x + 68y + 10z = 7
(2,68,10) = 2 , 2 ∤ 7

Twierdzenie 4.2

Jeśli (x0, y0) jest pewnym całkowitoliczbowym rozwiązaniem równanie

ax + by = c a,b,c ϵ ℤ

a2 + b2 > 0

wszystkie rozwiązania tego równania wyznaczymy wzorem

x = x

0

+

௕

(௔,௕)

∗

t ϵ ℤ

y = y

0

-

௕

(௔,௕)

∗

Przykłady:

20x + 502y = 3
(20,502) = 2

2 ∤ 3

czyli nie ma rozwiązań

28x + 15y = 2
(28,15) = 1
1 | 2
czyli rozwiązaniem jest

x = -1 +

ଵହ

(ଵହ,ଶ଼)

∗ x = -1 + 15t

t ϵ ℤ

y = 2 -

ଶ଼

(ଵହ,ଶ଼)

∗

y = 2 – 28t

5. Funkcje Eulera

Wartością jest ilość liczb pierwszych
φ (n) = { ilość liczb naturalnych ≤ n względnie pierwszych ≥ n }

Przykłady
φ (1) = 1 bo

(1,1) = 1

φ (2) = 1 bo

(1,2) = 1 (2,2) = 2 (2 nie jest względnie pierwsze)

φ (3) = 2 bo

(1,3) = 1 (2,3) = 1 (3,3) = 3

φ (4) = 2 bo

(1,4) = 1 (2,4) = 2 (3,4) = 1 (4,4) = 4

φ (5) = 4
φ (6) = 2
φ (12) = 4

Funkcja Eulena nie jest monotoniczna

Twierdzenie 5.1

Niech φ będzie funkcją Eulera φ(p) = p -1 gdzie p to zbiór liczb pierwszych

Funkcja π(x) x ∈ IN
π(x) = {ilość liczb pierwszych ≤ x}

π(1) = 0

π(4) = 2

π(2) = 1

π(5) = 3

π(3) = 2

π(7) = π(8) = π(9) = π(10) = 4

6. Kongruencja

3 = 20 (mod 17)
20 = 12 (mod 8)
100 = 80 (mod 4)

Definicja : o dwóch liczbach całkowitych a,b mówimy że przystają do siebie modulo m, m ∈IN,
jeśli m | a-b czyli

Twierdzenie 6.1

a,b,c,d ∈ Z, m ∈ IN

1

2

3

4

5

6

7

8

9

10