정수론 | 소수와 합성수

소수와 합성수란

• 양의 정수 p $(p\ne1)$가 p와 1 이외의 양의 약수를 갖지 않을 때 p를 소수(Prime Number)라고 정의한다.

• 1을 제외한 수 중 소수가 아닌 수를 합성수(Compositive Number)라고 부른다.

정리: 1보다 큰 양의 정수는 소수인 약수를 가진다.

1보다 큰 양의 정수 n에 대해 집합 S는 1보다 큰 n의 약수 집합이라고 정의하자. $n \in S$이므로 S는 공집합이 아님을 확인할 수 있다. 자연수의 순서 공리에 의해 자연수로 이루어진 n의 약수집합의 부분집합 S는 최소원소 p를 갖는다. 이 때 p는 소수이다. (∵ p가 소수가 아니라면 p보다 더 작은 인수 q가 최소원소여야 하기 때문에 모순이다.)

정리: 소수는 무한히 많다.

소수의 개수가 유한하다고 가정하자. (ex. $p_1\cdot p_2\cdot p_3\cdots p_n$) 그리고 임의의 정수 N이 $1+p_1\cdot p_2\cdots p_{n-1}\cdot p_n$이라고 하면 앞서 설명한 정리에 따라 소수약수 p를 갖는다. 하지만 gcd(N,N-1)=1이므로 소수약수 p는 유한하다고 가정한 소수집합에 포함될 수가 없다. 그러므로 소수의 개수가 유한하다는 가정에 모순된다.

산술의 기본정리(Fundamental Theorem of Arithmetic)

n이 1보다 큰 자연수이면 n은 소수이거나 소수의 곱으로 표현이 가능하며 n이 소수의 곱으로 표현될 경우 곱하는 순서를 무시하면 표현방법은 유일하다.

n이 소수일 경우 증명의 필요성이 없기 때문에 합성수라고 가정하면 n의 약수 중 소수인 약수를 무조건 가진다. 그 소수를 $p_1$이라고 했을 때 $1<n_1<n$을 만족하는 적당한 자연수 $n_1$이 존재하여 $n=n_1p_1$을 만족한다.

만약 $n_1$이 소수이면 $n$은 이미 소수의 곱으로 표현되었다고 할 수 있으므로 $n_1$이 $1<n_1<n$인 합성수라고 하자. 따라서 $n_1$도 양의 약수 중 소수가 존재한다. 그 약수를 $p_2$이라고 하면 $1<n_2<n_1$을 만족하는 적당한 자연수가 존재하여 $n_1=p_2n_2$가 되고 $n=p_1p_2n_2$이다.

마찬가지로 $n_2$가 소수인지 합성수인지에 따라 검사하며 과정을 반복하면 $n>n_1>n_2>\cdots>1$이고 $n,n_1,n_2\cdots,1$은 자연수이므로 그 과정이 유한하다. 그러므로 $n_k$가 소수가 되도록 하는 k는 존재하며 $n_k=p_k$라고 하면 $n=p_1p_2\cdots p-k$이다. 따라서, 합성수 n은 소수의 곱으로 표현할 수 있다.

그리고 그 표현방법이 유일함을 증명하기 위해 유한하지 않다고 가정하여 $n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$라고 하자. r, s는 자연수이고 n을 이루는 소수들은 $p_1\le p_2\le\cdots\le p_r$, $q_1\le q_2\le \cdots\le q_r$의 관계를 만족한다.

$p_1|q_1q_2\cdots q_s$이므로 적당한 자연수 i에 대해 $p_1=q_i\ge q_1$을 만족하며 역으로 $q_1|p_1p_2\cdots p_r$이므로 적당한 자연수 j에 대해 $q_1=p_j\ge p_1$를 만족한다. $p_1$과 $q_1$는 각각에 대해 가장 작은 자연수이므로 $p_1=q_1$이다. 따라서 양변에서 두 수를 소거한 뒤 $p_2$와 $q_2$에 대해서도 같은 과정을 반복할 수 있다. 계속 반복하다 보면 결국 $r=s$가 아니면 모순이 발생한다는 점을 알 수 있다.

만약 $r\ne s$인 경우 r>s라 하자. 앞서 설명한 과정을 반복했을 때 마지막으로 $p_{s+1}\cdots p_r=1$가 되어 모순이 발생한다. 그러므로 곱하는 순서를 고려하지 않는다면 합성수를 소수의 곱으로 표현하는 방법은 유일함을 확인할 수 있다.

정리: 임의의 양의 정수 m이 $\sqrt{m}$보다 작거나 같은 약수를 갖지 않으면 m은 소수이다.

명제의 대우가 참이면 해당 명제도 참이므로 "m이 합성수이면 $\sqrt{m}$보다 작거나 같은 약수를 가진다."를 증명하자.

