$$이번 포스트에서는 자연수 집합 위에 자연수의 소인수분해와 밀접한 관련이 있는 거리_(distance)을 정의해 볼 것이다. 우선 실수 집합 위에서 정의된 유클리드 거리_{(Euclidean distance)}를 이용하여 두 자연수 $12$과 $13$ 사이의 거리를 구해보면, $\left|12-13\right|=1$임을 쉽게 알 수 있다. 이번에는 두 자연수 $12$와 $18$을 생각해 보자. 이 두 자연수의 유클리드 거리는 $\left|12-18\right|=6$이지만, 자연수의 관점에서 본다면 두 자연수 $12$와 $13$ 사이의 거리 보다는 $12$와 $18$ 사이의 거리가 더 가깝다고 주장할 수 있다. $12$와 $18$이 더 많은 소인수를 공유하고 있기 때문이다. 이와 같은 관점을 반영하여 다음과 같이 자연수 집합 위에 산술거리_{(arithmetic distance)}을 정의하고 그 성질을 알아볼 것이다.

자연수의 집합을 $\mathbb{N}$으로, 소수의 집합을 $\mathbb{P}$로 각각 나타내기로 하자. 그러면 자연수 $n\in \mathbb{N}$과 소수 $p\in \mathbb{P}$에 대하여 $n$의 $p$진 값매김_{($p$-adic valuation)}을 다음과 같이 정의한다. $${\nu }_p(n)=max\left\{k\ge 0\right|p^k|n\}.$$ 즉, ${\nu }_p(n)$이란 주어진 $n$을 소수 $p$로 최대 몇 번까지 나눌 수 있는지를 알려주는 함수이다. 또한 산술의 기본정리_{(fundamental theorem of arithmetic)}에 의하면 임의의 자연수 $n$은 유일한 소인수분해를 가지는데, 이때의 소인수분해를 $p$진 값매김을 이용하여 $$n=\prod _{p\in \mathbb{P}}{p}^{{\nu }_p(n)}$$ 와 같이 나타낼 수 있다. 이를 이용하여 두 자연수 $m,n\in \mathbb{N}$ 사이의 산술거리_{(arithmetic distance)}를 다음과 같이 정의하자.

예를 들어 두 자연수 $12=2^2\cdot 3^1$와 $18=2^1\cdot 3^2$의 산술거리는 다음과 같이 $$d(12,18)=\left|{\nu }_2(12)-{\nu }_2(18)\right|+\left|{\nu }_3(12)-{\nu }_3(18)\right|=\left|2-1\right|+\left|1-2\right|=2$$ 와 같이 계산된다. 반면 $d(12,13)=4$이므로, 자연수의 소인수분해의 관점에서 $12$와 $13$ 사이의 거리 보다는 $12$와 $18$ 사이의 거리가 더 가까워야 할 것이라는 우리의 직관과 잘 맞아떨어진다.

위에서 정의한 산술거리함수가 실제로 거리함수_(metric)가 된다는 사실은 정의로부터 자명함을 알 수 있다. 이제 산술거리함수의 여러가지 성질을 증명하는데 중요한 도구가 될 정리를 하나 살펴보자. 우선 주어진 $n\in \mathbb{N}$의 소인수분해에서 나타나는 (중복을 포함한) 모든 소인수의 개수를 나타내는 함수를 생각해 보자. 이 함수는 다음과 같이 $$\mathrm{\Omega }(n)=\sum _{p\in \mathbb{P}}{\nu }_p(n)$$ 로 나타낼 수 있다. 이 함수를 정수론에서는 소인수계량함수_{(prime omega function)}이라 한다. 이 함수는 완전가법적_{(completely additive)}임이 잘 알려져 있다. 즉, 임의의 자연수 $m,n\in \mathbb{N}$에 대하여, $$\mathrm{\Omega }(mn)=\mathrm{\Omega }(m)+\mathrm{\Omega }(n)$$ 이 성립한다. (이는 산술의 기본정리를 생각해보면 간단히 성립함을 확인해 볼 수 있다.)다음 정리는 산술거리함수를 소인수계량함수를 이용하여 표현할 수 있음을 보여준다. 이제 두 자연수 $m,n\in \mathbb{N}$의 최소공배수와 최대공약수를 각각 $\mathrm{lcm}(m,n)$과 $gcd(m,n)$으로 나타내면 $m$과 $n$의 산술거리를 소인수계량함수를 이용하여 다음과 같이 나타낼 수 있다.

