수학사랑쇼핑몰

HOME >수학나눔>묻고답하기

정수의 소수여부를 판정하는 필요충분 조건식을 제안합니다.

윤영규

Posted at 2008-11-21 13:25:33


다음글	1~9까지의 숫자를 더해 100만들기

이전글	gsp 그림을 한글로 옮기는 방법???

안녕하세요. 수학사랑 회원 윤영규입니다. 지난 10월 말에 자연수 중에서 3의 배수를 제외할 때, 5이상의 홀수에 대한 '합성수 일반식'과 소수(prime)여부를 판정하는 판별식으로 '소수규칙 3'을 온라인 사이트에 제안한 적이 있습니다. 그런데, 소수여부를 판정하는 판별식('h^2 - w^2 = 4u)이 필요조건이었고 판별식이 2원2차 부정방정식이어서 조건에 맞는 변수를 탐색하는데 번거로움이 있었습니다. 그런데 '소수규칙 3'의 판별식을 보다 단순화하는 필요충분 조건을 알게되어 이번에 그 내용을 올립니다. 새롭게 제안하는 '소수규칙 3-1'에 대해 많은 회원님들의 검토와 의견을 부탁드립니다.   서술을 위한 기본정보와 '소수규칙 3', 그리고 '소수규칙 3-1'을 아래에 먼저 배치하였고, 구체적 산출과정을 그 다음으로 배치하였습니다.        ** 내용 전개를 위한 기본 정보    ===============================================================  * 기본 정의 : Z는 정수의 집합    기호 정의 : 3^5 => 3의 5제곱수를 의미                a_2, b_n => 각각 두번 째 a항과 n번째 b항을 의미              <소수 규칙 1>(intrinsic prime increase rule) n∈Z(n>0)이고, 임의의 정수 p(p>3)가 소수일 때, p를 원소로 하는 소수의 집합을 P라 하면 P는 다음과 같은 집합 S의 부분집합이다.      S = {5, 7, 11, 13, 17,…,3n+2-(1+(-1)^n)/2,…}   (1)      * 위의 집합 S의 원소들 중에서 n번째 원소 a_n은 '확정된 소수'가 아니기에 불확정 소수'라는 이름을 붙였습니다.  ===============================================================  ===============================================================  < 불확정 소수 집합 S 속의 불확정 소수와 합성수들간의 관계식 >     * 기본 조건    c,k,m,n,d ∈ Z    c[k]_n ∈ S(S는 '불확정 소수' 집합)    c[k]_n = 3d + 2-(1+(-1)^d)/2           (2)    c[k]_n = (3k + 2-(1+(-1)^k)/2) * (3m + 2-(1+(-1)^m)/2) (단,k≤m)    1. k가 홀수인 경우   (1) n이 홀수일 때      d = 3k^2+ (3n+1)k + 2n-1        (3)   (2) n이 짝수일 때      d = 3k^2+ 3n·k + 2n-2          (4)  2. k가 짝수인 경우   (1) n이 홀수일 때      d = 3k^2+ (3n-1)k + n-1         (5)   (2) n이 짝수일 때      d = 3k^2+ 3n·k + n-1           (6)     * d가 뜻하는 의미   => d는 불확정 소수 집합 S의 원소인 임의의 합성수 c[k]_n이 집합 S 속에서   차지하는 원소로서의 위치를 나타내는 순서번호입니다.    예.. c[5]_2 = 17 * 19 = 323 이고 323은 불확정 소수집합 S에서 107번째 원소이므로 d = 107입니다.     ===============================================================  ===============================================================   <소수 규칙 3>  * 기본 정의 : Z는 정수의 집합               S는 '불확정 소수'의 집합  S = {5, 7, 11, 13, 17,…,3n+2-(1+(-1)^n)/2,…}       h,w,u∈Z(h>0,w≥0)이고 임의의 정수 u(u>3)가 u∈S일 때, u가 합성수이기 위한 필요조건은 다음              h^2  -  w^2 = 4u      (7)   을 만족하는 h와 w의 순서쌍 (h,W)가 2개 이상 존재하는 것이다.  ==============================================================  ** <소수규칙 3>에 대한 부연 설명   (7)을 만족하는 h 와 w의 순서쌍 (h,w)가 1개인 경우, 즉, h=u+1이고 w=u-1인 경우, 위에서 소수와 합성수의 관계식 (3)~(6)을 만족하는 양의 정수 k와 n이 존재하지 않게되며, 따라서 그 주어진 u가 합성수가 아니라 소수라는 판정을 내리게 됩니다.    ==============================================================  ** 이번에 새롭게 제안하는 내용입니다.   <소수 규칙 3-1>  * 기본 정의 : S는 '불확정 소수'의 집합    S = {5, 7, 11, 13, 17,…,3n+2-(1+(-1)^n)/2,…}       w,k∈Z(w≥0,k>0)이고 임의의 정수 u(u>3)가 u∈S일 때, u가 합성수이기 위한 필요충분조건은 다음     w = u/(3k+2) - (3k+2)  (단, k가 홀수일 때)      (8)   w = u/(3k+1) - (3k+1)  (단, k가 짝수일 때)      (9)   을 만족하는 w가 존재하는 것이다.  ==============================================================  ** (부연 설명) 위에서 (8) 또는 (9)를 만족하는 w가 존재할 때, 주어진 정수 u가 합성수이므로, 만약 (8)과 (9) 모두의 경우에서 해당 조건식을 만족하는 w가 존재하지 않는다면 주어진 정수 u는 소수라고 판정할 수 있습니다.   ** 아래는 '소수규칙 3-1'이 유도된 구체적 산출과정입니다     먼저 '소수규칙 3'을 다시 확인하면 다음     <소수 규칙 3>    * 기본 정의 : S는 '불확정 소수'의 집합    S = {5, 7, 11, 13, 17,…,3n+2-(1+(-1)^n)/2,…}     h,w,u∈Z(h>0,w≥0)이고 임의의 정수 u(u>3)가 u∈S일 때, u가 합성수이기 위한 필요조건은 다음            h^2 - w^2 = 4u      (10) 을 만족하는 h와 w의 순서쌍 (h,w)가 2개 이상 존재하는 것이다. 와 같습니다. (10)은 식을 변형하여 다음              (h + w)(h - w) = 4u   (11)   와 같이 나타낼 수 있습니다. g가 정수일 때,  h - w = g라 가정하면 h = w + g이고 (10)에 대입하면 다음             (w + g)^2  -  w^2  = 4u               2gw + g^2     = 4u   와 같습니다. 정리하여, w를 구하면 다음             w = 2u/g - g/2       (12)   와 같고, h = w + g이므로 h를 구하면 다음             h = 2u/g + g/2       (13)   와 같습니다. 만약 u가 합성수라면 a,b∈Z(a>0,b>0)일 때, u = ab로 표시할 수 있고 b를 기준으로 나타내면 다음        b = u/a  = 2u/2a        (14)   와 같습니다. (12),(13)에서 g는 임의의 정수가 가능하므로 ‘g = 2a’라 가정하면 (12),(13)은 다음             w = 2u/2a - 2a/2                       h = 2u/2a - 2a/2              와 같고, 정리하면 다음             w = u/a - a    (15)           h = u/a + a    (16)   와 같습니다. ‘u = ab’와 (14)의 관계식을 고려하여 (15),(16)을 변형하면 다음            w = b - a          (17)          h = b + a          (18)   와 같습니다. 여기서 k,m∈Z(k>0,m>0),a_k,a_m∈S(S는‘불확정소수’집합)일 때, 합성수의 일반식을 상기하면 u가 합성수라는 조건에서, u는 다음               u = c[k]_n = a_k·a_m(k≤m)   와 같이 표시할 수 있고, c[k]_n은 k와 n의 홀수짝수 조건에 따라서 다음   1. k가 홀수인 경우   (1) n이 홀수일 때      c[k]= (3k+2)(3n+3k-1)          (19)   (2) n이 짝수일 때      c[k]= (3k+2)(3n+3k-2)          (20)  2. k가 짝수인 경우   (1) n이 홀수일 때      c[k]= (3k+1)(3n+3k-2)          (21)   (2) n이 짝수일 때      c[k]= (3k+1)(3n+3k-1)          (22)   와 같이 표시됩니다. 앞에서 u는 합성수이고 u = ab라 가정하였으므로 (19)~(22)과 비교할 때, a는 k의 홀수, 짝수 조건에 따라서 다음                  a = 3k + 2 (k가 홀수일 때)   (23)                a = 3k + 1 (k가 짝수일 때)   (24)   의 관계를 가집니다. (23),(24)의 관계식을 (15),(16)에 적용하여 h와 w를 구하면 다음  ============================================================== 1. k가 홀수인 경우           w =  u/(3k+2) - (3k+2)       (25)           h =  u/(3k+2) + (3k+2)       (26) 2. k가 짝수인 경우           w =  u/(3k+1) - (3k+1)       (27)           h =  u/(3k+1) + (3k+1)       (28)  ============================================================== 와 같습니다. 또한 u = ab일 때, 위의 (17),(18)에서 h = b+a, w = b-a이므로 (19)~(22)에 적용하여 h와 w를 구하면 다음  ==============================================================  1. k가 홀수인 경우   (1) n이 홀수일 때                    (29)      h = 6k + 3n +1            w = 3n - 3   (2) n이 짝수일 때                    (30)      h = 6k + 3n              w = 3n - 4  2. k가 짝수인 경우                    (31)   (1) n이 홀수일 때      h = 6k + 3n - 1          w = 3n - 3   (2) n이 짝수일 때                    (32)      h = 6k + 3n             w = 3n - 2  ============================================================== 와 같은 관계식이 산출됩니다. 위에서 (25)~(28)의 h,w,k 사이의 관계식을 활용하여 앞에서 제안안 <소수규칙 3-1>이 제안되었습니다. (25)~(28)에서 w와 h는 우변의 첫째항에서 동일한 분모를 가지고 있으므로 만약 w가 정수라면, h도 정수가 산출됨을 알 수 있습니다. 따라서 w가 정수라는 조건만을 가지고 <소수규칙 3-1>을 만들 수 있습니다. (25)~(28)에서 h^2과 w^2를 구하여 계산하면 'h^2 - w^2 = 4u'임을 확인할 수 있습니다. <소수규칙 3-1>을 이용하여 k와 w가 결정되면 위의 (29)~(32)를 이용하여 n을 찾을 수 있고, 따라서 합성수 c[k]_n을 결정할 수 있게 됩니다.  ==============================================================     ** 소수결정을 위한 탐색범위    w,k∈Z(w≥0,k>0)일 때, <소수규칙 3-1>에서 주어진 정수 u(u>3,u∈S)의 소수(prime) 여부를 판정하는 관계식을 다시 확인하면 다음      w = u/(3k+2) - (3k+2)   (단, k가 홀수일 때)           w = u/(3k+1) - (3k+1)   (단, k가 짝수일 때)       와 같습니다. 위의 관계식에서 우변의 첫째항과 둘째항의 연산관계는 ‘뺄셈’의 관계이고, 첫째항은 ‘3k+2' 또는 ’3k+1'을 분모로 가지는 형태이므로 양의정수 k가 k=1,2,3,4,… 등으로 증가함에 따라서 w는 일정 시점에서 음수의 형태로 전환됨을 알 수 있습니다. w는 '0'이거나 양의 정수라는 조건을 가지므로 주어진 정수 u의 소수여부를 판정하기 위한 k의 탐색범위는 w가 음수가 되기 전까지의 양의정수 k로 범위를 한정지을 수 있습니다.      예를 들어, 정수 989의 소수판정을 위한 k의 탐색개수는 홀수 5개, 짝수 5개 등 총 10개입니다. 그런데 에라토스테네스 방식의 탐색범위는 (989)^(1/2) = 31.44837 이므로 약 31개의 탐색범위를 갖습니다. 따라서 위의 <소수규칙3-1>에 의한 탐색효율성은 10/31 = 0.32258 이므로 에라토스테네스 방식보다 탐색범위를 약 67% 감소시킨 것에 해당합니다.       이번에 새롭게 제안한 '소수규칙 3-1'은 임의의 정수에 대해 소수(prime)여부를 단 하나의 필요충분 조건식으로 판별할 수 있다는 것에 유용성이 있다고 할 수 있습니다. 또한 앞에서 살펴본 것처럼 소수판정을 위한 탐색범위를 줄인 것에서도 효용성을 찾을 수 있다고 생각합니다. 회원님들의 자유로운 의견을 기다리겠습니다.

ㆍ총구매액	0 원
ㆍ적립금	0 원
ㆍ할인쿠폰	0 원

ㆍ장바구니	0 개
ㆍ위시리스트	0 개