【整数#2】約数

〈約数〉

ある整数を割り切る整数

12の約数

1,2,3,4,6,12

100の約数

1,2,4,5,10,20,25,50,100

53の約数

1,53

必ず1と自分自身を含む

約数が1と自分自身のみの数を素数という

aがbの約数⇔b=anとなる整数nがある

倍数のaとbが入れ替わっただけ

aがbの約数⇔bがaの倍数

〈公約数〉

2つの整数の約数のうち、共通している数

12と100の公約数

1,2,4

12と42の公約数

42の約数1,2,3,6,7,14,21,42

1,2,3,6

12と35の公約数

1

〈最大公約数（gcd）〉

公約数の最小値は必ず1だが、最大値は変わる

12と100→4

12と42→6

12と17→1

公約数は最大公約数の約数

最大公約数が1である数の組みを互いに素という

12と35は互いに素

→12を35倍しない限り35の倍数にはならない

問題

それぞれの最大公約数を求めよ

12と16

20と25

9と14

21と35

24と55

前回

次回