정답
\(a,b\in X\)이면 \(r^{ab}\)는 \(p\)의 원시근이다. 또한 조건을 만족하는 순서쌍 \((a,b)\)의 개수는 \(2|X|-1\)이고, 이것이 15가 되게 하는 모든 소수 \(p\)는 \(p=17,31\)이다.
출제 의도
원시근의 판정 조건(지수가 \(p-1\)과 서로소인지 여부)과, 생성원 \(r\)에 대해 \(r^u\equiv r^v\pmod p\)가 지수의 합동식 \(u\equiv v\pmod{p-1}\)로 환원된다는 성질을 이용해, 조건을 만족하는 순서쌍의 개수를 집합 \(X\)의 크기 \(|X|\)로 표현하고 이를 통해 가능한 소수 \(p\)를 찾아내는지를 평가한다.
풀이 과정
먼저 \(r\)이 홀수 소수 \(p\)의 원시근이라는 것은 \(r\)의 위수가 \(p-1\)이라는 뜻이다. 잘 알려진 성질로, \(r\)이 생성원일 때 \(r^k\)가 원시근이 될 필요충분조건은 \(\gcd(k,p-1)=1\)이다.
\(a,b\in X\)이면 \(\gcd(a,p-1)=\gcd(b,p-1)=1\)이다. 이때 \(\gcd(ab,p-1)=1\)임을 보이면 된다. 실제로 어떤 소수 \(q\)가 \(p-1\)을 나눈다고 하자. \(\gcd(a,p-1)=1\)이므로 \(q\nmid a\), \(\gcd(b,p-1)=1\)이므로 \(q\nmid b\)이다. 따라서 \(q\nmid ab\)이므로 \(p-1\)의 어떤 소인수도 \(ab\)를 나누지 못한다. 즉 \(\gcd(ab,p-1)=1\)이다. 그러므로 \(r^{ab}\)는 원시근이다.
이제 \(a,b\in X\)에 대하여 \(r^{ab}\equiv r^a\pmod p\) 또는 \(r^{ab}\equiv r^b\pmod p\)를 만족하는 순서쌍 \((a,b)\)의 개수를 구한다. \(r\)이 생성원이므로 다음이 성립한다.
$$ r^u\equiv r^v\pmod p \quad\Longleftrightarrow\quad u\equiv v\pmod{p-1} $$
편의상 \(m=p-1\)이라 두면, 조건 \(r^{ab}\equiv r^a\pmod p\)는
$$ ab\equiv a\pmod m $$
와 동치이다. 그런데 \(a\in X\)이므로 \(\gcd(a,m)=1\)이고, 따라서 \(a\)는 모듈러 \(m\)에서 역원을 갖는다. 위 합동식의 양변에 \(a^{-1}\)를 곱하면
$$ b\equiv 1\pmod m $$
가 된다. 또한 \(b\)는 \(1\le b 같은 방식으로 \(r^{ab}\equiv r^b\pmod p\)는
$$
ab\equiv b\pmod m
$$
이고, \(b\in X\)이므로 \(b\)의 역원을 곱해
$$
a\equiv 1\pmod m
$$
즉 \(a=1\)만 가능하다. 따라서 이 경우의 쌍은 \((1,b)\) 꼴로 \(|X|\)개이다. 두 조건을 “또는”로 합친 것은 \(b=1\)이거나 \(a=1\)인 경우의 합집합이다. \((1,1)\)이 중복되므로 전체 개수는
$$
|X|+|X|-1=2|X|-1
$$
이다. 문제에서 이 값이 15이므로
$$
2|X|-1=15 \quad\Rightarrow\quad |X|=8
$$
그런데 \(X=\{k\in\mathbb{N}\mid 1\le k
$$
\varphi(p-1)=8
$$
을 만족하는 홀수 소수 \(p\)를 찾으면 된다. \(\varphi(m)=8\)인 \(m\)은
$$
m\in\{15,16,20,24,30\}
$$
이고, \(p=m+1\)이므로 후보는 \(p\in\{16,17,21,25,31\}\)이다. 이 중 소수는
$$
p=17,\ 31
$$
뿐이다. <풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>