Zadania z Teorii liczb - Algorytm Euklidesa, liczby pierwsze

1. Wyznaczy¢ NW D(a, b) i przedstawi¢ w postaci kombinacji liniowej a oraz b dla

(a) a = 1093, b = 123,

(b) a = 2451, b = −614,

(c) a = 148, b = 324.

2. Wyznaczy¢ NW W (a, b) dla

(a) a = 1093, b = 123,

(b) a = 2451, b = −614,

(c) a = 148, b = 324.

3. Pokaza¢, »e

(a) ka»da zªo»ona liczba trzycyfrowa ma dzielnik pierwszy p ≤ 31.

(b) istnieje 1000 kolejnych liczb zªo»onych.

(c) istnieje niesko«czenie wiele liczb naturalnych które nie s¡ ró»nic¡ dwóch liczb

pierwszych.

(d) je±li p ∈ P \ {2, 3}, to p

2

+ 2

jest liczb¡ zªo»on¡.

(e) je±li n ∈ N oraz 2

n

− 1

jest liczb¡ pierwsz¡, to n te» jest liczb¡ pierwsz¡.

(f) je±li p

n

oznacza n-t¡ liczb¦ pierwsz¡, to p

n

≤ 2

2

n−1

.

(g) je±li p ∈ P, to

√

p

jest liczb¡ niewymiern¡.

(h) je±li k ∈ N i 2

k

+ 1

jest pierwsza, to k = 2

t

dla pewnego t ∈ N.

(i) je±li p, q ∈ P \ {2, 3} to 24|p

2

− q

2

.

4. Wyznaczy¢

(a) wszystkie trójki liczb pierwszych postaci n, n + 2, n + 4.

(b) wszystkie pary bli¹niaczych liczb pierwszych mniejszych od 200.

(c) najmniejsz¡ liczb¦ naturaln¡, która nie jest ró»nic¡ dwóch liczb pierwszych.

(d) wszystkie liczby pierwsze, które s¡ jednoczesnie sumami i ró»nicami dwóch liczb

pierwszych

(e) najmniejsz¡ liczb¦ zªo»on¡ postaci n

2

+ n + 17

, gdzie n ∈ N.

5. Niech n ∈ N \ {1} ma nast¦puj¡c¡ wªasno±¢: je±li b i c s¡ liczbami caªkowitymi takimi, »e n|bc, to

n|b

lub n|c. Udowodni¢, »e n jest liczb¡ pierwsz¡.

6. Niech a, b ∈ N oraz a

2

+ b

2

> 1

. Je±li k jest liczb¡ nieparzyst¡ wi¦ksz¡ ni» 1, to a

k

+ b

k

nie jest

liczb¡ pierwsz¡.

7. Udowodni¢, »e je±li n ∈ N \ {1} nie ma dzielnika pierwszego p ≤

3

√

n

, to albo n jest liczb¡

pierwsz¡, albo n jest iloczynem dwóch liczb pierwszych.

8. Niech c = a

4

+ 4b

4

, a, b ∈ Z \ {0}. Pokaza¢, »e je±li a 6= ±1 lub b 6= ±1, to c jest liczb¡ zªo»on¡.