정수론 | 양의 정수의 약수개수와 약수의 총합

자연수 $n$의 소인수 분해식을 $n=p_1^{e_1}p_2^{e2}\cdots p_k^{e_k}$이라고 하면,

양의 정수 $n$의 약수개수는 $r(n)=(e_1+1)(e_2+1)\cdots (e_k+1)$

$n$의 약수들의 총합은 $\sigma(n)=(1+p_1+\cdots+p_1^{e_1})(1+p_2+\cdots+p_2^{e_2})\cdots(1+p_k+\cdots+p_k^{e_k})$

$= (\frac{p_1^{e_1+1}-1}{p_1-1})(\frac{p_2^{e_2+1}-1}{p_2-1})\cdots (\frac{p_k^{e_k+1}-1}{p_k-1})$

예제

양의 정수 $n=2^{30}3^{15}$에 대해, $n^2$의 양의 약수 중 $n$보다 작고 $n$의 약수가 아닌 것의 개수를 구하여라.

$n$이 $2^23$이라 생각해보자.

$n^2$의 약수를 나열하면 $1,2,3,4,6,8,9,12,16,18,24,36,48,72,144$로 총 15개임을 알 수 있다. 즉, 제곱수이므로 홀수 개의 약수를 가지며 피제곱수를 중심으로 양 옆에 같은 수의 약수가 분포한다.

$n^2$의 약수 중 $n$보다 작은 약수의 개수는 $\bigr[\cfrac{61\cdot31}{2}\bigl]$이고 여기서 $n$의 약수는 $31\cdot16$이므로 $\bigr[\cfrac{61\cdot31}{2}\bigl]-(31\cdot16-1)=450$

$2^{18}+1$의 양의 약수의 총합을 $A$라고 할 떄, $\big[ \frac{A}{1000} \big]$를 구하여라.

양의 약수의 총합을 구해야 하므로 $2^{18}+1$을 소인수 분해식의 형태로 나타내야 한다. $k=2^4$라 했을 때 $(2k^2)^2+1$로 나타낼 수 있고 식을 조금 변형하여

$(2k^2)^2+2\cdot2k^2+1-2\cdot2k^2$

$=((2k^2)+1)^2-(2k)^2$

$=(2k^2+2k+1)(2k^2-2k+1)$로 나타낼 수 있다.

다시 $k$를 대입하면 $481\cdot545=13\cdot37\cdot5\cdot109$으로 $14\cdot38\cdot6\cdot110$이 약수의 총합이 되어 $\big[ \cfrac{351120}{1000} \big]=351$이 된다.

여기서 $481$이 $13\cdot37$이란 사실을 찾기 힘들 수 있다. 보통 소인수 분해 시 10이상 넘어가면 소수로 판단하기 쉽기 때문이다. (필자가 그랬음)

$k=2^6$이라 했을 떄 $k^3+1$로 나타낼 수 있고 이는 $(k+1)(k^2-k+1)$로 나타낼 수 있으므로 $k+1=65=5\cdot13$임을 알 수 있다. 위에서 545가 5의 배수이나 13의 배수임이 아닌 것을 확인하였으므로 481은 13의 배수이다.

개인적으로 $k^3+1$의 인수분해식까지 유념할 것 같진 않지만 익숙해지거나 습관이 들면 가능하겠다 싶어서 함께 작성하였다.

자연수 $n$에 대하여 $2n$은 28개의 양의 약수를 갖고, $3n$은 30개의 양의 약수를 가질 때, $6n$의 양의 약수의 개수를 구하여라.

$n=2^a3^b5^c\cdots p^k$라 하자. $n$의 양의 약수의 개수는 $(a+1)(b+1)(c+1)\cdots(k+1)$이다. 문제에서는 2와 3에 대해서만 다루고 있으므로 뒤의 $(c+1)\cdots(k+1)$를 $A$로 치환하자.

$2n$의 약수의 개수는 $(a+2)(b+1)A=28$, $3n$의 약수의 개수는 $(a+1)(b+2)A=30$이다.

둘을 서로 빼면 $A(a-b)=2$이므로 $(A,(a-b))=(1,2)or(2,1)$이다.

1. $A$가 1이면 $a=b+2$이고 식에 대입하여 $a=5,b=3$을 얻을 수 있다.
2. $A$가 2면 $a=b+1$이고 식에 대입하였을 때 $b^2+4b-11=0$에 따라 해가 무리수이므로 성립하지 않는다.

따라서 $6n$의 양의 약수의 개수는 $(5+2)(3+2)=35$이다.

양의 정수 $n$에 대하여 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$의 해 (x,y)의 개수를 구하여라.

