Teoria liczb 2010, sem.IV,

B.Bajorska, O.Macedo«ska

Wykªad 6.

Podstawowe Twierdzenie Arytmetyki

1 Podstawowe Twierdzenie Arytmetyki i jego

implikacje

Wyka»emy najpierw kilka pomocniczych faktów.

Lemat 1. Niech p b¦dzie liczb¡ pierwsz¡ i niech a, b b¦d¡ liczbami caªkowi-

tymi. Je±li p|ab, to p|a lub p|b.

Dowód. Niech p|ab. Je±li p - a, to poniewa» p jest liczb¡ pierwsz¡, to
NW D(a, p) = 1

, wi¦c z Lematu Euklidesa (Wykªad 3, Lem.2) mamy wtedy

p|b

. Zatem p|a lub p|b.

Lemat 2. Niech p b¦dzie liczb¡ pierwsz¡, n liczba naturaln¡ oraz niech a

1

, a

2

,

..., a

n

b¦d¡ liczbami caªkowitymi. Je±li p|a

1

a

2

· · · a

n

, to p|a

k

dla pewnego k

takiego, »e 1 ≤ k ≤ n.

Dowód. Przeprowadzimy dowód indukcyjnie ze wzgl¦du na n. Dla n = 1

stwierdzenie jest oczywiste, dla n = 2 wynika z Lematu 1. Zaªó»my, »e

dla n − 1 czynników stwierdzenie jest prawdziwe i niech p|a

1

a

2

...a

n

. Wtedy

z Lematu 1 wynika, »e p|a

n

lub p|a

1

a

2

...a

n−1

. Je±li p|a

n

to k := n, je±li

p - a

n

to z zaªo»enia indukcyjnego wynika, »e p|a

k

dla pewnego k takiego,

»e 1 ≤ k ≤ n − 1. Ostatecznie p|a

k

dla pewnego k takiego, »e 1 ≤ k ≤ n.

Wobec tego zgodnie z Zasad¡ indukcji (Wykªad 1, Tw.3) stwierdzenie jest

prawdziwe dla ka»dego naturalnego n.

Wniosek 1. Je±li liczby p, q

1

, ..., q

n

s¡ pierwsze oraz p|q

1

q

2

· · · q

n

, to p = q

k

dla pewnego k takiego, »e 1 ≤ k ≤ n.

Dowód. Z Lematu 2 wynika, »e istnieje takie k, »e p|q

k

. Poniewa» obie

liczby s¡ pierwsze, to mamy p = q

k

.

Twierdzenie 1 (Podstawowe Twierdzenie Arytmetyki). Ka»da liczba zªo-

»ona mo»e by¢ przedstawiona jako iloczyn liczb pierwszych. Przedstawienie

takie jest jednoznaczne z dokªadno±ci¡ do kolejno±ci czynników.

Dowód. (Cz¦±¢ 1: Istnienie przedstawienia) Zaªó»my nie wprost, ze istnieje

pewna liczba zªo»ona n, której nie mo»na przedstawi¢ w postaci iloczynu

liczb pierwszych. Niech teraz S b¦dzie zbiorem wszystkich liczb zªo»onych

które nie s¡ iloczynami liczb pierwszych. Wtedy S jest niepusty, bo n ∈ S.

Wobec Zasady minimum (Wykªad 1, Tw.1) istnieje w S liczba najmniejsza,

powiedzmy n

0

. Zatem istniej¡ liczby caªkowite a, b takie, »e n

0

= ab

oraz

1 < a ≤ b < n

0

(Wykªad 5, Wn.1). Ponadto, liczby a, b nie mog¡ by¢

pierwsze (bo n

0

nie jest iloczynem liczb pierwszych) ani te» nie mog¡ nale»e¢

1

do S (bo n

0

jest najmniejsza liczb¡ w S). Zatem a, b mog¡ by¢ przedstawione

w postaci iloczynów liczb pierwszych, powiedzmy a = p

1

· · · p

