Algebra liniowa z geometrią

Ćwiczenia nr 3

Stefan Sokołowski

9 października 2007

Zadanie 1:

Załózmy, że w pewnym zabawkowym komputerze na liczbę calkowita przeznaczone sa

tylko 3 bity; tak więc liczba 2

3

= 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

= m

0

+ m

1

·

10 + m

2

·

10

2

+ . . . + m

p

·

10

p

(gdzie 0 ¬ m

i

<

10 dla wszystkich i), to

m

mod 11 = (m

0

−

m

1

+ m

2

−

. . .

+ (−1)

p

·

m

p

) mod 11

Zadanie 3:

Znaleźć 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¨odla 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:

p

1

= 2 p

2

= 3 p

3

= 5 p

4

= 7

. . .

Wektory koduje się przez podnoszenie liczb pierwszych do potęgi i mnożenie tych potęg
w następujący sposób:

(a

1

, a

2

, . . . , a

n

)

7−→

p

1

a

1

·

p

2

a

2

·

. . . p

n

a

n

·

Na przykład:

(2, 3, 0, 1)

7−→

2

2

·

3

3

·

5

0

·

7

1

= 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