양변에 $nxy$를 곱하여 정리하면 $ny+nx=xy$를 얻을 수 있고 우변으로 옮긴 후 $n^2$을 더해 정리하면 $(x-n)(y-n)=n^2$가 완성된다. $n$의 소인수 분해식이 $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$라고 했을 때, 문제의 조건에 따라 $x,y>n$이므로 $n^2$의 약수에 대해 $(x,y)$가 한쌍씩 일대일 대응으로 성립한다. 따라서, 해의 개수는 $\gamma(n^2)=(2e_1+1)(2e_2+1)\cdots(2e_k+1)$이다.

$\frac{3}{18620}=\frac{1}{a}+\frac{1}{b}$를 만족시키는 양의 정수 $a,b$의 순서쌍 $(a,b)$의 개수를 구하여라.

18620을 $A$라 하자. $\cfrac{3}{A}=\cfrac{1}{a}+\cfrac{1}{b}$ 에서 양변에 $Aab$를 곱한 후 정리하면 $3ab-A(a+b)=0$가 된다. 하지만 이 경우 두 수의 곱으로 표현할 수 없기 때문에 양변에 3을 곱하고 $A^2$을 더한 뒤 인수분해를 하면 $(3a-A)(3b-A)=A^2$의 식을 얻을 수 있다. 그리고 18620을 소인수분해하면 $2^2\cdot5\cdot7^2\cdot19$이므로 $(3a-18620)(3b-18620)=2^4 5^2 7^4 19^2$이다.

18620을 3으로 나눈 나머지는 2이므로 $3a-18620 \equiv 3b-18620 \equiv 18620^2 \equiv 1(mod\ 3)$이다. 그러므로 18620을 두 수로 분할한 값은 각각 3으로 나눈 나머지가 1이어야 한다. $2^4 5^2 7^4 19^2$를 $3a-18620$과 $3b-18620$으로 분리했을 때 3으로 나눈 나머지가 1이어야 하므로 각 인수별로 3으로 나눈 나머지가 2가 되는 경우가 있는지 검사하여야 한다. $2\equiv2^3\equiv2(mod\ 3),\ 5\equiv2(mod\ 3),\ 2^2\equiv2^4\equiv1(mod\ 3),\ 7\equiv 19\equiv5^2\equiv 1(mod\ 3)$ 이므로 $2^4 5^2$를 분할하는 경우엔 3으로 나눈 나머지가 모두 2이거나 1이 되도록 묶어줘야 한다.

$2\equiv2^3\equiv2(mod\ 3)$은 2와 8을 3으로 나눈 나머지가 2임을 의미한다. 자세한 개념은 '합동식'을 찾아보자. (나중에 포스팅으로 다룰 예정)

$2^45^2$를 분할하는 방법으로는 모두 1인 경우의 (1,4,16)(1,25)와 모두 2인 경우의 (2,8)(5)이 있으므로 $3\cdot2+2\cdot1$이 되어 8가지이다. 그리고 나머지 약수에 대해서는 모든 경우에 대해 성립하므로 $8\cdot(4+1)\cdot(2+1)=120$이다.

양의 정수 $n$을 두 개 이상의 연속한 양의 정수의 합으로 나타내는 방법을 생각하자. 예를 들어 15의 경우에는 7+8, 4+5+6, 1+2+3+4+5의 세 가지 방법이 있다. 999를 이와 같이 나타내는 방법의 수를 구하여라.

$(n+1)+(n+2)+\cdots+(n+k)=999$라 하자. 좌변을 정리하면 $nk+\frac{k(k+1)}{2}=999$가 되고 양변에 2를 곱하여 정리하면 $2nk+k^2+k=k(k+2n+1)=2\cdot999=2\cdot3^3\cdot37$이 된다. 문제에서 두 개 이상의 연속한 양의 정수의 합으로 나타낸다 했으므로 $k$의 범위는 $2\leq k < k+2n+1$이며 이 조건에 만족하지 않는 경우는 (1,999)밖에 없다.

$2\cdot999$의 약수의 개수는 $2\cdot4\cdot2=16$이고 조건에 맞지 않는 약수는 2개에 $k+2n+1$보다 작아야 하므로 나타낼 수 있는 방법의 개수는 $\frac{16-2}{2}=7$이다.

양의 정수 $k$에 대하여 $a_k=\frac{(2^k)^{30}-1}{31}$이라 하자. $S=a_1+a_2+\cdots+a_{10}$이라 할 때, S를 31로 나눈 나머지를 구하여라.

주어진 수식은 초항이 1이고 공비가 32인 등비급수의 합을 나타내는 수식으로 $a_k=\cfrac{(2^5)^{6k}-1}{32-1}$ 과 같이 변형할 수 있다. 즉 $a_k=1+2^5+\cdots+(2^5)^{6k-1}$로 표현할 수 있고 각 항을 31로 나누면 $\cfrac{a_k}{31}\equiv1+1+\cdots+1=6k(mod31)$이다. 문제에서 주어진 $S$를 대입해서 나타내면 $\frac{S}{31}\equiv6(1+2+\cdots+10)(mod\ 31)=6\cdot\cfrac{10\cdot11}{2}(mod\ 31)=20$

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저