Elektronika AiR
Matematyka
Lista 5
Teoria liczb
Zad. 1. Stosując algorytm Euklidesa znaleźd największy wspólny dzielnik liczb NWD(29716, 8568).
Zad. 2. Zapisując liczby a, b w postaci kanonicznej (rozkładając na czynniki pierwsze) znaleźd ich
największy wspólny dzielnik NWD(a, b) oraz najmniejszą wspólną wielokrotnośd NWW(a, b)=[a, b] dla
a=18018, b=350.
Zad. 3. Znaleźd (a, b) oraz *a, b+ dla liczb a, b jak w zad. 2. wykorzystując algorytm Euklidesa i stosując
twierdzenie (a, b) · [a, b] = a · b.
Zad. 4. Wykorzystad cechy podzielności liczby naturalnej x przez liczby odpowiednio 7, 11, 13:
skreślamy trzy ostatnie cyfry liczby x. Od tak powstałej liczby odejmujemy liczbę powstałą z tych
trzech skreślonych cyfr. Liczba x jest podzielna przez 7, 11, 13 wtedy i tylko wtedy gdy powstała
różnica jest podzielna odpowiednio przez 7, 11, 13.
Zad. 5. Znajdź rozkład kanoniczny następujących liczb a) 443, b) 11849, c) 6967664, d) 61930099.
Zad. 6. Znaleźd najmniejszą liczbę naturalną n taką, że f(n) jest liczbą złożoną jeśli:
a) f(x) = x
2
+ x +17
n = 17
b) f(x) = x
2
+21x +1
n = 23
c) f(x) = 3x
2
+ 3x + 23
n = 23.
Zad. 7. Metryka taksówkowa (miejska) dla dowolnych punktów P(x, y, z), P’(x’, y’, z’) z przestrzeni
R
3
definiujemy ich odległośd wzorem: d(P, P’) = |x – x’| + |y – y’| + |z –z’|
Pokazad, że tak zdefiniowana odległośd spełnia trzy warunki wymagane od metryki.
Dla dowolnych
3
a)
d(P, P’) ≥ 0 i d(P, P’) = 0 wtedy i tylko wtedy gdy P = P’
b)
d(P, P’) = d(P’, P)
c)
d(P, P’) ≤ d(P, Q) + d(Q,, P’) (nierównośd trójkąta).
Zad. 8. Pokazad, że prosta k o równaniu parametrycznym
t
dowolne
nie przechodzi przez żaden punkt kratowy czyli należący do Z
3
gdzie Z – zbiór liczb całkowitych.
Znaleźd minimalną odległośd prostej k od zbioru Z
3
obliczaną w metryce taksówkowej. (odp. 1/5)
Zad. 9. Stosując sito Eratostenesa znaleźd wszystkie liczby pierwsze w przedziale (100, 200).