유클리드 호제법

Thm 2.2 a와 b가 정수이고 b>0 일 때 a = g*b + r (0≤r≤b) 인, g와 r이 반드시 유일하게 존재한다. (유클리드 호제법) GREATEST COMMON DIVISOR (최대 공약수) a가 b를 나눈다(b가 a에 의해 나눠진다. ) -> b = ac를 만족하는 정수 c가 존재한다. -> b는 a의 배수이다. a는 b의 약수이다. 0은 모든 수의 배수이다. / 1은 모든 수의 약수이다. 자기 자신은 자기 자신의 약수이다. 예) 0 = a * 0 a가 b를 나눈다는 것을 기호로 다음과 같이 나타낸다. a | b a가 b를 나누지 못한다는 것을 다음 기호로 나타낸다. (대충 수식으로 쓰는 문자가 뭔지 몰라서 그림판으로 그렸다는 뜻) 정수 d가 다음 조건을 만족할 때, d는 a와 b의 gcd라 한다. 1. d | a, d | b // d는 a와 b의 공약수이다. 2. c | a, c | b // c ≤ d (d는 a, b의 공약수 중 가장 크다.) = c | a, c ...

원문링크 : 유클리드 호제법