1. 위수와 원시근
위수(계수, Order)
$ n > 1, gcd(a, n) = 1 $ 일 때, $a^k \equiv 1 \pmod{n}$을 만족하는 가장 작은 양의 정수 $k$를
법 $n$에 대한 a의 위수라고 한다.
오일러 정리 쓰면 $a ^ {\phi (n)} \equiv 1 \pmod{n}$이지만 종종 작은 게 더 있어서 이렇게 정의한다고 한다.
아래는 위수의 성질을 정리한 것이다. 증명은 생략.
1. $a \equiv b \pmod{n}$이면 법 $n$에 대한 $a, b$의 위수는 같다.
2. $a, n$이 서로소가 아니면 법 $n$에 대한 $a$의 위수는 존재하지 않는다.
3. 법 $n$에 대한 $a$의 위수가 $k$이면 $a^h \equiv 1 \pmod{n}$인 모든 h에 대해 $k | h$
4. 법 $n$에 대한 $a$의 위수가 $k$이면 $k | \phi (n)$
5. 법 $n$에 대한 $a$의 위수를 $k$라고 할 때, $a^j \equiv a^m \pmod{n}$이면 $j \equiv m \pmod{k}$이고, 그 역도 성립한다.
6. $a$가 법 $n$에 대한 위수 $k$를 가지면 $a, a^2, ... a^k$는 법 n에 대해 합동이 아니다.
위수 공식으로, 다음이 성립한다.
법 $n$에 대한 $a$의 위수가 $k$일 때, $a^s$의 위수는 $\frac{k}{gcd(s, k)}$이다.
증명
먼저 k가 위수이므로 $a^k \equiv 1 \pmod{n}$이다.
$g = gcd(s, k)$라 하면, $gcd(x, y) = 1$인 $x, y$에 대해 $gx = s, gy = k$인 $x, y$가 존재한다.
조금 생각해보면 $sy = kx = lcm(s, k)$임을 알 수 있다.
전개시키면 $a^{sy} \equiv a^{kx} \equiv 1 \pmod{n}$
$a^s$의 위수를 $r$이라 하면, 성질 3에 의해 $r | y$이고, $a^sr$을 생각하면 $k | sr$이다.
이때 $k | sr$이므로 전개하면 $gy | gxr, y | xr$이다.
이때 $gcd(x, y) = 1$이이므로 유클리드 보조정리에 의해 $y | r$이다.
따라서 $r | y, y | r$이므로 $r = y$이므로 위수 $r = y = \frac{k}{g} = \frac{k}{gcd(s, k)}$이다.
간단히 요약하면 $a^{sr} \equiv 1$인 $r$을 찾고 싶은데 $a^k \equiv 1$이여야 하니까,
대충 $sr = lcm(s, k)$가 되게 때려맞춘다는 것.
원시근(Primitive root)
$a \pmod{n}$의 위수가 $\phi (n)$이면 $a$를 $n$의 원시근이라고 한다.
예를 들어 법 7에 대해 생각해보면, $\phi (7) = 6$이다.
이때 3은 반드시 6승을 해야 1이므로 3은 7의 원시근인데, 2는 $2^3 \equiv 1 \pmod{7}$이므로 2는 7의 원시근이 아니다.
원시근에 대한 중요한 성질이 하나 있다.
$gcd(a, n) = 1$이며 $a_1, a_2, ..., a_{\phi(n)}$을 $n$과 서로소인 $n$ 미만의 수라고 하자.
만약 $a$가 $n$의 원시근이면, $a^1, a^2, ... , a^{\phi (n)}$은 $a_1, a_2, ... , a_{\phi (n)}$과 특정한 순서대로 합동이다.
요약하면 원시근이 성립하면 대충 $a$ 거듭제곱만으로 $n$의 기약잉여계를 채울 수 있다는 말이다.
증명은 $k = \phi (n)$으로 보일 수 있다.
다음으로 원시근의 개수이다. 정리는 아래와 같다.
$n$이 원시근을 가지면 그 원시근은 $\phi ( \phi ( n ) )$개이다.
증명
$a$를 $n$의 원시근이라 하면 위의 성질에 의해 원시근은 $a, a^2, ... , a^{\phi (n) }$ 에 존재한다.
이때 위수 공식에 의하면 $a^i$의 위수는 $\frac{\phi (n) }{ gcd(i, \phi (n) ) }$이므로 $gcd(i, \phi (n)) = 1$
따라서 원소의 개수는 $\phi( \phi(n) )$이다.
지표(index)
$r$이 법 $n$에 대한 원시근일 때, 다음을 만족하는 가장 작은 양의 지수 $k$를 $r$에 대한 $a$의 지표(index)라 한다.
$r^k \equiv a \pmod{n}$
표기는 $k = ind_r(a), ind(a)$로 한다.
로그와 유사하게 생겨서 지표를 이산로그(discrete logarithm)라고 부르기도 한다.
지표의 성질은 다음이 있다. 단순 노가다이므로 증명은 생략한다.
1. $r$이 $n$의 원시근일 때, $a \equiv b \pmod{n}$이면 $ind_r(a) = ind_r(b)$이다.
2. $ind_r(ab) \equiv ind_r(a) + ind_r(b) \pmod{\phi(n)}$
3. $ind_r(a^k) \equiv k \times ind_r(a) \pmod{\phi(n)}$
4. $ind_r(1) = 0, ind_r(r) = 1$
라그랑주의 정리(Lagrange's theorem)
내용은 다음과 같다.
$p$가 소수이고 정수계수 다항식 $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0$가
$a_n \neq 0 \pmod{p}$이면 $f(x) \equiv 0 \pmod{p}$는 최대 $n$개의 해를 가진다.
대충 인수정리 + 수학적 귀납법으로 증명할 수 있다.
사실 따름정리가 더 많이 쓰인다고 한다. 아래는 라그랑주 정리의 따름정리이다.
$p$가 소수이고 $d | p-1$이면 $x^d - 1 \equiv 0 \pmod{p}$는 $d$개의 해를 가진다.
비선형 합동식
그냥 이산로그 딸깍하면 된댄다. 귀찮아 몰라
이 활동은 jbs33_LDH과의 협업 뭐시기로 이루어졌습니다.