유클리드 호제법을 이용한 방식이다. a-bq가 서로소인 이유는 귀류법을 사용하여 증명하면 된다. 둘 사이에 공약수 p가 있다고 가정하고 진행하면 a,b가 공약수를 가지면서 모순이 된다. LCM은 더욱 간단하다. 최소 공배수이기때문에 서로소인 a,b를 모두 갖고 있어야하고 a와 b에도 서로소인 d또한 갖고 있어야 한다. 즉 최소공배수는 a*b*d가 된다. 코드를 보면 다음과 같다. public static int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % b); } gcd코드이다. 두 숫자를 받아 나머지를 찾는 방식으로 진행된다. 그러다 나머지가 나오지 않는 -> 즉 공약수가 처음 생기는 지점에서 그 값을 반환시키며 재귀 함수 호출을 마친다. p..