k

, b = q

1

· · · q

m

.

St¡d n

0

= p

1

· · · p

k

q

1

· · · q

m

, a wi¦c jest iloczynem liczb pierwszych, co przeczy

przynale»no±ci n

0

do S. Pokazali±my tym samym, »e ka»d¡ liczb¦ zªo»on¡

mo»na przedstawi¢ w postaci iloczynu liczb pierwszych.

(Cz¦±¢ 2: Jednoznaczno±¢ przedstawienia). Zaªó»my, »e istnieje liczba

zªo»ona n posiadaj¡ca dwa przedstawienia w postaci iloczynu liczb pierw-

szych, powiedzmy n = p

1

p

2

· · · p

r

= q

1

q

2

· · · q

s

. Zaªó»my nast¦puj¡c¡ kolej-

no±¢ czynników: p

1

≤ p

2

≤ ... ≤ p

r

oraz q

1

≤ q

2

≤ ... ≤ q

s

.

Bez straty

ogólno±ci mo»emy równie» zaªo»y¢, »e r ≤ s. Poniewa» p

1

|q

1

. . . q

s

, to na

podstawie Wniosku 1 istnieje k takie, »e p

1

= q

k

. Poniewa» q

k

≥ q

1

, to

p

1

≥ q

1

. Analogicznie, z faktu, »e q

1

|p

1

p

2

· · · p

r

otrzymujemy, »e q

1

≥ p

1

, co

oznacza, »e p

1

= q

1

, a st¡d wynika, »e wyj±ciowa równo±¢ ma po skróceniu

posta¢ p

2

· · · p

r

= q

2

· · · q

s

. Powtarzaj¡c powy»sze rozumowanie dla kolejnych

i = 2, ..., r

otrzymujemy, »e p

2

= q

2

, ..., p

r

= q

r

.

Gdyby r < s, to p

1

· · · p

r

= q

1

· · · q

r

q

r+1

· · · q

s

= p

1

· · · p

r

q

r+1

· · · q

s

, a wi¦c

mieliby±my q

r+1

· · · q

s

= 1

, co jest niemo»liwe, bo wszystkie liczby q

i

s¡ pierw-

sze. Tak wi¦c r = s oraz p

i

= q

i

dla 1 ≤ i ≤ r. Oznacza to, »e przedstawienie

jest tylko jedno z dokªadno±ci¡ do kolejno±ci czynników, co ko«czy dowód

jednoznaczno±ci i twierdzenia.

Uwaga Dowód istnienia rozkªadu mo»na te» przeprowadzi¢ wprost. Mia-

nowicie, je±li n jest liczb¡ zªo»on¡, to z denicji zbiór naturalnych dzielników

liczby n wi¦kszych ni» 1 (i mniejszych ni» n) jest niepusty. Z Zasady mini-

mum (Wykªad 1, Tw.1) istnieje w tym zbiorze liczba najmniejsza, powiedzmy
p

1

. Gdyby p

1

byªa zªo»ona, to istniaªby dzielnik q liczby p

1

, który byªby rów-

nie» dzielnikiem liczby n, co przeczyªoby wyborowi p

1

. Zatem liczba p

1

jest

pierwsza i mamy n = p

1

n

1

,

gdzie 1 < n

1

< n

. Je±li n

1

jest pierwsza, to otrzy-

mali±my »¡dany rozkªad liczby n, a je±li nie, to powtarzamy rozumowanie dla
n

1

, otrzymuj¡c n = p

1

p

2

n

2

, gdzie 1 < n

2

< n

1

. Poniewa» (n

i

)

i∈N

jest male-

j¡cym ci¡giem liczb naturalnych, to jest on sko«czony, czyli istnieje w tym

ci¡gu liczba najmniejsza, powiedzmy n

k

. Liczba n

k

musi by¢ pierwsza, bo

w przeciwnym razie mogliby±my powtórzy¢ jeszcze raz rozumowanie otrzy-

muj¡c 1 < n