m이 소수가 아니라고 가정하면 m은 1과 m 이외의 약수 p를 갖는다. 즉, $m=pq$, $1<p\le q<m$이 성립한다. $m=pq\ge q^2$에서 $q\le\sqrt{m}$이므로 m은 $\sqrt{m}$보다 작거나 같은 약수를 갖는다.

예제

임의의 정수 n에 대하여 $n^4-20n^2+4$는 소수가 아님을 보여라

문제에서 제시된 식을 합차공식의 형태로 정리하면 $n^4-4n^2+4-16n^2$가 되고 $(n^2-2)^2-(4n)^2$가 되어 $(n^2+4n-2)(n^2-4n-2)$가 된다. 주어진 수가 소수라면 둘 중 하나는 1 혹은 -1의 값을 가져야 한다. 따라서, $n^2+4n-2=\pm1$, $n^2-4n-2=\pm1$의 4가지 경우에서 정수해를 갖는 경우가 존재하면 합성수이다. 하지만 우변을 좌변으로 이항하여 정리하여도 정수해가 존재하지 않음을 확인할 수 있다.

$41pm-42p^2=m^3$을 만족하는 양의 정수 m이 존재하게끔 하는 소수 p의 값을 모두 더하여라.

$p(41m-42p)=m^3$에서 $p|m$이다. 따라서 적당한 정수 k에 대해 $m=pk$라 하면 $41p^2k-42p^2=p^3k^3$이고 양변에서 $p^2$을 소거하면 $41k-42=pk^3$이다. 그리고 k에 대해 정리하면 $k(41-pk^2)=42$이다. 즉, $k|42$이고 $41k-42>0$ 으로 인해 k>1이고 $41>pk^2$에 따라 p가 최소값인 2가 되더라도 k<4를 만족해야 한다. 즉, k가 취할 수 있는 값은 2, 3이다.

• k=2이면 $41-4p=21$에 따라 p=5
• k=3이면 $41-9p=14$에 따라 p=3

소수 p, r (p>r)에 대하여 $p^r+9r^6$이 정수의 제곱일 때, p+r의 값을 구하여라

$p^r+9r^6=k^2$이라고 하자. 그럼 합차 공식에 따라 $p^r=(k+3r^3)(k-3r^3)$로 정리할 수 있다. 그렇다면 $r=a+b,\ (a<b)$에 대해 $k+3r^3=p^b,\ k-3r^3=p^a$로 표현할 수 있다. 미지수 k를 소거하기 위해 서로 뺴면 $p^b-p^a=6r^3$이 된다. 즉, $a\ne0$이면 $p|6r^3$으로 p는 2, 3, r 중 하나를 인수로 가져야 한다. 문제에 제시된 정의에 따라 p는 p>r인 소수이므로 p=3, r=2의 값을 가질 수 있다. 그러나 $p^r+9r^6$에 대입하면 $3^2+9\cdot2^6$가 되어 $9(2^6+1)$이므로 제곱수가 성립되지 않아 a=0임을 확인하였다.

따라서 a=0이므로 b=r이다. p>r이므로 p는 홀수이고 그와 함께 k도 홀수가 된다. a=0을 대입하면 $3r^3+1=k$에 따라 r은 짝수여야 한다. 짝수인 소수는 2밖에 없으므로 r=2이다. $3r^3+1=k$으로 인해 k=25이고 $k-3r^3=25+3\cdot2^3=49=p^2$에 따라 p=7이다.

다음 조건을 만족하는 소수 a, b, c에 대하여 세수의 곱 abc를 구하여라

• $b+8$은 a의 배수이고, $b^2-1$은 a와 c의 배수이다.
• $b+c=a^2-1$이다.

$b^2-1=ak$라고 하자. 문제의 조건에 b+8도 a의 배수라고 제시되었으므로 합차 공식의 형태로 만들면 $ak-63=b^2-64=(b+8)(b-8)$이다. 우변이 a의 배수이므로 좌변도 a의 배수여야 한다. 그렇기 때문에 $a|63$이 성립해야 한다. a는 소수이므로 3, 7을 가질 수 있다.

1. a=3일 때, b+c=8이고 가능한 순서쌍은 (3,5), (5,3)이다. 그러나 두 경우 모두 $a|b+8$이 성립하지 않는다.
2. a=7일 때, b+c=48이고 b+8은 7의 배수이다. b가 소수이면서 조건을 만족하는 값은 13, 41이다. c또한 소수여야 하므로 b, c가 취할 수 있는 값은 (41, 7)이다.

모든 양의 정수 k에 대하여 $2^{2^k}+2^{2^{k-1}}+1$은 소수인 약수를 k개 이상 가짐을 보여라

