Page 24 - Numbertheory

@ @@Hßìÿa@ö§aI@†a‡Èÿa@óî‹Åä@

75 = 1× 45 + 30
45 = 1× 30 +15
30 = 2×15 + 0

. gcd(45, 75) = 15

ba gcd(a, b ) = 1 ()
14 9 ()
. (relatively prime)
. . gcd(9, 14) = 1

ba

yx

gcd(a, b ) = ax + by

45 ( )
.75

15 = 45 −1× 30

= 45 −1(75 −1× 45)

= 45× 2 + 75× (−1)

. y = −1 x = 2

١١