Page 23 - Numbertheory

@ @@@óáÕÜa@óïÝibÔ

:

. gcd(a, b ) = gcd(a, r ) b = qa + r ()

. gcd(a, b ) = gcd(−a, b ) = gcd(a,−b ) = gcd (−a,−b ) ( )

. a>0 gcd(a, 0) = a ( )

. a ≥b >0 [Euclidean Algorithm]

b = r1 a = r0

:

0 ≤ r2 < r1 r0 = q1r1 + r2
0 ≤ r3 < r2 r1 = q 2r2 + r3

0 ≤ rn−1 < rn−2 rn−3 = q n−2rn−2 + rn −1
0 ≤ rn < rn−1 rn −2 = qn−1rn−1 + rn

rn −1 = q n rn + 0

." "

0

. a = r0 > r1 > r2 > ... ≥ 0

gcd(a, b ) = gcd(r0, r1) = gcd(r1, r2) = ... = gcd(rn−1, rn ) = gcd(rn , 0) = rn

45 ( )
. 75

١٠