4. 정수의 2, 10진 표현, 일차합동식

4. 정수의 2, 10진 표현, 일차합동식

\(b\in\mathbb{Z}\,(b>1)\)에 대하여 양의 정수 \(N\)을$$N=a_{m}b^{m}+a_{m-1}b^{m-1}+\cdots+a_{2}b^{2}+a_{1}b+a_{0}$$로 나타낼 수 있고 여기서 \(0\leq a_{k}<b\)이고 \(a_{m}\neq0\)이다. 위의 표현은 \(N\)을 \(b\)진법 \(m\)자리수로 나타낸 것으로 $$N=(a_{m}a_{m-1}\cdots a_{2}a_{1}a_{0})_{b}$$로 나타낼 수 있다.

이를 증명하는데 먼저 표현가능성을 보이자.

\(N<b\)이면, \(N=a_{0}\)이고, \(N\geq b\)이면, 나눗셈 알고리즘에 의해 \(N=q_{1}b+a_{0}\)이다. 

\(q_{1}<b\)이면, 이 과정을 정지(\(q_{1}=a_{1}\), \(N=a_{1}b+a_{0}\))하고

\(q_{1}\geq b\)이면, 다시 나눗셈 알고리즘을 적용해 \(q_{1}=q_{2}b+a_{1}\,(0\leq a_{1}<b)\)을 얻고 \(N=q_{2}b^{2}+a_{1}b+a_{0}\)이다.

\(q_{2}<b\)이면, 이 과정을 정지(\(q_{2}=a_{2},\,N=a_{2}b^{2}+a_{1}b+a_{0}\))하고

\(q_{2}\geq b\)이면, 이 과정을 반복하여 몫의 수열 \(q_{1}>q_{2}>\cdots>q_{k}\)를 얻는다. 이때 \(q_{k}\)는 감소수열이고, 이 과정은 유한번 안으로 끝나므로, 표현$$N=a_{m}b^{m}+a_{m-1}b^{m-1}+\cdots+a_{1}b+a_{0}$$를 얻는다.

이제 표현의 유일성을 보이자.$$N=a_{m}b^{m}+\cdots+a_{1}b+a_{0}=c_{n}b^{n}+\cdots+c_{1}b+c_{0}\,(m\geq n)$$이라 하자.

\(m>n\)일 때 \(c_{m}=c_{m-1}=\cdots=c_{n+1}=0\)이라 하면$$N=a_{m}b^{m}+\cdots+a_{1}b+a_{0}=c_{m}b^{m}+\cdots+c_{1}b+c_{0}$$이고 \(d_{k}=a_{k}-c_{k}\)라 하면$$0=d_{m}b^{m}+\cdots+d_{1}b+d_{0}\,(|d_{k}|<b)$$이고, \(d_{0},\,d_{1},\,\cdots,\,d_{1}\)중에서 최초로 \(0\)이 아닌 수를 \(d_{j}\)라고 하자. 서로 다른 표현법을 가정했기 때문에 \(d_{j}\)는 존재해야 한다. 그러면$$0=d_{m}b^{m}+\cdots+d_{j}b^{j}$$이고,$$0=d_{m}b^{m-j}+\cdots+d_{j}$$이므로$$d_{j}=-(d_{m}b^{m-j}+\cdots+d_{j+1}b)$$이고 \(d_{j}|b\)가 되는데 \(|d_{j}|<b\)이고 \(d_{j}\neq0\)이므로 모순이다. 따라서 유일한 표현을 갖는다.

\(k\)가 큰수일 때 \(a^{k}\)를 \(n\)으로 나눈 나머지를 다음의 방법으로 구할 수 있다:

\(k\)를 2진법으로 표현(\(k=(a_{m}a_{m-1}\cdots a_{1}a_{0})\))한 다음 \(a^{2^{j}}\)를 \(n\)으로 나눈 나머지를 계산해 그 결과들을 곱해서 구할 수 있다. 

예를들어 \(5^{110}\)을 \(131\)로 나눈 나머지를 구하려고 한다.

