[Factors] gcd, lcm Theorem | C++ / Cpp

중고등학생때 해보고 냅다 까먹어 버린 최대공약수와 최소공배수를 다시 리마인드 하러 왔.땨.

 

# gcd(a,b) : greatest commom divisor

두 integer a,b에 대하여 a,b의 공통된 factor들 중 최대값을 뜻한다.

ex) gcd(30,12) =6

 

#lcm(a,b) : lowest common multiple 

두 integer a,b를 모두 factor로 가지는 수들 중 가장 작은 수

ex) lcm(30,12) = 60

 

# 관계 성립

<<  lcm(a,b) = a*b / gcd(a,b)  >>

 

 

# Theorem

non-zero integer a,b에 대해 아래 statement들이 성립한다.

1. gcd(a,b)=gcd(b,a)
2. if a>0, and a|b, -> gcd(a,b)=a
3. if a≡c(mob b) -> gcd(a,b)=gcd(c,b)
4. a≡c(mob b) a%b ==c

 

• a ≡ c (mod b) 이므로 b | (a-c). 따라서 정의에 의해 by = (a-c) 를 만족하는 integer y 가 존재. 
  • a%b = c ----> a-c = b * y
• 따라서 c = a – by 가 된다. 이제 d 를 a 와 b 의 common divisor 라 하면 d | (a-by) 이다 
  • d% (a-by) == 0
• => d 는 b 와 c 의 common divisor 가 된다.
• 반대로 d 가 b 와 c 의 common divisor 라면 d 는 b 와 a 의 common divisor 임을 쉽게 증명할 수 있다.

 

대충썼냐구요? 맞아요.