Matematyka dyskretna (M) - Lista 4.

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.

#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

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.

http://pl.wikipedia.org/wiki/Twierdzenie_Wilsona (cały dowód)

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