Zadanie 1. Znajdź wszystkie liczby całkowite u spełniające jednocześnie następujące warunki: u �Ą 1(mod 7), u �Ą 6(mod 11), u �Ą 5(mod 13), 0 �ń u < 1000. 1. NWD(7,11,13) = 1 2. u1 �Ą 1(mod 7) u2 �Ą 6(mod 11) u3 �Ą 5(mod 13) N = 7 * 11 * 13 = 1001 n1 = 1001 / 7 = 143 n2 = 1001 / 11 = 91 n3 = 1001 / 13 = 77 143 * x1 �Ą 1(mod 7) -> x1 = 5, ponieważ: 7 | (143*5-1) 91 * x2 �Ą 1(mod 11) -> x2 = 4, ponieważ: 11 | (91*4-1) 77 * x3 �Ą 1(mod 13) -> x3 = 12, ponieważ: 13 | (77*12-1) 3. x �Ą ((1 * n1 * x1) + (6 * n2 * x2) + (5 * n3 * x3)) (mod N) x �Ą ((1 * 143 * 5) + (6 * 91 * 4) + (5 * 77 * 12)) (mod 1001) x �Ą ((1 * 143 * 5) + (6 * 91 * 4) + (5 * 77 * 12)) (mod 1001) x �Ą 7519 (mod 1001) x �Ą 512 (mod 1001), ponieważ 7519 = 7 * 1001 + 512 4. Rozwiązaniem układu kongruencji są liczby: u = {512, 512 + N, 512 + 2N, 512 + 3N, ...} W rozpatrywanym przedziale: 0 �ń u < 1000, rozwiązaniem jest: u = 512 Zadanie 2 Rozważmy hipotetyczny komputer dziesiętny, którego słowa (maszynowe) mogą pomieścić dwie cyfry, czyli rozmiarem słowa jest 100. Wybieramy kolejne wartości modułów m1 = 99, m2 = 97, itd zgodnie z zasadą opisaną w wykładzie (patrz slajdy z wykładu), by m1 była największą liczbą nieparzystą mieszczącą się w słowie maszynowym, m2 – największą liczbą całkowitą mniejszą od m1 i z nią względnie pierwszą, m3 – największą liczbę całkowitą, mniejszą od m2 i względnie pierwszą z liczba m1 i m2, itd. Wyznacz wszystkie możliwe wartości m_i i podaj wartość liczby N = m1 * m2 * ... Liczby {m1...m25} = {99, 98, 97, 95, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 1} N = m1 * m2 * m3 * ... * m25 = 10119137793756880366241365324639077391230 Algorytm: wejście: M, M �Ą 2 wyjście: a[] - tablica liczb mniejszych od M, parami względnie pierwszych (1) d := �Ł√M�Ś // część całkowita pierwiastka kwadratowego z M a[0] := M-1 last := 1 // liczba znaków w tablicy a i := M-2 (2) k := 0 (3) j := 2 (4) Jeżeli (i mod j = 0) oraz (a[k] mod j = 0) przejdź do (6) (5) Zwiększ: j = j + 1, jeżeli j �ń d wróć do (4) (6) Jeżeli j �ń d przejdź do (8) (7) Zwiększ: k = k + 1, jeżeli k < last wróć do (3) (8) Jeżeli (k = last) to: a[last] = i, last = last + 1 (9) Jeżeli (i = 0) zakończ, zwracając last jako rozmiar tablicy a[] W przeciwnym wypadku zmniejsz: i = i - 1 i przejdź do (2) Kod w C: src/main.c -> zad2() Zadanie 6 Korzystając z Rozszerzonego Algorytmu Euklidesa wyznacz liczby całkowite m i n, takie że 31408m + 2718n = NWD(31408, 2718) m = u[0] = 2 n = u[1] = -23 NWD(31408, 2718) = u[2] = 302 Kod w C: src/main.c -> zad6()