기약분수

 

기약분수(Irreducible Fraction)는 분자와 분모의 공약수 (Greatest Common Factor, GCF)가 1뿐이어서 더이상 약분되지 않는 분수이다. 분자와 분모를 1 이외의 공통된 약수로 나누는 행위를 약분(Reduction of a fraction) 이라고 한다. 정수 a,b에 대해, 분수 a/b가 기약분수라는 것과, a,b가 서로소 즉, 최대공약수가 1이라는 것은 같은 의미이다.

[출처] 위키백과 - 기약분수

 

기약분수는 분모와 분자의 최대공약수를 구한 뒤 분모와 분자에 각각 나눠주면 된다.

(예) 분모: 120, 분자: 90 == 최대공약수: 30 → 분모: 4, 분자: 3

 

이 때, 최대 공약수를 구하는 방법에는 유클리드 호제법 등이 있다.

 

* 연관 문제:

- [백준] 1735번: 분수 합