집합과 명제 고난도 문제: 배수 조건과 논리적 관계

문제

전체집합 $U = \{x \mid x\text{는 } 100 \text{ 이하의 자연수}\}$ 에 대하여, 세 조건 $p(x), q(x), r(x)$를 다음과 같이 정의한다.

$p(x): x\text{는 } k \text{의 배수이다. (단, } k \text{는 자연수)}$q(x): x\text{는 } m \text{의 배수이다. (단, } m \text{은 자연수)} $r(x): x\text{는 } 6 \text{의 배수이다.}

두 자연수 $k, m$이 다음 세 조건을 모두 만족할 때, 가능한 순서쌍 $(k, m)$의 개수를 구하시오.

(가) 명제 $r(x)$는 $p(x)$이기 위한 충분조건이다. (나) 명제 $\neg q(x)$는 $\neg p(x)$이기 위한 필요조건이다. (다) 모든 $x \in U$에 대하여 명제 '$q(x) \rightarrow r(x)$'가 참이 아니다.