k+1

< n

k

, co przeczy denicji n

k

. Mamy wi¦c n = p

1

· · · p

k

n

k

,

czyli »¡dany zapis liczby n w postaci iloczynu liczb pierwszych.

Z powy»szego Twierdzenia otrzymujemy natychmiast

Wniosek 2. Ka»da liczba naturalna n wi¦ksza ni» 1 mo»e by¢ zapisana jed-

noznacznie w tzw. postaci kanonicznej:

n = p

α

1

1

p

α

2

2

· · · p

α

r

r

,

gdzie p

i

∈ P, α

i

∈ N,

p

1

< p

2

< . . . < p

r

. 2

Uwaga Posta¢ kanoniczn¡ liczby n mo»na równie» zapisa¢ nast¦puj¡co:

n =

Y

p

i

∈P

p

α

i

i

,

2

gdzie α

i

= 0

dla prawie wszystkich i, a P jest uporz¡dkowanym (rosn¡co)

zbiorem wszystkich liczb pierwszych.

Korzystaj¡c z postaci kanonicznej udowodnimy dwa twierdzenia doty-

cz¡ce liczb pierwszych. Poka»emy najpierw

Lemat 3. Dla ka»dego naturalnego k wi¦kszego ni» 2 zachodzi nierówno±¢
k < 2

k−1

.

Dowód. Indukcyjnie ze wzgl¦du na k. Dla k = 3 mamy 3 < 2

2

. Dalej,

zaªó»my, »e k − 1 < 2

k−2

. Wtedy k < 2

k−2

+ 1 < 2

k−2

+ 2

k−2

= 2

k−1

. Wobec

tego zgodnie z Zasad¡ indukcji (Wykªad 1, Tw.3) wzór jest prawdziwy dla

ka»dego k wi¦kszego ni» 2.

Twierdzenie 2. Liczba naturalna n wi¦ksza ni» 4 jest pierwsza wtedy i tylko

wtedy gdy n - (n − 1)!.

Dowód. Je±li n jest liczb¡ pierwsz¡, to nie dzieli »adnej z liczb 1, 2, ..., n−1,

wi¦c na podstawie Lematu 2 nie dzieli tak»e ich iloczynu, czyli n - (n − 1)!

Drug¡ implikacj¦ poka»emy korzystaj¡c z prawa kontrapozycji, tzn. udo-

wodnimy, »e je±li n jest zªo»ona, to n|(n − 1)!. Z Wniosku 3 wynika, »e n ma

posta¢ kanoniczn¡, powiedzmy n = p

k

1

1

p

k

2

2

· · · p

k

s

s

.

Zauwa»my najpierw, »e poniewa» p

i

s¡ ró»ne, to p

k

i

i

te» s¡ ró»ne. Rze-

czywi±cie, gdyby dla pewnych liczb pierwszych p, q oraz pewnych liczb natu-

ralnych k, l zachodziªa równo±¢ p

k

= q

l

, to oznaczaªoby w szczególno±ci, »e

p|q

l

, czyli z Wniosku 1 p = q, co jest niemo»liwe.

(1).

Je±li s > 1, czyli w postaci kanonicznej n wyst¦puj¡ co najmniej dwie

liczby pierwsze, to liczby p

k

i

i

s¡ ró»ne i mniejsze ni» n, a st¡d ich iloczyn

dzieli (n − 1)!, czyli n|(n − 1)!.

(2).

Niech n = p

2

. Poniewa» n > 4, to p nie mo»e by¢ równe 2, wi¦c mamy

p < 2p < p

2

= n

. Wi¦c p i 2p s¡ ró»ne i nie wi¦ksze od n − 1. St¡d ich

iloczyn dzieli (n − 1)!, a wi¦c n|(n − 1)!.

(3).

Je±li n = p

k

dla k > 2, to z Lematu 3 wynika k < 2

k−1

≤ p

k−1

, a wi¦c

p < 2p < ... < kp < p

k−1