$a=2^{2^{k-1}}$이라 하면 $a^2+a+1$꼴이 되어 인수분해가 되지 않는다. 따라서 차수를 높이기 위해 $a=2^{2^{k-2}}$라 두면 $a^4+a^2+1$이 된다. 앞의 계수를 모르기 때문에 임의의 정수인 x, y를 계수로 가정하여$(a^2+xa+1)(a^2+ya+1)$이라 두고 전개하면 $a^4+a^3(x+y)+a^2(2+xy)+a(x+y)+1$이다. 2+xy=1이고 x=-y에 따라 인수분해 결과는 $(a^2-a+1)(a^2+a+1)$이 되어 $(2^{2^{k-1}}-2^{2^{k-2}}+1)(2^{2^{k-1}}+2^{2^{k-2}}+1)$이 된다. 그렇다면 같은 방법을 통해 $a=2^{2^{k-3}}$이라 가정하면 $(2^{2^{k-1}}-2^{2^{k-2}}+1)(2^{2^{k-2}}-2^{2^{k-3}}+1)(2^{2^{k-2}}+2^{2^{k-3}}+1)$이 되고 끝까지 그 과정을 반복하면 $(2^{2^{k-1}}-2^{2^{k-2}}+1)\cdots(2^{2^1}-2^{2^0}+1)(2^{2^1}+2^{2^0}+1)$이다. 마지막 항이 각각 3과 7이 되어 모든 항이 1보다 큼을 알 수 있다.

위에서 인수분해한 결과에 따라 약수를 얼마나 가질 수 있는지 검사하려면 우선 $gcd(a^2+a+1,a^2-a+1)$이 어떻게 되는지 확인해야 한다. $gcd(a^2+a+1,a^2-a+1)=d$라 하자. $d|a^2+a+1$, $d|a^2-a+1$이므로 서로 뺀 값인 2a도 d의 배수이다. 그러나 $a(a+1)+1$과 $a(a-1)+1$ 모두 홀수이므로 모순이다. 따라서 d는 1이다.

즉, 인수분해된 각 항들의 관계는 서로소이고 ((k-1)-1+1)+1=k개 항을 가짐에 따라 주어진 식은 소수인 약수를 k개 갖는다.

양의 정수 m, n(m>n)에 대하여 $\frac{m^2-n^2}{2n}$이 1000보다 작은 소수가 될 때, $m-n$의 최솟값과 최댓값의 합을 구하여라

다른 자료를 참고한 결과 대부분 $\cfrac{m^2-n^2}{2n}=p^2 \ or \ p$로 가정하여 해결하지만 제곱수를 찾아야 하는 등 쉽지 않다. 따라서 다른 출처의 풀이과정을 인용하여 작성하기로 하였다.

문제에 제시된 수식이 합차공식의 형태를 띠고 있어 $(m+n)(m-n)$꼴로 표현되므로 $2n={(m+n)-(m-n)}$이라고 변형하자. 그러면 $(m+n)(m-n)={(m+n)-(m-n)}p$라고 할 수 있다. 그리고 $m+n=Ga$, $m-n=Gb$, $gcd(a,b)=1$라고 표현하여 위 식에 대입하면 $GaGb=G(a-b)p$가 되고 정리하면 $Gab=(a-b)p$가 된다. 앞에서 가정한 $gcd(a,b)=1$ 조건으로 인해 (a-b)|G, ab|p임을 알 수 있다. 그러나 p는 소수이고 $a>b$이므로 $a=p$, $b=1$이다. a, b값을 다시 대입하면 $Gp=(p-1)p$가 되어 $G=p-1$이고 모든 값을 m, n에 대입하였을 때 $m+n=p(p-1)$, $m-n=p-1$가 됨을 확인하였다.

$m-n$의 값이 최솟값이 되려면 p가 최소여야 한다. 그러나 p가 2일 경우 m, n은 정수라는 전제에 성립하지 않으므로 p가 3일 경우부터 검사한다. 그리고 m-n의 값이 최댓값이 되려면 p가 1000이하의 소수 중 가장 큰 값이 되어야 한다. 즉, p가 997인 경우부터 검사하면 된다.

• p가 3일 경우, $m=n+2$가 되고 $2n+2=6$이 되어 $n=2$, $m=4$가 성립한다. 따라서 $m-n$의 최소값은 2이다.

• p가 997일 경우 $m=n+996$이 되고 $2n+996=997\cdot996$이다. n에 대해 정리하면 $n=\cfrac{996^2}{2}$이고 $m=n+996$이 되어 양의 정수 조건을 만족한다.

따라서, $m-n$의 최솟값과 최댓값의 합은 998이다.

풀이 링크

작성에 도움이 된 자료

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