5027720047

Lista 5 -Chińskie twierdzenie o resztach

1.    Rozwiąż układ kongruencji:

a)    x = 1 mod 3, x = 2 mod 5, x = 3 mod 7;

b)    2x = 1 mod 5, 3x = 9 mod 6, 4x = 1 mod 7, 5x = 9 modli.

2.    Pewna liczba z przedziału [1,1200] daje przy dzieleniu przez 9, 11, 13 resztę odpowiednio 1, 2, 6. Co to za liczba?

3.    Ile rozwiązań modulo 60 ma układ kongruencji:

a)    x = 5 mod 6, x = 4 mod 10;

b)    x = 5 mod 6, x = 7 mod 10.

Dlaczego otrzymane wyniki nie przeczą CTR?

4.    Gdy z koszyka wyjmujemy każdorazowo 2 jajka zostaje w nim jedno. Podobnie, gdy każdorazowo wyjmujemy 3, 4, 5 albo 6 jajek. Gdy wyjmujemy po 7 jajek, koszyk w końcu okazuje się pusty. Znajdź minimalna liczbę jajek w koszyku.

5.    Banda 17 piratów zdobyła worek jednakowych złotych monet. Przy próbie podziału po równo zostały 3 monety. Rozgorzał spór, w wyniku którego jeden z piratów stracił życie. Podjęto kolejną próbę podziału, ale tym razem zostało 10 monet. I znów doszło do zaciętej polemiki, po której liczba piratów zmalała do 15. Teraz już równy podział nie stwarzał matematycznych problemów. Znajdź minimalną liczbę monet.

6.    Rozwiąż układ kongruencji

5x + 3y = 1 mod 7, 7x + 3y= modli.

7.    Pokaż, jak wywnioskować z CTR, że istnieje nieskończenie wiele liczb pierwszych.

8.    Niech

M, =    .

Uzasadnij, że Mi = 1 mod m* i wyprowadź stąd nowy dowód CTR.