p = p

k

= n,

p < 2p < ... < kp ≤ n − 1.

Zatem liczby p, 2p, ..., kp s¡ ró»nymi czynnikami w (n − 1)!, wi¦c ich iloczyn
k!p

k

dzieli (n − 1)!. St¡d mamy, »e p

k

|(n − 1)!

, czyli n|(n − 1)!.

Uwaga Powy»sze twierdzenie jest prawdziwe równie» dla n = 2 i n = 3,

ale nie dla n = 4.

Twierdzenie 3. Istnieje niesko«czenie wiele liczb pierwszych postaci 4k −1.

3

Dowód. Zauwa»my najpierw, »e
ka»da liczba nieparzysta jest postaci 4k + 1 lub 4k − 1,
iloczyn liczb pierwszych postaci 4k + 1 jest te» liczb¡ postaci 4k + 1,

bo
je±li p

1

= 4s

1

+ 1, p

2

= 4s

2

+ 1

, to wtedy p

1

p

2

= 4(4s

1

s

2

+ s

1

+ s

2

) + 1

.

Indukcyjnie wynika z tego, »e iloczyn dowolnej sko«czonej ilo±ci liczb postaci
4k + 1

jest liczb¡ postaci 4k + 1.

Aby udowodni¢ Twierdzenie, zaªo»my nie wprost, »e Q = {q

1

, q

2

, ..., q

r

}

jest zbiorem wszystkich liczb pierwszych postaci 4k − 1 i niech

m := 4q

1

q

2

· · · q

r

− 1.

Liczba m jest liczb¡ nieparzyst¡, a wi¦c wszystkie dzielniki pierwsze liczby
m

s¡ nieparzyste, oraz przynajmniej jeden ma by¢ postaci q = 4k − 1, a wi¦c

nale»e¢ do Q. Zatem z Wªasno±ci 8 (Wykªad 2, Tw.1) q|4q

1

q

2

· · · q

r

− m

czyli

q|1

, a st¡d q = 1, co daje sprzeczno±¢ z zaªo»eniem, »e q jest liczb¡ pierwsz¡.

Wobec tego liczb pierwszych postaci 4k − 1 jest niesko«czenie wiele.

2 Elementarna metoda szukania postaci kano-

nicznej

1. Opis algorytmu: Niech n b¦dzie liczb¡, dla której szukamy rozkªadu.

Je±li 2 - n, to znaczy, »e w postaci kanonicznej liczby n nie ma czynnika

b¦d¡cego pot¦g¡ 2. Je±li 2|n, to sprawdzamy czy 2

2

| n

. Kontynuujemy

do momentu w którym 2

k

1

| n

i 2

k

1

+1

- n

. Wtedy 2

k

1

jest najwi¦ksz¡

pot¦g¡ 2 dziel¡c¡ n, zatem jest pierwszym czynnikiem w postaci ka-

nonicznej. Rozpatrujemy wtedy kolejn¡ liczb¦ pierwsz¡ i powtarzamy

powy»sz¡ procedur¦.
Je±li p

k

1

1

jest pierwszym czynnikiem w postaci kanonicznej liczby n oraz

n = p

k

1

1

, to mamy »¡dan¡ posta¢. Je±li nie, to deniujemy n

1

:=

n

p

k1

1

i powtarzamy powy»sze rozumowanie znajduj¡c najmniejszy dzielnik

pierwszy p

2

liczby n

1

, a nast¦pnie tak¡ pot¦g¦ k

2

, »e p

k

2

2

| n

1

oraz

p

k

2

+1

2

- n

1

. Je±li n

1

= p

k

2

2

, to postaci¡ kanoniczn¡ jest n = p

k

1

1

p

k

2

2

.

Je±li nie, to deniujemy n

2

:=

n

1

p

k2

2

=

n

p

k1

1

p

k2

2

i ponownie powtarzamy ob-

liczenia szukaj¡c najmniejszego dzielnika p

3