증명. 먼저 최소공배수와 최대공약수를 $p$진 값매김을 이용하여 다음과 같이 표현 가능함을 확인해 보자. $$\begin{array}{rl}\mathrm{lcm}(m,n)& =\prod _{p\in \mathbb{P}}max\{{\nu }_p(m),{\nu }_p(n)\}\\ gcd(m,n)& =\prod _{p\in \mathbb{P}}min\{{\nu }_p(m),{\nu }_p(n)\}\end{array}$$ 이 사실을 이용하면, $$\begin{array}{rl}\mathrm{\Omega }(\mathrm{lcm}(m,n))& -\mathrm{\Omega }(gcd(m,n))\\ & =\prod _{p\in \mathbb{P}}max\{{\nu }_p(m),{\nu }_p(n)\}-min\{{\nu }_p(m),{\nu }_p(n)\}\\ & =\sum _{p\in \mathbb{P}}\left|{\nu }_p(m)-{\nu }_p(n)\right|\\ \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}& & =d(m,n).\end{array}$$

따라서 $\mathrm{lcm}(12,18)=36$, $gcd(12,18)=6$이라는 사실로부터, $$d(12,18)=\mathrm{\Omega }(36)-\mathrm{\Omega }(6)=4-2=2$$ 와 같이 계산할 수 있다.

증명. $m$과 $n$이 서로소이므로, $\mathrm{lcm}(m,n)=mn$, $gcd(m,n)=1$이 성립한다. 따라서 정리 1과 $\mathrm{\Omega }$의 완전가법성에 의해, $$\begin{array}{rl}d(m,n)& =\mathrm{\Omega }(\mathrm{lcm}(m,n))-\mathrm{\Omega }(gcd(m,n))\\ & =\mathrm{\Omega }(mn)-\mathrm{\Omega }(1)\\ & =\mathrm{\Omega }(m)+\mathrm{\Omega }(n)-\mathrm{\Omega }(1)\\ & =\mathrm{\Omega }(m)+\mathrm{\Omega }(n)\end{array}$$ 을 얻는다. 특히 임의의 자연수 $n\in \mathbb{N}$에 대하여 $n$과 $1$은 서로소이므로, $$d(n,1)=\mathrm{\Omega }(n)+\mathrm{\Omega }(1)=\mathrm{\Omega }(1)$$ 이 성립한다.$$

두 자연수 $m,n\in \mathbb{N}$가 서로소가 아닌 경우, 즉, 공통인수 $k\in \mathbb{N}$가 존재하는 경우에는, 다음 정리를 이용하여 $d(m,n)$의 계산을 좀 더 간단히 할 수 있다.

증명. 정리 1과 $\mathrm{\Omega }$의 완전가법성에 의해 다음을 얻는다. $$\begin{array}{rl}d(km,kn)& =\mathrm{\Omega }(\mathrm{lcm}(km,kn))-\mathrm{\Omega }(gcd(km,kn))\\ & =\mathrm{\Omega }(k\mathrm{lcm}(m,n))-\mathrm{\Omega }(kgcd(m,n))\\ & =[\mathrm{\Omega }(k)+\mathrm{\Omega }(\mathrm{lcm}(m,n))]-[\mathrm{\Omega }(k)+\mathrm{\Omega }(gcd(m,n))]\\ & =\mathrm{\Omega }(\mathrm{lcm}(m,n))-\mathrm{\Omega }(gcd(m,n))\\ \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}& & =d(m,n)\end{array}$$

