최대공약수와 유클리드 알고리즘
수학이야기
2015. 1. 12. 16:41
정의 $b=ac\;(a\not=0)$일 때, $b$는 $a$로 나누어 떨어진다고 하고 기호로 $a|b$로 적는다. 나누어 떨어지지 않을 때는 $a\not| \;\; b$로 적는다. 이 때, $a$는 $b$의 약수(divisor), $b$는 $a$의 배수(multiple)라고 한다. $b=ac$라면 $b=(-a)(-b)$이다. 언제나 음수와 양수가 짝으로 있으므로 약수와 배수를 연구할 때 양의 정수만 생각해도 충분하다. 또한 나누는 수는 $0$이 아닌 수로 생각한다. 정리 정수 $a,b,c$에 대하여 다음이 성립한다. 1) $a|0,\;1|a,\;a|a$ 2) $a|1\iff a=\pm1$ 3) $a|b \wedge c|d\Rightarrow ac|bd$ 4) $a|b \wedge b|c\Rightarro..