본문 바로가기

최대공약수

최소공배수, 최대공약수 - 유클리드 호제법 최대공약수 : gcd(a,b)최소공배수 : lcm(a,b) = a*b/gcd(a,b)최대공약수가 1인, 둘 이상의 양의 정수들은 서로소(relatively prime) a = Gx, b = Gy (단, x, y는 정수)일때... G 는 최대공약수최소공배수는 a*b/G 임 ---------------------- gcd(a,b) 구하기 설명 1071과 1029의 최대공약수를 구하면, 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 421029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 2142는 21로 나누어 떨어진다.따라서, 최대공약수는 21이다. 78696과 19332의 최대공약수를 구하면, 78696 ＝ .. 더보기

티스토리툴바