[정수의 성질]
- 약수(divisor), 배수(multiple)
- Division algorithm : a = bq + r (0<=r<b)
- gcd (greatest common divisor, 최대공약수) = d = gcd(a, b) = ax + by (d>0)
ex) gcd(14, 35) = gcd(-14, 35) = gcd(14, -35) = 7
= 14 x (-2) + 35 x (1) = -28 + 35 = 7
a = bq + r 이면 gcd(a, b) = gcd(r, b)
ex) gcd(1022222, 24555) = (* 1022222=24555*41+15467) #mod연산
= gcd(15467, 24555) = gcd(15467, 9088) = gcd(6379, 9088) = gcd(6379, 2709)
= gcd(961, 2709) = ... = gcd(3, 2) = 1
gcd(12321, 8658) = gcd(999, 333) = 3
- lcm (least common multiple, 최소공배수) = l = lcm(a, b) (l>0)
4의 배수 : 마지막 두 자리 수가 4의 배수인 수
8의 배수 : 마지막 세 자리 수가 8의 배수인 수
3의 배수 : 각 자리 수의 합이 3이 배수인 수
9의 배수 : 각 자리 수의 합이 9의 배수인 수
11의 배수 : 일의 자리로부터 두 자리씩 더한 수가 11의 배수인 수
ex) 13563 → 1/35/63 → 63+35+1=99 (11의 배수) / 145431 → 14/54/31 → 14+54+31=99 (11의 배수)
몇 가지 수식들 (증명생략)
1. gcd(a,b) lcm(a,b) = ab
2. gcd(a,b) = gcd(a, a+b) = gcd(a+b, b)
3. gcd(ac,bc) = c gcd(a,b)
4. lcm(ac,bc) = c lcm(a,b)
5. gcd(a,b,c) lcm(ab, bc, ca) = abc
6. lcm(a,b,c) gcd(ab, bc, ca) = abc
7. gcd(a, lcm(b,c)) = lcm(gcd(a,b), gcd(a,c))
8. lcm(a, gcd(b,c)) = gcd(lcm(a,b), lcm(a,c))
9. gcd(lcm(a,b), lcm(a,c), lcm(b,c)) = lcm(gcd(a,b), gcd(a,c), gcd(b,c))