Page 25 - Numbertheory

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

gcd(a, b ) ()
gcd(45, 75) :

gcd(45, 75) = gcd(45, 30)
= gcd(30, 15)
= gcd(15,15)
= 15

.( )

:

gcd(a1,a2, ... , an ) = gcd(a1,a2 , ... ,an−2, gcd(an−1,an ) )

. gcd(35, 45, 75) ()

. gcd(45, 75) = 15 ( )

gcd(35, 45,75) = gcd(35,15)

35 = 2 ×15 + 5

15 = 3×5 + 0

. gcd(35, 45, 75) = gcd(35, 15) = 5

١٢