진법 표현

모든 양의 정수 $N$은 다음과 같이 $b$의 거듭제곱의 항들로 유일하게 나타낼 수 있다.

$$ N=a_mb^m+a_{m-1}b^{m-1}+\cdots+a_1b+a_0 ~(0 \le a_i < b) $$

증명

나눗셈 정리에 의해 $N=q_1b+a_0$인 $q_1$과 $a_0(0 \le a_0 < b)$이 유일히 존재한다.

만약 $q_1<b$라면 종료한다.

그렇지 않다면 $q_1=q_2b+a_1~(0 \le a_1 < b)$인 $q_2$와 $a_1$이 유일히 존재한다.

$N=q_2b^2+a_1b+a_0$처럼 계속 진행하면 시행은 유한히 반복되고 종료된다.

따라서 이와 같은 표현은 존재한다. $\square$

유일성 증명 생략

2진법과 이진 지수 알고리즘

특히 $b=2$일 때, 이를 $2$진법이라하며 $0$과 $1$로만 수가 표현된다.

$105=(11010001)_2$처럼 쓸 수 있고, $79$는 예를 들어

$$ 79=1 \cdot 2^6+0 \cdot 2^5+0 \cdot 2^4+1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 1 $$

처럼 표현된다.

이진 지수 알고리즘은 PS에서 바로 거듭제곱을 $O(\log n)$에 계산하도록 해주는 분할정복을 이용한 거듭제곱 알고리즘을 의미한다.

알고리즘

큰 수 $k$에 대해 $a^k \pmod n$을 알고싶다 하자.

$k=(a_ma_{m-1}\dots a_1a_0)_2$ 처럼 이진수로 나타낼 수 있다.

이를 이용해 부분적인 답을 구해 결과에 곱해줄 수 있다.

예를 들어,

$5^{110} \pmod {131}$ 을 보자.

$5^{110}=5^{64+32+8+4+2}=5^{64} \cdot 5^{32} \cdot 5^8 \cdot 5^4 \cdot 5^2 \equiv 105 \cdot 74 \cdot 114 \cdot 101 \cdot 25 \equiv 60 \pmod {131}$ 이다.

이를 코드로 표현하면 다음과 같다.

ll poww(int a, ll b, ll mod = -1) {
   ll ret = 1;
   while (b) {
      if (b & 1) {
         ret *= a;
         if (~mod) ret %= mod;
      }
      a *= a;
      if (~mod) a %= mod;
      b >>= 1;
   }
   return ret;
}

나눗셈 테스트

Theorem 4.4 ⭐️

$P(x)=\displaystyle \sum_{k=0}^{m} c_kx^k$를 정수계수 $c_k$ 들을 가진 $x$의 다항 함수라 하자.

$a \equiv b \pmod n$이면, $P(a) \equiv P(b) \pmod n$이다.

증명

$a \equiv b \pmod n$일 때, 음이 아닌 정수 $k$에 대해,

$a^k \equiv b^k \pmod n$이 되기 때문에, 각 $k$에 대해

$c_ka^k \equiv c_kb^k \pmod n$이 된다.

따라서

$$ \displaystyle \sum_{k=0}^m c_ka^k \equiv \sum_{k=0}^m c_kb^k \pmod n $$

$\square$

Corollary 1

$a$가 합동식 $P(x) \equiv 0 \pmod n$의 해이고, $a \equiv b \pmod n$이면, $b$또한 해이다.

$\because P(a) \equiv P(b) =0 \pmod n$이기 때문에 $b도$ 해가 된다.

Theorem 4.5

$N=a_m10^m+a_{m-1}10^{m-1}+\cdots +a_110^1+a_0$ 일 때,

$S=a_m+a_{m-1}+\cdots+a_1+a_0$ 라고 하면,

쉽게 말하면 10진수로 표현했을 때, 자리수의 합이다.

$9 \mid S \Longrightarrow 9 \mid N$

증명

$1 \equiv 10 \pmod 9 \Longrightarrow P(1)\equiv P(10) \pmod 9$

$P(1)=a_m+a_{m-1}+\cdots +a_0$ 이므로 $P(1)=S$ 이고, $P(10)=N$ 이기 때문에 $S \equiv N \pmod 9$

$N \equiv 0 \pmod 9$일 필요충분조건은 $S \equiv 0 \pmod 9$ 이다. $\square$

이제 $n=9$ 일 때 말고, $n=11$ 일 때도 비슷한 성질을 볼 수 있다.

Theorem 4.6

$N=a_m^10^m+a_{m-1}10^{m-1}+\cdots+a_1^10+a_0$ 일 때,

$S=a_0-a_1+a_2-a_3+\cdots+(-1)^ma_m$ 이라 하면,

$11 \mid S \Longrightarrow 11 \mid N$

증명

$-1 \equiv 10 \pmod {11}$ 이다.

즉, $P(-1) \equiv P(10) \pmod {11}$

$P(-1) = S$ , $P(10)=N$ 이기 때문에,

$S \equiv N \pmod {11}$ 임이 보인다.

$N \equiv 0 \pmod {11}$일 필요충분조건은 $S \equiv 0 \pmod {11}$ 이다. $\square$

Comments

You may also enjoy