나눗셈 : division
- a는 정수이고 b는 양의 정수라 할 때, 다음을 만족하는 유일한 정부 q, r이 존재한다.
약수(divisor)와 배수(multiple)
- a,b가 정수이고 a ≠ 0 일 때, b=ac를 만족시키는 종수 c가 있다면 “a가 b를 나머지 없이 나눈다.” 또는 “a는 b를 정제한다” 또는 “b는 a로 나누어 떨어진다” 라고한다. 이 경우 a는 b의 약수 또는 인수, b는 a의 배수라고 하며, 기호 a | b로 나타낸다. 만약 a가 b를 나누지 않을 때에는 기호 a ∤ b로 나타낸다.
나누어떨어짐의 성질
- a를 0이 아닌 정수, b와 c를 임의의 정수라고 할 떄
- a | b이고 a | c 이면, a | ( b + c ) 이다.
- a | b이면, a | bc 이다.
- a | b이고 b | c 이면, a | c 이다.
최대 공약수 : greatest common divisor
- 0이 아닌 두 정수 a, b에 대하여 d | a 이고 d | b 인 최대의 양의 정수 d를 a와 b의 최대 공약수라고 하고 d = gcd(a, b) 로 표기한다.
a, b에 대하여 1 = gcd(a, b)를 만족하면 a와 b는 서로소 라 한다.
- 배주의 항등식
- 적어도 하나는 0이 아닌 정수 a, b가 임의로 주어져 있다고 하자, 그러면 gcd(a, b) = d 라고 할 때, ax + by = d 를 만족하는 정수 x,y가 존재한다.
- 유클리드 호제법
- a, b, q, r이 정수일 떄, a = bq + r 이면 gcd(a,b) = gcd(b,r) 이다.
1
2
3
4
gcd(287, 91)
1 ] gcd(287, 91) = 14
2 ] gcd(91, 14) = 7
3 ] gcd(14, 7) = 0
24m x 15m 크기의 직각 사각형 바닥에 빈자리가 없도록 타일을 깔고자 한다.
동일한 크기의 정사각형 타일만 사용한다고 할 때, 필요한 타일의 최소 개수를 구하시오.
1
2
3
4
5
6
gcd(24,15)
1 ] gcd(24,15) = 9
2 ] gcd(15,9) = 6
3 ] gcd(9,6) = 3
4 ] gcd(6,3) = 0
∴ 3