따라서 $d(12,18)$의 경우, 다음과 같이 정리 2와 정리 3을 적용하여 $$d(12,18)=d(2,3)=\mathrm{\Omega }(2)+\mathrm{\Omega }(3)=1+1=2$$ 로 계산이 가능하다.

증명. $m=g{m}_0$, $n=g{n}_0$, $l=g{m}_0{n}_0$를 만족하는 서로소인 두 자연수 $m_0,n_0\in \mathbb{N}$을 택하자. 그러면 $m^k=g^k{m}_0^k$, $n^k=g^k{n}_0^k$로 나타낼 수 있다. 이제 $m_0$와 $n_0$가 서로소이므로 $m_0^k$와 $n_0^k$ 또한 서로소이다. 따라서 정리 2, 정리 3과 $\mathrm{\Omega }$의 완전가법성에 의해 $$\begin{array}{rl}d(m^k,n^k)& =d(m_0^k,d_0^k)\\ & =\mathrm{\Omega }(m_0^k)+\mathrm{\Omega }(n_0^k)\\ & =k[\mathrm{\Omega }(m_0)+\mathrm{\Omega }(n_0)]\\ & =kd(m_0,n_0)\\ \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}& & =kd(m,n).\end{array}$$

증명. 우선 적당한 소수 $\overline{p}\in \mathbb{P}$에 대하여 $m=\overline{p}n$이 성립한다고 가정하자. 그러면 정리 1과 $\mathrm{\Omega }$의 완전가법성에 의해 $$\begin{array}{rl}d(m,n)& =\mathrm{\Omega }(\mathrm{lcm}(m,n))-\mathrm{\Omega }(gcd(m,n))\\ & =\mathrm{\Omega }(\mathrm{lcm}(\overline{p}n,n))-\mathrm{\Omega }(gcd(\overline{p}n,n))\\ & =\mathrm{\Omega }(\overline{p}n)-\mathrm{\Omega }(n)\\ & =\mathrm{\Omega }(\overline{p})+\mathrm{\Omega }(n)-\mathrm{\Omega }(n)\\ & =\mathrm{\Omega }(\overline{p})\\ & =1\end{array}$$ 임을 알 수 있다.

이번에는 반대로 $d(m,n)=1$을 가정하자. 이는 정의에 의해 $$\sum _{p\in \mathbb{P}}\left|{\nu }_p(m)-{\nu }_p(n)\right|=1$$ 임을 뜻한다. 여기서 위 식 우변의 $\left|{\nu }_p(m)-{\nu }_p(n)\right|$의 값은 모든 $p\in \mathbb{P}$에 대하여 음이 아닌 정수이므로, 적당한 $\overline{p}\in \mathbb{P}$가 존재하여, $\left|{\nu }_{\overline{p}}(m)-{\nu }_{\overline{p}}(n)\right|=1$이고 $\overline{p}$가 아닌 모든 소수 $p$에 대하여 $\left|{\nu }_p(m)-{\nu }_p(n)\right|=0$이어야만 함을 알 수 있다. 이는 $m$과 $n$의 소인수분해를 비교해 보았을 때, 소수 $\overline{p}$를 제외한 모든 소인수의 개수가 동일함을 의미한다. 이제 $m\ge n$을 가정했으므로, $m=\overline{p}n$이어야만 하고, 따라서 증명이 완료된다.$$