dziel¡cego liczb¦ n

2

. Pow-

tarzamy rozumowanie do momentu, w którym dla pewnego s mamy
n

s−1

= p

k

s

. Wówczas n = p

k

1

1

p

k

2

2

· · · p

k

s

s

i jest to szukana posta¢ kano-

niczna liczby n.

2. Poprawno±¢ procedury: Zauwa»my najpierw, »e algorytm zawsze si¦

ko«czy. Rzeczywi±cie, po pierwsze ci¡g n > n

1

> n

2

> ...

jest sko«czo-

ny, po drugie ka»da liczba zªo»ona z na dzielnik pierwszy mniejszy ni»

√

z

(Wykªad 5, Lem.2), zatem w celu znalezienia zgodnie z algorytmem

ka»dej kolejnej liczby n

i

trzeba wykona¢ sko«czon¡ operacji. Ponadto,

ze sformuªowania algorytmu wida¢, »e daje on »¡dany wynik.

4

3. Przykªad: Znale¹¢ posta¢ kanoniczn¡ liczby 84.

Mamy n := 84.
Dla 2 mamy n = 84 = 2 · 42 = 2 · 2 · 21 oraz 2 - 21. St¡d p

1

= 2

i

pierwszym czynnikiem jest 2

2

oraz n

1

:= 21

.

Dla 3 mamy n

1

= 21 = 3 · 7

oraz 3 - 7. St¡d p

2

= 3

i drugim czynnikiem

jest 3

1

oraz n

2

:= 7

.

Dla 5 mamy 5 - n

2

.

St¡d w rozkªadzie n nie ma czynnika b¦d¡cego

pot¦g¡ 5.
Dla 7 mamy n

2

= 7 = 7

1

, czyli proces si¦ zako«czyª i otrzymujemy

84 = 2

2

· 3

1

· 7

1

.

Uwaga Powy»szy przykªad zostaª zapisany zgodnie z algorytmem.

W zapisie postaci kanonicznej mo»na opu±ci¢ wszystkie pot¦gi równe 1

i oczywi±cie, je±li zorientujemy si¦ wcze±niej, jaki jest kolejny dzielnik

pierwszy i/lub która jego pot¦ga jest t¡ szukan¡, to mo»emy procedur¦

skróci¢. Wtedy przykªad wygl¡daªby tak:
Mamy n := 84.
Dla 2 mamy n = 84 = 2 · 42 = 2 · 2 · 21 oraz 2 - 21. St¡d pierwszym

czynnikiem jest 2

2

oraz n

1

:= 21

.

Dla 3 mamy n

1

= 21 = 3·7

. St¡d drugim czynnikiem jest 3, a ostatnim

7

i otrzymujemy 84 = 2

2

· 3

1

· 7

1

.

3 Algorytm Fermata

1. Algorytm Fermata

1

sªu»y do znalezienia zapisu nieparzystej liczby

naturalnej n, nie b¦d¡cej kwadratem »adnej liczby caªkowitej, w postaci
n = ab

, gdzie 1 < a < b < n lub stwierdzenia, »e n jest liczb¡ pierwsz¡.

2. Idea algorytmu Jesli n = ab, 1 < a < b < n i obie liczby s¡

nieparzyste, to liczby a ± b sa parzyste, oraz n = (

a+b

2

)

2

− (

a−b

2

)

2

, czyli

n

jest ró»nica dwóch kwadrtów. Jesli znajdziemy takie przedstawienie

dla n to znajdziemy a i b.

3. Opis algorytmu: Dla liczby n deniujemy k

1

:= d

√

ne

(gdzie dxe

oznacza najbli»sz¡ x-owi liczb¦ naturaln¡ wi¦ksz¡ od x). Sprawdzamy,

czy istnieje takie m

1

∈ N

, »e k

2

1

− n = m

2

1

. Je±li tak, to szukanym

zapisem jest n = k

2

1

−m

2

1

= (k

1

+m

1

)(k

1

−m

1

).