\(110=(1101110)_{2}\)이고,$$\begin{align*}5^{2^{0}}&\equiv5\,(\text{mod}\,131),\,5^{2^{1}}\equiv25\,(\text{mod}\,131),\,5^{2^{2}}\equiv(25)^{2}\equiv101\,(\text{mod}\,131),\,5^{2^{3}}\equiv(101)^{2}\equiv114\,(\text{mod}\,131)\\5^{2^{4}}&\equiv114^{2}\equiv27\,(\text{mod}\,131),\,5^{2^{5}}\equiv27^{2}\equiv73\,(\text{mod}\,131),\,5^{2^{6}}\equiv(74)^{2}\equiv105\,(\text{mod}\,131)\end{align*}$$이고 \(101=64+32+8+4(2^{6}+2^{5}+2^{3}+2^{2})\)이므로$$\begin{align*}5^{110}&=5^{64+32+8+4+2}\\&=5^{64}\cdot5^{32}\cdot5^{8}\cdot5^{4}\cdot5^{2}\\&\equiv105\cdot74\cdot114\cdot101\cdot25\\&\equiv60\,(\text{mod}\,131)\end{align*}$$이고 따라서 \(5^{110}\)을 \(131\)로 나눈 나머지는 \(60\)이다.

\(\displaystyle P(x)=\sum_{k=0}^{n}{c_{k}x^{k}}\)를 정수계수 다항식이라고 하자. \(a\equiv b\,(\text{mod}\,n)\)이면, \(P(a)\equiv P(b)\,(\text{mod}\,n)\)이다.

증명: \(a\equiv b\,(\text{mod}\,n)\)이므로 \(c_{k}a^{k}\equiv c_{k}b^{k}\,(\text{mod}\,n)\)이고, 따라서 \(P(a)\equiv P(b)\,(\text{mod}\,n)\)이다.

이 결과를 이용해서 정수계수 다항식 \(P(x)\)에 대해 \(a\)가 합동식 \(P(x)\equiv0\,(\text{mod}\,n)\)의 해이면, \(b\)도 이 합동식의 해가 됨을 알 수 있다.

\(N=a_{m}10^{m}+a_{m-1}10^{m-1}+\cdots+a_{1}10+a_{0}\,(0\leq a_{k}<10,\,a_{m}\neq0)\)를 \(N\)의 10진 전개라 하고

(a)$$S=a_{m}+a_{m-1}+\cdots+a_{1}+a_{0}$$(\(N\)의 자릿수들의 합)이라 하자. \(9|N\)일 필요충분조건은 \(9|S\)이다.

(b)$$T=a_{0}-a_{1}+a_{2}-\cdots+(-1)^{m}a_{m}$$이라 하자. \(11|N\)일 필요충분조건은 \(11|T\)이다.

증명: 

\(\displaystyle P(x)=\sum_{k=0}^{n}{a_{k}x^{k}}\,(0\leq a_{k}<10,\,a_{m}\neq0)\)이라 하자. 

(a): \(N=P(10),\,S=P(1)\)이고, \(10\equiv1\,(\text{mod}\,9)\)이므로 \(P(10)\equiv P(1)\,(\text{mod}\,9)\)이고 따라서 \(N\equiv S\,(\text{mod}\,9)\)이며 이 사실로부터 \(9|N\)일 필요충분조건은 \(9|S\)이다.

(b): \(N=P(10),\,T=P(-1)\)이고, \(10\equiv-1\,(\text{mod}\,11)\)이므로 \(P(10)\equiv P(-1)\,(\text{mod}\,11)\)이고 따라서 \(N\equiv T\,(\text{mod}\,11)\)이며 이 사실로부터 \(11|N\)일 필요충분조건은 \(11|T\)이다.

\(ax\equiv b\,(\text{mod}\,n)\)형태의 식을 1차합동식(또는 선형합동식, linear congruence)이라고 하고 \(ax_{0}\equiv b\,(\text{mod}\,n)\)인 \(x=x_{0}\)를 합동식의 해(solution)라고 한다.

\(x_{0}\in\mathbb{Z}\)가 1차합동식 \(ax\equiv b\,(\text{mod}\,n)\)의 해일 필요충분조건은 \(ax_{0}\equiv b\,(\text{mod}\,n)\)이고, 이 조건은 \(n|ax_{0}-b\)과 같고 또한 조건 \(y\in\mathbb{Z}\)가 존재해서 \(ax-b=ny\), 즉 \(ax+(-n)y=b\)와 같다.

