약수/배수 판별
나머지의 특징을 이용하면 두 정수의 약수/배수 관계를 판별할 수 있습니다.
두 정수 a와 b에 대하여 몫과 나머지를 x, y 라고 할 때에 아래와 같은 식이 성립함을 알고있습니다.
a = xb + y
이 때 y(나머지)가 0이 되는 경우, a = xb가 되어 a는 b로 나누어 떨어지며 이 때 b는 a의 약수라 할 수 있습니다.
이처럼 '나머지가 0이다'와 'b는 a의 약수이다'는 서로 동치가 됨을 알 수 있습니다.
또한 'b가 a의 약수이다'는 'a가 b의 배수이다'와 동치입니다.
그러므로 우리는 % 연산자와 if문을 통하여 두 정수의 약/배수 관계를 쉽게 판별할 수 있습니다.
bool isMultiple(int mul,int div)
{//mul이 div의 배수이면 true, 아니면 false
return (mul % div) == 0;
}
약수의 특징
어떤 수의 약수는, 나누어서 나머지가 0이 된다는 특징 외에도 재미있는 규칙성을 보입니다.
양의 정수 n, a, b에 대해 n=a*b (단, a <= b) 라고 해봅시다. 그러면 a와 b는 n의 약수가 됨을 알 수 있습니다.
a와 b의 값을 생각해봅시다. a의 최소값은 1이 되며, 이 떄 b는 n이 됩니다. 위의 식이 성립하기 위해서는 a가 점점 커질수록 b는 작아져야 하는 반비례 관계임을 알 수 있습니다.
위의 식 n=a*b에서 약수 a가 존재하면, 곱해서 n이 되는 짝 b가 항상 존재합니다. 즉, 모든 약수는 곱해서 n이 되는 쌍이 존재하며, (a, b) 꼴 쌍에서 a <= b라고 할 경우 a의 최대값은 sqrt(n)가 됩니다.
그 이유는 a <= b 가 성립하는 상태에서 a가 가장 커질 수 있는 경우는 a == b인 경우이고, 이는 n= a*a꼴이 됩니다.
이러한 특징은 이후에 소수 판별에서 중요한 특징으로 사용될 수 있습니다.