Je±li nie, to powtarzamy

powy»sz¡ procedur¦ dla kolejnej liczby naturalnej, tzn. k

2

:= k

1

+ 1

szukaj¡c m

2

. Algorytm si¦ ko«czy albo je±li dla pewnego i istniej¡ takie

m

i

, k

i

, »e k

2

i

− n = m

2

i

albo je±li dla »adnej liczby k

i

< n

taka liczba m

i

nie istnieje. W tym pierwszym przypadku szukanym przedstawieniem

1

Pierre de Fermat 1601-1665

5

jest n = (k

i

+ m

i

)(k

i

− m

i

)

. W drugim przypadku wnioskujemy, »e n

jest liczb¡ pierwsz¡.
Ze sformuªowania algorytmu wynika, »e jest on najbardziej efektywny

wtedy, kiedy ró»nica mi¦dzy czynnikami w rozkªadzie liczby n jest sto-

sunkowo niewielka.

4. Poprawno±¢ procedury Je±li n liczb¡ zªo»on¡, to n = ab, gdzie

1 < a ≤ b < n

(Wykªad 5, Wn.1). Poniewa» n jest niekwadratowa,

to a 6= b. Ponadto, skoro n jest nieparzysta, to a, b s¡ nieparzyste, wo-

bec tego 2|(a ± b). Ponadto n = (

a+b

2

)

2

− (

a−b

2

)

2

, przy czym obie liczby

k :=

a+b

2

, m :=

a−b

2

s¡ naturalne, zatem algorytm daje poprawny wy-

nik. Poniewa» k

2

> n

, to k >

√

n

, a wi¦c k ≥ d

√

ne

. Z drugiej strony

k =

a+b

2

< b < n

. Zatem algorytm b¦dzie miaª mniej ni»

√

n

kroków, a

wi¦c zawsze si¦ sko«czy.

5. Przykªad Przedstawi¢ liczb¦ n = 27 308 533 w postaci nietrywialnego

iloczynu dwóch liczb naturalnych.
Obliczamy:

k

1

= d≈ 5 225, 7e = 5 226 =⇒ k

2

1

− n = 2 543 ≈ (50, 4)

2

/

∈ N

2

=⇒

k

2

= 5 227 =⇒ k

2

2

− n = 12 966 = (114)

2

=⇒ m

2

= 114

St¡d 27 308 533 = (5 227 + 114)(5 227 − 114) = 5 341 · 5 113.

Uwaga W celu znalezienia postaci kanonicznej mo»na poª¡czy¢ algorytm

Fermata (zastosowany kilkukrotnie w razie potrzeby) z elementarnym algo-

rytmem opisanym w Rozdziale 2.

4 Funkcja Eulera

Denicja 1. Dla ka»dej liczby naturalnej n wi¦kszej ni» 1 okre±lamy liczb¦
ϕ(n)

jako ilo±¢ liczb naturalnych mniejszych od n i wzgl¦dnie pierwszych z n.

Funkcj¦ ϕ = ϕ(n) nazywamy funkcj¡ Eulera

2

.

Lemat 4. Dla dowolnej liczby pierwszej p oraz dowolnej liczby naturalnej k
zachodzi równo±¢ ϕ(p

k

) = p

k

³

p−1

p

´

.

Dowód. Poniewa» p jest liczb¡ pierwsz¡, to liczby naturalne mniejsze od p

k

,

które nie s¡ wzgl¦dnie pierwsze z p, to liczby podzielne przez p. Mo»emy je

zapisa¢ w postaci l · p, gdzie 1 ≤ l ≤ p

k−1

. Poniewa» jest dokªadnie p

k−1

takich liczb, wi¦c liczb wzgl¦dnie pierwszych z p

k

i mniejszych od p

k

jest

p

k

− p

k−1

. St¡d

ϕ(p

k

) = p

k

− p

k−1

= p

k

µ

p − 1

p

¶

.

2

Leonhard Euler 1707-1783

