5027720042

Matematyka - Teoria liczb z elementami kryptografii Lista 1 -Algorytm Euklidesa i ułamki łańcuchowe

1.    Znajdź największy wspólny dzielnik i najmniejszą wspólną wielokrotność liczb: a) 2711, 451; b) 121121, 1002.

2.    Korzystając z odwrotnego algorytmu Euklidesa przedstaw największy wspólny dzielnik podanych liczb jako ich całkowitą kombinację:

a) 144 i 169; b) 286 i 169.

3.    Przedstaw w postaci ułamka łańcuchowego:

a) 355/113; b) 55/34; c) >/l0; d) y/U.

4.    Co to za liczba:

a) [2,2]; b) [2,1,1,1,4]; c) [5,2,1,1,2,10]; d) [1,M]?

5.    Znajdź największy wspólny dzielnik liczb:

a) lll¹¹¹¹¹¹ oraz llllll^{1 2}; b) lilii¹¹¹¹ oraz llll¹¹¹¹¹.

6.    Czy można wyznaczyć liczby a oraz 6, znając ich największy wspólny oraz ich najmniejszą wspólną wielokrotność?

7.    Scharakteryzuj liczby wymierne, których rozwinięcie w ułamek łańcuchowy składa się z samych jedynek.

8.    Udowodnij, że każda liczba mająca okresowe rozwinięcie łańcuchowe ma postać a + by/d, gd zie a, b, d € Q.

9.    Udowodnij, że pośród 101 liczb naturalnych z przedziału [1,200] znajdą się:

a)    dwie względnie pierwsze;

b)    dwie takie, że jedna z nich dzieli drugą.

10.    Wykaż, że prawie wszystkie liczby naturalne dadzą się przedstawić w postaci całkowitej nieujemnej kombinacji liczb 6, 10 i 15.

1

   Załóżmy, że największym wspólnym dzielnikiem liczb a\, a^, ..., a*, jest 1. Wy

2

każ, że prawie wszystkie liczby naturalne dadzą się przedstawić w postaci ich całkowitej nieujemnej kombinacji.