최대공약수 계산기 – GCF
두 개 이상의 숫자의 최대공약수(GCF/GCD)를 계산합니다. 무료 수학 계산기로 즉시 결과를 확인하세요.
최대 공배수 (GCF)가 뭔가요?
최대 공배수 (GCF) — 또는 최대 공약수 (GCD) 또는 최고 공배수 (HCF) — 는 두 개 이상의 숫자를 나누어 나머지가 남지 않는 가장 큰 양의 정수입니다. 이는 수론의 기본 개념이며, 분수 간단화, 단어 문제 해결 및 동일한 그룹으로 물건 분배에 있어 실제적인 응용이 있습니다.
예를 들어, 24의 인수는: 1, 2, 3, 4, 6, 8, 12, 24. 36의 인수는: 1, 2, 3, 4, 6, 9, 12, 18, 36. 공통 인수는: 1, 2, 3, 4, 6, 12. 그 중 가장 큰 것은 12이므로 GCF(24, 36) = 12입니다.
최대 공배수는 최소 공배수 (LCM)와의 기본적 인식과 관련이 있습니다: GCF(a, b) × LCM(a, b) = a × b. 즉, GCF를 알면 LCM를 쉽게 계산할 수 있으며, 반대로도 가능합니다. 24와 36의 경우: GCF = 12, LCM = 24×36/12 = 72.
최대 공배수 찾는 방법
최대 공배수 찾는 방법은 세 가지가 있습니다. 각 방법은 수치 크기에 따라 장점이 있습니다.
방법 1: 인수 목록
각 수의 모든 인수를 나열하고, 가장 큰 공통 인수를 식별하세요. 작은 수에 적합하지만 큰 수에 대해 번거롭습니다.
예: GCF(18, 24). 18의 인수: 1, 2, 3, 6, 9, 18. 24의 인수: 1, 2, 3, 4, 6, 8, 12, 24. 공통: 1, 2, 3, 6. GCF = 6.
방법 2: 소인수 분해
각 수를 소인수 분해하여, 각 소인수에 대한 최저 지수를 곱하여 공통 소인수를 곱하세요.
예: GCF(120, 180). 120 = 2³ × 3 × 5. 180 = 2² × 3² × 5. 공통 소인수: 2² × 3 × 5 = 4 × 3 × 5 = 60. GCF(120, 180) = 60.
| 단계 | 120 | 180 |
|---|---|---|
| 2로 나누기 | 60 | 90 |
| 2로 나누기 | 30 | 45 |
| 2가 30에 들어감 | 15 | — |
| 3으로 나누기 | 5 | 15 |
| 3으로 나누기 | — | 5 |
| 5로 나누기 | 1 | 1 |
| 최대 공배수 | 2² × 3 × 5 = 60 | |
방법 3: 유클리드 알고리즘
유클리드 알고리즘은 가장 효율적인 방법으로, 큰 수에 적합합니다. GCF(a, b) = GCF(b, a mod b)라는 성질에 기반합니다. 나머지가 0이 될 때까지 반복하세요. 마지막으로 남은 나머지가 최대 공배수입니다.
예: GCF(252, 105). 1단계: 252 = 2 × 105 + 42. 2단계: 105 = 2 × 42 + 21. 3단계: 42 = 2 × 21 + 0. GCF = 21.
최대 공배수 참조 표: 일반적인 숫자 쌍
수학 문제와 분수 간단화에 사용되는 일반적인 숫자 쌍의 최대 공배수 값을 아래에 나열했습니다.
| 숫자 A | 숫자 B | 최대 공배수 | 최소 공배수 | 사용 사례 |
|---|---|---|---|---|
| 12 | 18 | 6 | 36 | 시계 mặt 분수 |
| 24 | 36 | 12 | 72 | 십이율 |
| 15 | 25 | 5 | 75 | 15/25 = 3/5를 간단화 |
| 48 | 64 | 16 | 192 | 이미지 해상도 비율 |
| 100 | 75 | 25 | 300 | 퍼센티지 계산 |
| 120 | 180 | 60 | 360 | 원 circumference, 시간 |
| 56 | 84 | 28 | 168 | 주간 스케줄링 |
| 1001 | 143 | 143 | 1001 | 나눗셈의 놀라운 발견 |
최대 공배수(a, b) = b일 때, b는 a를 나누어 떨어집니다. 최대 공배수(a, b) = 1일 때, 두 수는 서로 공통 인수를 공유하지 않습니다. 공통 인수가 1인 수는 암호화에서 특히 중요합니다. RSA 암호화에서 공통 인수가 1인 수를 선택하는 것은 키 생성에 중요합니다.
분수 간단화하기
가장 일반적인 일상생활에서 GCF의 사용은 분수를 가장 낮은 형태로 단순화하는 것입니다. 분수 a/b를 단순화하려면, 분모와 분자를 GCF(a, b)로 나누어 분자와 분모를 나눕니다.
예시:
- 48/60: GCF(48, 60) = 12. → 48÷12 / 60÷12 = 4/5 ✓
- 56/84: GCF(56, 84) = 28. → 56÷28 / 84÷28 = 2/3 ✓
- 75/100: GCF(75, 100) = 25. → 75÷25 / 100÷25 = 3/4 ✓
- 144/360: GCF(144, 360) = 72. → 144÷72 / 360÷72 = 2/5 ✓
분수는 분자와 분모의 GCF가 1일 때 가장 낮은 형태(단순한 형태)입니다. 예를 들어, 3/5는 이미 가장 낮은 형태입니다. GCF(3, 5) = 1이기 때문입니다. 6/10은 가장 낮은 형태가 아닙니다. GCF(6, 10) = 2이기 때문입니다. 6/10을 3/5로 단순화할 수 있습니다.
요리에서 GCF는 레시피를 조절하는 데 도움이 됩니다. 레시피는 24명에게 먹을 수 있지만 18명에게 먹고 싶다면, 18/24 = 3/4의 양을 사용해야 합니다. GCF(18, 24) = 6이므로 18/24 → 3/4입니다. 모든 양을 3/4로 곱합니다.
GCF의 실용적 응용
GCF는 분수 단순화 외에도 여러 가지 유형의 실제 문제를 해결할 수 있습니다:
균등 그룹 배포: 36개의 사과와 48개의 오렌지를 동일한 양의 과일이 남지 않도록 담는 바구니에 담을 때, 각 바구니에 동일한 양의 과일이 담기는 최대 수는 GCF(36, 48) = 12입니다. 각 바구니에 3개의 사과와 4개의 오렌지를 담습니다.
타일/그리드 문제: 120cm × 180cm의 바닥을 동일한 사각 타일로 덮을 때 낭비를 최소화하고 싶습니다. 가장 큰 사각 타일은 GCF(120, 180) = 60cm의 한 변 길이를 가집니다. 필요한 타일의 수는 (120/60) × (180/60) = 2 × 3 = 6입니다.
스케줄링: Event A는 12일 간격으로 반복하고 Event B는 18일 간격으로 반복합니다. 그들이 다시 함께 발생하는 것은 LCM(12, 18) = 36일 후입니다. GCF(12, 18) = 6은 단위 주기를 알려줍니다. LCM = 12×18/6 = 36입니다.
암호화: RSA 암호화는 두 개의 큰 소수 p와 q를 선택하는 데 필요합니다. 공개 키 n = p×q와 이커를 사용하여 Euler의 totient 함수 φ(n) = (p-1)(q-1)입니다. 알고리즘을 안전하게 작동하려면 암호화 키 e는 φ(n)와 coprime 이어야 합니다. - 즉, GCF(e, φ(n)) = 1입니다. coprimality는 유럽 알고리즘을 사용하여 검증됩니다.
유칼리드 알고리즘: 역사와 증명
유칼리드 알고리즘은 유clid의 원리 (책 VII, 제안 2, 기원전 300년)에서 설명 된 가장 오래된 알고리즘 중 하나입니다. - 대부분의 현대 수학보다 2,000년 이상 앞서 있습니다. 그것은 그 아름다움과 효율성으로 인해 오늘날까지 광범위하게 컴퓨터 사용을 계속하고 있습니다.
알고리즘: GCF(a, b)에서 a > b를 찾으려면 a를 b로 나누어 몫 q와 나머지 r을 얻습니다. 그런 다음 GCF(a, b) = GCF(b, r). r = 0이 될 때까지 반복합니다. 마지막 비ゼ로 나머지는 GCF입니다.
왜 그것이 작동하는가: d가 a와 b를 모두 나눌 수 있다면, d가 a - q × b = r를 나눌 수 있다. 그 반대도 마찬가지입니다. d가 b와 r를 모두 나눌 수 있다면, d가 b × q + r = a를 나눌 수 있다. 따라서 (a, b)의 공통 약수 집합은 (b, r)의 공통 약수 집합과 같습니다. 그들의 GCF는 같아야 합니다.
효율성: 최악의 경우 (연속적인 피보나치 수), 알고리즘은 O(log(min(a,b))) 단계를 취합니다. GCF(F(n+1), F(n))은 정확히 n 단계가 필요합니다. - 이것이 연속적인 피보나치 수를 "최악의 경우"로 부르는 이유입니다. GCF(144, 89) : 144 = 1 × 89 + 55; 89 = 1 × 55 + 34; 55 = 1 × 34 + 21; 34 = 1 × 21 + 13; 21 = 1 × 13 + 8; 13 = 1 × 8 + 5; 8 = 1 × 5 + 3; 5 = 1 × 3 + 2; 3 = 1 × 2 + 1; 2 = 2 × 1 + 0. GCF = 1. (10 단계, F(12)/F(11)와 예상한대로)
GCF vs LCM: 주요 차이점과 연결
GCF (Greatest Common Factor)와 LCM (Least Common Multiple)은 상반되는 연산입니다. 각을 사용할 때는 분수 산술을 이해하는 것이 중요합니다.
| 속성 | GCF | LCM |
|---|---|---|
| 정의 | 두 수를 모두 나누는 가장 큰 수 | 두 수를 모두 나누는 가장 작은 수 |
| 결과 크기 | ≤ min(a, b) | ≥ max(a, b) |
| 사용할 때 | 분수 간소화, 등분배 | 분수 더하기 (공통 분모 찾기) |
| 공식 | 유칼리드 알고리즘 | LCM(a,b) = a × b / GCF(a,b) |
| 특별한 경우 | GCF(a, a) = a | LCM(a, a) = a |
| 소수인 경우 | GCF(a, b) = 1 | LCM(a, b) = a × b |
분수 1/12 + 1/18를 더하려면 LCM(12, 18) = 36을 찾습니다. 변환: 3/36 + 2/36 = 5/36. 분수 12/18를 간소화하려면 GCF(12, 18) = 6을 찾습니다. 나누기: 2/3.
Frequently Asked Questions
24와 36의 GCF는 무엇입니까?
GCF(24, 36) = 12. 24의 인수는 1, 2, 3, 4, 6, 8, 12, 24입니다. 36의 인수는 1, 2, 3, 4, 6, 9, 12, 18, 36입니다. 가장 큰 공통 인수는 12입니다. 동등하게: 24 = 2³ × 3, 36 = 2² × 3², GCF = 2² × 3 = 12.
GCF는 GCD와 같은가?
예. GCF (Greatest Common Factor), GCD (Greatest Common Divisor), HCF (Highest Common Factor)는 모두 동일한 개념 - 양의 정수 중 가장 큰 공통 인수입니다. 다른 교과서와 지역에서 다른 용어를 사용합니다: GCF는 미국 초등 교육에서 일반적이지만, GCD는 고등 수학 및 컴퓨터 과학에서, HCF는 영국과 인도 교육에서 사용됩니다.
GCF가 1이면?
GCF(a, b) = 1, 두 수는 "coprime" 또는 "relatively prime"라고 합니다. 공통의 소인수는 없습니다. 예: GCF(7, 9) = 1, GCF(14, 15) = 1, GCF(35, 36) = 1. 연속된 정수는 항상 coprime입니다. coprime 수는 모듈러 대수와 암호학에서 중요합니다.
3개 이상의 수의 GCF를 찾는 방법은?
GCF(a, b, c) = GCF(GCF(a, b), c) 연산을 반복적으로 적용합니다. 예를 들어, GCF(12, 18, 24): GCF(12, 18) = 6, 그 다음 GCF(6, 24) = 6. 따라서 GCF(12, 18, 24) = 6. 순서는 연관성의 연산으로 인해 중요하지 않습니다.
n에 대한 GCF(0, n)는 무엇입니까?
GCF(0, n) = n에 대해 n이 0이 아닌 경우. 0은 모든 비零 정수에 의해 나누어집니다. 유클리드 알고리즘: GCF(n, 0) = n (기본 사례 - 두 번째 수는 0이면 첫 번째 수를 반환합니다). GCF(0, 0)는 정의되지 않습니다 (또는 때때로 0으로 정의됩니다).
음수에 대한 GCF를 사용할 수 있나요?
예, 그러나 GCF는 양의 정수에 대해 정의됩니다. 음수에 대해 절대값을 취하세요: GCF(-24, 36) = GCF(24, 36) = 12. 유클리드 알고리즘은 절대값과 함께 작동합니다.
GCF를 계산하는 가장 빠른 알고리즘은?
일반적인 정수 크기 (64비트까지) 에 대해, 이진 GCD 알고리즘 (Stein의 알고리즘)은 현대 하드웨어에서 유클리드 알고리즘보다 빠릅니다. 암호학적으로 큰 수 (천의 비트) 에 대해 더 정교한 알고리즘, Lehmer-GCD 또는 반 GCD 방법이 사용됩니다.
GCF는 소인수 분해와 어떻게 관련되어 있나요?
GCF(a, b)는 두 인수 분해에서 공통되는 소인수에 대한 모든 인수, 각 인수를 최소화합니다. 예: 360 = 2³ × 3² × 5 및 756 = 2² × 3³ × 7. GCF = 2^min(3,2) × 3^min(2,3) = 2² × 3² = 4 × 9 = 36.
GCF는 컴퓨터 과학에서 어떻게 사용되나요?
컴퓨터 과학에서 GCF (GCD)는 RSA 암호화 키 생성 (coprimality를 확인), 유리수 대수 (분수 단순화), 모듈러 역수 계산 (확장 유클리드 알고리즘), 중국 제약 정리 (해), 해시 테이블 설계 (소수 크기 선택)에서 사용됩니다. 유클리드 알고리즘은 모듈러 대수에서 연산의 정의된ness를 증명하기 위해도 사용됩니다.
GCF는 가장 큰 소인수와 같은가요?
아니요. GCF는 두 수의 공통 인수에 대해, 단일 수의 가장 큰 소인수와는 다른 개념입니다. GCF(12, 15) = 3, 그러나 12의 가장 큰 소인수는 3이고 15의 가장 큰 소인수는 5입니다. 단일 수의 가장 큰 소인수는 두 수의 GCF와는 다른 개념입니다.