6

Poni»sze twierdzenie mo»na udowodni¢ elementarnie, podobnie jak po-

wy»szy Lemat, jednak taki dowód byªby zbyt pracochªony. Zgrabny dowód

zostanie podany na jednym z pó¹niejszych wykªadów.

Twierdzenie 4. Niech n ∈ N \ {1} i niech p

k

1

1

p

k

2

2

· · · p

k

s

s

b¦dzie postaci¡

kanoniczn¡ liczby n. Wtedy

ϕ(n) = n

s

Y

i=1

µ

p

i

− 1

p

i

¶

5 Niektóre problemy otwarte zwi¡zane z P

Problem 1 (Hipoteza Goldbacha

3

). Ka»da liczba parzysta wi¦ksza od 2 jest

sum¡ dwóch liczb pierwszych.

Uwaga Znane jest tylko cz¦±ciowe rozwi¡zanie tego problemu: w 1937

Winogradow

4

udowodniª, »e zbiór liczb parzystych nie speªniaj¡cych hipotezy

Goldbacha ma g¦sto±¢ 0, to znaczy lim

n→∞

A(n)

n

= 0

, gdzie A(n) oznacza ilo±¢

liczb parzystych mniejszych od n, które nie speªniaj¡ hipotezy Goldbacha,

czyli takich, które nie s¡ sum¡ dwóch liczb pierwszych.

Problem 2. Czy istnieje niesko«czenie wiele liczb pierwszych Mersenne'a

5

?

Uwaga Liczb¡ Mersenne'a nazywamy liczb¦ postaci M

p

= 2

p

− 1

, gdzie

p ∈ P

. Nie wszystkie liczby Mersenne'a s¡ pierwsze, jak np. M

11

. Do tej

pory znaleziono 46 liczb pierwszych Mersenne'a. Przedostatnia z nich jest

najwi¦ksz¡ obecnie znan¡ liczb¡ pierwsz¡.

Problem 3. Czy istnieje niesko«czenie wiele liczb pierwszych Fermata?

Uwaga Liczb¡ Fermata nazywamy liczb¦ postaci F

n

= 2

2

n

+ 1

, gdzie

n ∈ N

. Nie wszystkie liczby Fermata s¡ pierwsze, jak np. F

5

.

Problem 4. Czy istnieje niesko«czenie wiele liczb Sophie Germain

6

?

Uwaga Liczb¡ Sophie Germain nazywamy liczb¦ pierwsz¡ p pod warun-

kiem, »e 2p + 1 te» jest liczb¡ pierwsz¡.

Problem 5. Czy istnieje funkcja f = f(x), której warto±ciami s¡ wyª¡cznie

liczby pierwsze?

Uwaga Wiadomo, »e nie mo»e to by¢ funkcja wielomianowa.

Problem 6. Czy istnieje niesko«czenie wiele liczb pierwszych bli¹niaczych?

3

Christian Goldbach 1690-1764

4

Iwan Matwiejewicz Winogradow 1891-1983

5

Marin Mersenne 1588-1648

6

Marie-Sophie Germain 1776-1831

7

Uwaga Liczbami bli¹niaczymi nazywamy par¦ liczb pierwszych postaci

p, p + 2

.

Problem 7. Czy istnieje niesko«czenie wiele liczb pseudopierwszych Fermata

przy danej podstawie a?

Uwaga Liczb¡ pseudopierwsz¡ Fermata przy podstawie a ∈ N nazywamy

ka»d¡ liczb¦ zªo»on¡ n tak¡, »e n|a

n

− a

.

Problem 8. Czy istnieje niesko«czenie wiele liczb Carmichaela

7

?

Uwaga Liczb¡ Carmichaela nazywamy ka»d¡ liczb¦ zªo»on¡ n, która jest

liczb¡ pseudopierwsz¡ Fermata przy ka»dej podstawie a wzgl¦dnie pierwszej

z n.

7

Robert Daniel Carmichael 1879-1967

8