어떤 소수를 정수로 만들기 위해 곱해야하는 최수 정수 구하기

예를 들어 소수 0.375 를 정수로 만들어 주기 위하여 곱해야 하는 최소 정수는 몇일까?

답은 40이 나와야 한다.

10의 거듭제곱꼴인 매우 큰 수 S가 있다고 하자. 그리고 주어진 소수를 p라고 해보자.

그러면 p*S 는 정수가 될 것이 분명하다. (물론 가장 낮은 소수점 자릿수보다 10의 지수가 크거나 같아야만 한다)

그렇다면 gcd(pS, S) 를 해보자. 만약 p가 정수였다면 gcd(pS, S)는 S임이 자명하다. 하지만 p 가 소수이기때문에

p를 정수로 만들어 주기 위한 S의 최소 약수만큼이 빠질것이다. 그렇다면

 p를 정수로 만들어 주기 위한 S의 최소 약수는 S/gcd(pS, S) 가 될 것이다. 그런데 잘 생각해 보면

어떤 소수를 분수의 합꼴로 나타내보면, 즉 3*(1/10^(-1)) + 7*(1/10^(-2)) + 5*(1/10^(-3)) 으로 나타내보면

이것을 정수로 만들려면 모든 분모를 없애주어야 하는데 이 때 곱해주어야 할 수는 무조건 2와 5만을 

소인수로 갖는다는 것을 알 수가있다. 왜냐하면 분모들이 모두 10의 거듭제곱꼴이기 때문에 소인수가 2와 5뿐인 것만

봐도 알 수가 있다. 그런데 분자가 2나 5일 때는 분모와 약분이 가능해지기 때문에 곱해야 할 수가 10^(최하자릿수) 보다

작아질 수가 있는 것이다. 아무튼 그럼 p를 정수로 만들어 주기 위한 S의 최소 약수는 S/gcd(pS, S) 인데

S의 약수는 2와 5만을 소인수로 갖기 때문에 우리가 원하는 답과 같다는 것을 알 수 있을 것 같다.

그럼 위의 예에서는 S = 10^3 라고 보면 gcd(375, 1000) 은 25이고 이것으로 1000을 나누면 40이 잘 나오는 것을

알 수가있다.

결과적으로 어떤 소수 p를 정수로 만들기 위해 곱해야하는 가장 작은 정수는 S/gcd(pS, S) 이며

이 때 만들어지는 정수는 p*S/gcd(p*S, S) 라는것을 알 수가 있다.