정답
\(|A|=3,\ |B|=3\) 이고, \(|A|=|B\cup C|\) 를 만족시키는 정수 \(n\,(0\le n\le150)\) 의 개수는 \(60\)개이다.
출제 의도
선형 합동식의 해의 개수를 구하고, 소수 법에서의 곱셈군이 순환군이라는 사실을 이용하여 \(x^k\equiv1\pmod p\) 의 해의 개수를 파악하게 한다. 더 나아가 위에서 얻은 결과를 이용해 부분군의 합집합·교집합 크기를 계산하고, 그 조건을 만족시키는 지수 \(n\) 의 개수를 구하는 능력을 평가한다.
풀이 과정
먼저 집합 \(A\) 를 본다.
\(A=\{x\in\mathbb Z\mid 21x\equiv45\pmod{66},\ 0\le x\le65\}\) 에서 합동식 \(21x\equiv45\pmod{66}\) 을 푼다.
\(\gcd(21,66)=3\) 이고 \(3\mid45\) 이므로 해가 존재한다. 양변을 3으로 나누면 \[ 7x\equiv15\pmod{22} \] 가 된다. \(\gcd(7,22)=1\) 이므로 역원을 구하면 \(7\cdot19\equiv1\pmod{22}\) 이다. 따라서 \[ x\equiv19\cdot15\equiv285\equiv21\pmod{22} \] 이다.
원래 법 \(66\) 에서는 해가 \(3\)개이고 \[ x\equiv21,\ 43,\ 65\pmod{66} \] 이며 모두 \(0\le x\le65\) 에 들어간다. 따라서 \(|A|=3\) 이다.
다음으로 집합 \(B\) 를 본다.
\(B=\{x\in\mathbb Z\mid x^3-1\equiv0\pmod{151},\ 0\le x\le150\}\) 이다. \(151\) 은 소수이므로, 법 \(151\) 의 비제로 원소들의 곱셈군은 순서 \(150\) 인 순환군이다. 순서 \(150\) 인 순환군에서 방정식 \[ x^3=1 \] 의 해의 개수는 \(\gcd(3,150)=3\) 개이다. (순서 \(m\) 인 순환군에서 \(x^k=1\) 의 해는 \(\gcd(k,m)\) 개.)
따라서 \(0\le x\le150\) 에서도 서로 다른 해가 정확히 \(3\)개 존재하므로 \(|B|=3\) 이다.
이제 집합 \(C\) 를 보자.
\(C=\{x\in\mathbb Z\mid x^n-1\equiv0\pmod{151},\ 0\le x\le150\}\) 에서, 위와 같은 이유로 방정식 \(x^n=1\) 의 해의 개수는 \[ |C|=\gcd(n,150) \] 이다. (단, \(x=0\) 은 어떤 \(n\ge1\) 에 대해서도 해가 아님.)
집합 \(B\) 는 곱셈군의 부분군(순서 3), 집합 \(C\) 는 순서 \(\gcd(n,150)\) 인 부분군이다.
부분군 \(B\) 와 \(C\) 의 교집합의 크기는 \[ |B\cap C|=\gcd(|B|,|C|)=\gcd(3,\gcd(n,150)) \] 이므로
- \(3\mid n\) 인 경우: \(\gcd(n,150)\) 이 3의 배수이므로 \(B\subset C\) 이고 \(|B\cap C|=3\).
- \(3\nmid n\) 인 경우: \(\gcd(n,150)\) 은 3과 서로소이므로 \(|B\cap C|=1\) (항등원 1만 공통).
따라서 \[ |B\cup C|= \begin{cases} |C|=\gcd(n,150), & 3\mid n,\\[2mm] |B|+|C|-1=3+\gcd(n,150)-1=\gcd(n,150)+2, & 3\nmid n. \end{cases} \] 우리가 원하는 것은 \(|B\cup C|=|A|=3\) 인 경우이다.
두 경우로 나눠 보자.
(1) \(3\mid n\) 인 경우 이때 \(|B\cup C|=\gcd(n,150)=3\) 이어야 하므로 \[ \gcd(n,150)=3 \] 을 만족해야 한다.
\(\gcd(n,150)=3\) 이면 \(n\) 은 3의 배수이면서 2와 5의 배수가 아니다. 즉 \(n=3k,\ 1\le k\le50,\ \gcd(k,50)=1\) 이다. \(1\le k\le50\) 중 \(50\) 과 서로소인 수의 개수는 \[ \varphi(50)=50\left(1-\frac12\right)\left(1-\frac15\right) =50\cdot\frac12\cdot\frac45=20 \] 이므로 이런 \(n\) 이 \(20\)개 있다.
(2) \(3\nmid n\) 인 경우 이때 \(|B\cup C|=\gcd(n,150)+2=3\) 이어야 하므로 \[ \gcd(n,150)=1 \] 이 되어야 한다.
\(1\le n\le150\) 에서 \(\gcd(n,150)=1\) 인 정수의 개수는 \[ \varphi(150)=150\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right) =150\cdot\frac12\cdot\frac23\cdot\frac45=40 \] 이다. 이들은 모두 3의 배수가 아니므로 조건을 만족한다.
따라서 \(|B\cup C|=3\) 이 되도록 하는 \(n\) 의 개수는 \[ 20+40=60 \] 이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>