VII 권
명제
명제 29
소수는 자신의 배수가 않은 수와 서로소이다.
소수 \(a\)에 대하여, \(b\)는 \(a\)의 배수가 아니다. 그러면 \(a\), \(b\)는 서로소이다.
VII 권
명제
소수는 자신의 배수가 않은 수와 서로소이다.
소수 \(a\)에 대하여, \(b\)는 \(a\)의 배수가 아니다. 그러면 \(a\), \(b\)는 서로소이다.
소수 \(a\)에 대하여, \(b\)는 \(a\)의 배수가 아니다.
그러면 \(a\), \(b\)는 서로소임을 보여야 한다.
\(a\), \(b\)가 서로소가 아니라고 하자. 그러면 \(a\), \(b\)의 공약수 \(c\)가 존재한다. [VII권 정의 11]
\(c\)는 \(b\)의 약수이고, \(a\)는 \(b\)의 약수가 아니므로, \(c\ne a\)이다.
\(c\)는 \(a\), \(b\)의 공약수이므로 \(c\)는 \(a\)의 약수이다. 그런데 \(a\)는 홀수이고 \(c\ne a\)이므로 이것은 모순이다.
그러므로 \(a\), \(b\)는 서로소이다.
그러므로 소수는 자신의 배수가 않은 수와 서로소이다.
Q.E.D.
사실상, 이 명제는 소수가 다른 수에 서로소가 되지 못하는 유일한 방법은 소수가 다른 수의 약수(나누는 것)라는 것이다.
이 명제는 다음 명제와 [IX권 명제 12], [IX권 명제 36]에서 사용된다.