정수론

약수와 배수

약수/배수 판별

 나머지의 특징을 이용하면 두 정수의 약수/배수 관계를 판별할 수 있습니다.

두 정수 ab에 대하여 몫과 나머지를 x, y 라고 할 때에 아래와 같은 식이 성립함을 알고있습니다.

a = xb + y

 이 때 y(나머지)가 0이 되는 경우, a = xb가 되어 ab로 나누어 떨어지며 이 때 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꼴이 됩니다.

 이러한 특징은 이후에 소수 판별에서 중요한 특징으로 사용될 수 있습니다.

 

 

댓글

댓글 본문
작성자
비밀번호
  1. 붐브로스
    감사합니다!
  2. algoism
    감사합니다!
    대화보기
    • integer
      sqrt(a) => sqrt(n)
    버전 관리
    코딩몬스터
    현재 버전
    선택 버전
    graphittie 자세히 보기