증명. 주어진 가정으로부터 $m=g{m}_0$, $n=g{n}_0$, $l=g{m}_0{n}_0$를 만족하는 서로소인 두 자연수 $m_0,n_0\in \mathbb{N}$을 택할 수 있다. 따라서 정리 2와 정리 3에 의해 $$\begin{array}{rl}d(l,m)& =d(g{m}_0{n}_0,g{m}_0)=d(n_0,1)=\mathrm{\Omega }(n_0)\\ d(g,m)& =d(g,g{m}_0)=d(1,m_0)=\mathrm{\Omega }(m_0).\end{array}$$ 같은 방법으로 $d(l,n)=\mathrm{\Omega }(m_0)$, $d(g,n)=\mathrm{\Omega }(n_0)$을 얻는다. 한 편, $m_0$와 $n_0$는 서로소이므로 다시 한 번 정리 2와 정리 3에 의해 $$d(m,n)=d(g{m}_0,g{n}_0)=d(m_0,m_0)=\mathrm{\Omega }(m_0)+\mathrm{\Omega }(n_0).$$ 그러므로 위 정리에 주어진 세 변 모두 $\mathrm{\Omega }(m_0)+\mathrm{\Omega }(n_0)$ 값을 가짐을 알 수 있다.$$

아래 그림과 같이 집합 $\{1,2,\dots ,18\}$ 위에서의 약수관계를 부분순서_{(partial order)}로 정의하고, 이에 대한 하세 도형_{(Hasse diagram)}을 생각해 보자.

이제 정리 6에 의하면, 두 자연수 $12$와 $18$ 사이의 산술거리는 위 하세 도형에서 $12$에서 $18$로 가는 최단 경로의 길이와 같음을 알 수 있다.

참고. 주어진 자연수 $n\in \mathbb{N}$의 소인수분해를 p진 값매김 함수를 이용하여 다음과 같이 나타내자. $$n=\prod _{p\in \mathbb{P}}{p}^{{\nu }_p(n)}=2^{{\nu }_2(n)}{3}^{{\nu }_3(n)}{5}^{{\nu }_5(n)}{7}^{{\nu }_7(n)}\cdots .$$ 그러면 소인수분해의 유일성에 의해 "자연수 집합"과 "유한개의 항을 제외한 모든 항이 $0$인 음이 아닌 정수로만 이루어진 수열들의 집합"간의 일대일대응관계를 줄 수 있다. $$n=2^{{\nu }_2(n)}{3}^{{\nu }_3(n)}{5}^{{\nu }_5(n)}{7}^{{\nu }_7(n)}\cdots ⟷({\nu }_2(n),{\nu }_3(n),{\nu }_5(n),{\nu }_7(n),\dots ).$$ 예를 들면, $$\begin{array}{r}5⟷(0,0,1,0,\dots )\\ 12⟷(2,1,0,0,\dots )\\ 18⟷(1,2,0,0,\dots )\end{array}$$ 과 같은 식이다. 이 때, 두 자연수의 산술거리는 그 자연수들과 대응관계에 있는 두 수열 사이의 유클리드 거리_{(Euclidean distance)}와 같음을 알 수 있다. $$\begin{array}{rl}d(m,n)& =\sum _{p\in \mathbb{P}}\left|{\nu }_p(m)-{\nu }_p(n)\right|\\ & =|({\nu }_2(m),{\nu }_3(m),{\nu }_5(m),{\nu }_7(m),\dots )-({\nu }_2(n),{\nu }_3(n),{\nu }_5(n),{\nu }_7(n),\dots )|.\end{array}$$ 예를 들어 $12$와 $18$의 산술거리는 이 두 자연수의 대응관계에 있는 두 수열 $(2,1,0,0,\dots )$과 $(1,2,0,0,\dots )$의 유클리드 거리를 이용하여 $$d(12,18)=|(2,1,0,0,\dots )-(1,2,0,0,\dots )|=2$$ 로 계산할 수 있다.$$

위에서 살펴본 일대일대응 관계를 이용하여 산술거리를 유리수 집합까지 확장할 수 있는데, 이에 대한 내용은 다음 포스트에서 좀 더 자세히 알아보기로 하자.