====== Matematyka dyskretna (M) - Lista 4. ====== ===== Zadanie 1. =====


def gcd(a,b):
   if b == 0: return a
   return gcd(b,a%b)

def lcm(a,b):
   if a < 1 or b < 1: raise ValueError
   return (a/gcd(a,b))*b

\\ Nie mnożymy najpierw $a \cdot b$ tylko najpierw dzielimy $a$ przez $\gcd(a,b)$ i potem mnożymy przez $b$. Tym sposobem nigdy nie przetrzymujemy w zmiennej wartości większej od a lub b. ===== Zadanie 2. =====

#vanzi
def mgcd(l):
	t = len(l)
	if t < 1:
		raise ValueError
	elif t == 1:
		return l[0]
	else:
		return mgcd(l[:t-2] + [gcd(l[t-1],l[t-2])])

dla lcm tak samo ===== Zadanie 3. ===== ===== Zadanie 4. ===== ===== Zadanie 5. ===== ===== Zadanie 6. ===== ===== Zadanie 7. ===== a) $ xz \equiv yz \text{ (mod mz) } <=> \exists_{k \in Z} xz = kmz+yz <=> \exists_{k \in Z} x = km+y <=> x \equiv y \text{ (mod m) }$\\ b) $ z \cdot z' + m \cdot m' = \gcd{(m,z)} => z \cdot z' + m \cdot m' \equiv \gcd{(m,z)} \text{ (mod m) } $\\ $ => z \cdot z' \equiv \gcd{(m,z)} \text{ (mod m) } $\\ $xz \equiv yz \text{ (mod m) } <=> $\\ $xzz' \equiv yzz' \text{ (mod m) } <=> $\\ $x\gcd{(m,z)} \equiv y\gcd{(m,z)} \text{ (mod m) } <=> $\\ $x\gcd{(m,z)} \equiv y\gcd{(m,z)} (\text{mod } \gcd{(m,z)} \cdot \frac{ m}{\gcd{(m,z)})} ) <=> $\\ $x\equiv y (\bmod{\frac{ m}{\gcd{(m,z)})}})$\\ Korzystając z a)\\ c) $ x \equiv y \text{ (mod mz) } <=>\exists_{k \in Z} kmz = y - x <=> \exists_{l \in Z} lm = y - x <=> x \equiv y \text{ (mod m) } $\\ Bo $l = kz$. ===== Zadanie 8. ===== ===== Zadanie 9. ===== http://pl.wikipedia.org/wiki/Twierdzenie_Wilsona (cały dowód) ===== Zadanie 10. ===== ===== Zadanie 11. ===== ===== Zadanie 12. ===== ALGORYTM http://pl.wikipedia.org/wiki/Chi%C5%84skie_twierdzenie_o_resztach 27, 64 i 25 są parami względnie pierwsze Wtedy... : $ M = 27\cdot 64\cdot 25 $ $ M_1 = 64\cdot25, M_2 = 27\cdot25, M_3 = 27\cdot64 $ $ g_1 = 4, g_2 = 11, g_3 = -8 $ (wartości g wylicza się algorytmem euklidesa) $ y_1 = 11, y_2 = 12, y_3 = 13 $

>>> x = 11*64*25*4 + 12*27*25*11 - 13*27*64*8
>>> x
-20212
>>> x += 27*64*25
>>> x
22988
>>> x%27
11
>>> x%64
12
>>> x%25
13

===== Zadanie 13. ===== ===== Zadanie 14. ===== ===== Zadanie 15. ===== {{tag>[listy_zadan]}}