Algebra liniowa z geometriÄ…
Ćwiczenia nr 3
Stefan Sokołowski
9 paz
dziernika 2007
Zadanie 1:
Załózmy, że w pewnym zabawkowym komputerze na liczbę calkowita przeznaczone sa
tylko 3 bity; tak więc liczba 23 = 8 jest już utożsamiana z zerem. Jaki będzie wydrukowany
przez ten komputer wynik następujących obliczeń?
1. 3 " 2 = ?
2. 3 " 3 " 3 " 3 = ?
3. (-4) " (-4) " (-4) " (-4) " (-4) = ?
Zadanie 2:
Uzasadnić następującą cechę podzielności przez 11:
Reszta z dzielenia liczby naturalnej m przez 11 jest taka sama jak reszta z
dzielenia naprzemiennej sumy cyfr liczby m przez 11.
To znaczy: jeśli rozpiszemy liczbę m na cyfry:
m = m0 + m1 · 10 + m2 · 102 + . . . + mp · 10p
(gdzie 0 mi < 10 dla wszystkich i), to
m mod 11 = (m0 - m1 + m2 - . . . + (-1)p · mp) mod 11
Zadanie 3:
Znalez
ć wszystkie liczby pierwsze mniejsze od 100 za pomocą sita Eratosthenesa. W
tym celu należy
1. wypisac wszystkie liczby naturalne od 2 do 99; niektóre z nich będziemy skreślać;
2. uznać pierwszą nieskreśloną liczbę za pierwszą a następnie skreślić jej wielokrotności;
to znaczy jesłi zaczęliśmy od liczby p, to skreślamy co p-tą liczbę;
3. powtarzać krok 2 aż dojdziemy do końca ciągu liczb.
Liczby nieskreślone są pierwsze.
Zadanie 4:
Kodowanie Gödla sÅ‚uży do zapisu ciÄ…gów (wektorów) liczb naturalnych w pojedyn-
czych liczbach naturalnych. Do jego wykonania musimy dysponować spisem kolejnych
liczb pierwszych:
p1 = 2 p2 = 3 p3 = 5 p4 = 7 . . .
Wektory koduje się przez podnoszenie liczb pierwszych do potęgi i mnożenie tych potęg
w następujący sposób:
1 2 n
(a1, a2, . . . , an) - p1a · p2a · . . . pna ·
Na przykład:
(2, 3, 0, 1) - 22 · 33 · 50 · 71 = 756
Jaki wektor koduje liczba 709632?
Zadanie 5:
Uproszczony algorytm Euklidesa do znajdywania największego wspólnego dzielnika
(oryginalny algorytm byl omawiany na wykładzie) opiera się na następujących własno-
ściach NWD:
" NWD(a, a) = a,
" jeśli a > b, to NWD(a, b) = NWD(a - b, b),
" jeśli a < b, to NWD(a, b) = NWD(a, b - a).
Obliczyć tą metodą NWD(828, 468).
2