(1) \(ax\equiv b\,(\text{mod}\,n)\)의 해가 존재할 필요충분조건은 \(d=\text{gcd}(a,\,n)|b\)이고

(2) \(d|b\)일 때, \(ax\equiv b\,(\text{mod}\,n)\)는 서로다른(법 \(n\)에 대해 합동이 아닌) \(d\)개의 해를 갖는다.

(1)의 증명은 디오판토스 방정식 \(ax+(-n)y=b\)의 해가 존재할 조건으로부터 성립한다.

(2)의 증명은 \((x_{0},\,y_{0})\)를 디오판토스 방정식 \(ax+(-n)y=b\)의 해라고 하면$$x=x_{0}+\frac{n}{d}t\,(t\in\mathbb{Z})$$이고$$\left\{x_{0},\,x_{0}+\frac{n}{d},\,\cdots,\,x_{0}+\frac{(d-1)n}{d}\right\}$$는 법 \(n\)에 대해 합동이 아니고 다른 모든해 \(x\)는 위의 집합의 어느 한 원소와 법 \(n\)으로 합동이다.$$x_{0}+\frac{in}{d}\equiv x_{0}+\frac{jn}{d}\,(\text{mod}\,n)\,(0\leq i,\,j\leq d-1)$$이라고 하자. 그러면$$\frac{n}{d}(i-j)\equiv0\,(\text{mod}\,n)$$이고$$i\equiv j\,(\text{mod}\,d)$$인데 \(|i-j|\leq d-1\)이므로 \(i=j\)이어야 한다.

\(x\)가 합동식 \(ax\equiv b\,(\text{mod}\,n)\)의 또다른 해 \(\displaystyle x=x_{0}+\frac{n}{d}t\,(t=qd+r\,(0\leq r<d))\)이면,$$x=x_{0}+\frac{n}{d}(qd+r)=x_{0}+qn+\frac{nr}{d}\equiv x_{0}+\frac{n}{d}r\,(\text{mod}\,n)\,(0\leq r<d)$$이므로 이 합동식의 해는 \(\displaystyle x_{0},\,x_{0}+\frac{n}{d},\,\cdots,\,x_{0}+\frac{(d-1)n}{d}\)이다.

위의 결과를 이용하여 \(\text{gcd}(a,\,n)=1\)이면, 합동식 \(ax\equiv b\,(\text{mod}\,n)\)은 단 하나의 해를 가짐을 알 수 있다.

일차합동식 \(18x\equiv 30\,(\text{42})\)에서 \(\text{gcd}(18,\,42)=6|30\)이므로 이 합동식은 \(6\)개의 해를 가진다.

\(6\cdot 3x\equiv6\cdot 5\,(\text{mod}\,6\cdot7)\)이므로 \(3x\equiv5\,(\text{mod}\,7)\)이고 \(3\cdot5\equiv1\,(\text{mod})\,7\)이므로 \(x\equiv5\cdot5=25\equiv4\,(\text{mod}\,7)\)이다. 그러면 하나의 특수해는 \(4\)이고, \(\displaystyle\frac{n}{d}=\frac{42}{6}=7\)이므로 따라서 \(x=4,\,11,\,18,\,25,\,32,\,39\)이다.

일차합동식 \(9x\equiv21\,(\text{mod}\,30)\)에서 \(\text{gcd}(9,\,30)=3|21\)이므로 \(3\)개의 해를 가진다.

\(3\cdot3x\equiv3\cdot7\,(\text{mod}\,3\cdot10)\)이므로 \(3x\equiv7\,(\text{mod}\,10)\)이고, \(3\cdot7\equiv1\,(\text{mod}\,10)\)이므로 \(x\equiv7\cdot7=49\equiv9\,(\text{mod}\,10)\)이다. 그러면 하나의 특수해는 \(9\)이고, \(\displaystyle\frac{30}{3}=10\)이므로 따라서 \(x=9,\,19,\,29\)이다.

참고자료:   

Elementary Number Theory 7th edition, Burton, McGraw-Hill