서로소 생성 다항식

2018년 창의적수학탐구대회에 보고서로 제출한 내용이다. 물론 최우수상을 타냈다.

I. 탐구주제

오일러가 찾아낸 이차식x2+x+41은 −40≤x≤39인 정수 x에 대해 소수를 만들어낸다. 이는 불규칙하기로 악명 높은 소수에서 불가사의한 질서를 보여준다. 한편, 이 이차식은 특정한 범위 밖에 정수 x를 대입했을 때는 항상 소수가 나오지는 않는다. 오일러의 제자 르장드르는 항상 소수를 생성하는 다항식은 존재하지 않는다고 증명했다. 그러나 특정 정수와 서로소인 정수를 생성하는 다항식은 무한히 써내려갈 수 있다. 본 탐구에서는 6과 서로소인 정수를 생성하는 모든 이차식을 알아내는 방법을 찾고 나아가 임의의 정수와 서로소인 정수를 생성하는 다항식을 알아내는 방법을 찾는다.

II. 탐구목적

  1. 6과 서로소인 정수를 생성하는 이차식을 알아내는 방법을 찾는다.
  2. 임의의 정수와 서로소인 다항식을 알아내는 알고리즘을 작성한다.

III. 탐구방법

  1. 6의 소인수는 2와 3 뿐이므로, 임의의 정수 x에 대해 x가 6과 서로소라는 것은 x가 2로 나누어떨어지지 않고 3으로 나누어떨어지지 않는다는 것과 동치다.
  2. 2로 나누어떨어지지 않는 정수를 생성하는 이차 이하 다항식을 알아낸다.
  3. 3으로 나누어떨어지지 않는 정수를 생성하는 이차 이하 다항식을 알아낸다.
  4. 6과 서로소인 정수를 생성하는 이차식을 알아낸다.
  5. 앞의 탐구를 토대로 임의의 정수와 서로소인 정수를 생성하는 다항식을 알아내는 알고리즘을 작성한다.

IV. 탐구내용

본 탐구에 구하는 조건에 부합하는 다항식을 모두 늘어놓는 것은 무의미하며 가능하지도 않다. 앞에서 밝혔듯 임의의 정수와 서로소인 이차 이하 다항식의 개수가 무한하기 때문이다. 따라서 본 탐구에서는 최소한의 다항식을 구하고, 구하는 조건의 모든 다항식을 일정한 규칙에 따라 생성할 수 있음을 보일 것이다.

본격적인 탐구에 앞서 나머지의 정의와 특성 등을 알아둔다.

정수 n과 자연수 m에 대해 다음 식을 성립시키는 r, q(r, q는 정수, 0≤r<m)가 유일하게 정해진다.

n=mq+r

이때 n을 m으로 나눈 나머지가 r이다.

이하 a와 b를 각각 m으로 나눈 나머지가 같다는 뜻으로 다음 기호를 사용한다. 이 기호는 일반적으로도 그런 뜻으로 쓰인다.

a≡b(mod m)

정수 a, b를 자연수 m으로 나눈 나머지 r, s에 대해 다음이 성립한다.

a±b≡r±s(mod m)
a×b≡r×s(mod m)

그러므로 정계수 다항식 P(x)에 대해 P(x)의 계수들을 각각 m으로 나눈 나머지와, a를 m으로 나눈 나머지 r만 알고 있으면, P(a)를 m으로 나눈 나머지를 구할 수 있다. 한편 m으로 나눈 나머지가 r인 정수 n는 다음의 식으로 모두 구할 수 있다.

n=mq+r
q는 임의의 정수

따라서 본 탐구에서는 m으로 나눈 나머지에 대한 탐구에서, 0 이상 m 미만인 정수 계수를 가지는 P(x)만을 구한다.

이차식 P(x)는 x에 x+(어떤 정수)를 대입하여 일차항의 계수를 단순하게 만들 수 있다. 본 탐구에서 구한 이차식의 일차항의 계수가 복잡한 경우 단순화하여 사용하기로 한다.

이제 본격적인 탐구를 시작한다.

1. 2로 나누어떨어지지 않는 정수를 생성하는 이차 이하 다항식

구하는 다항식을 ax2+bx+ca, b, c는 정수, 0≤a,b,c<2라 한다. P(x)가 2로 나누어떨어지지 않는 정수만을 생성하려면 0≤n<2에 대해 P(n)이 2로 나누어떨어지지 않아야 한다.

P(0)=c≡1(mod 2)
P(1)=a+b+c≡1(mod 2)
∴c=1
a+b≡0(mod 2)
∴
a=0
b=0
or
a=1
b=1

∴P(x)=1 or P(x)=x2+x+1

이때 2로 나누어떨어지는 정수만을 생성하는 다항식을 Q(x)=a′x2+b′x+c′a′, b′, c′는 정수, 0≤a′,b′,c′<2라 하면 Q(x)는 다음과 같이 구해진다.

Q(0)=c′≡0(mod 2)
Q(1)=a′+b′+c′≡0(mod 2)
∴c′=0
a′+b′≡0(mod 2)
∴
a′=0
b′=0
or
a′=1
b′=1
Q(x)=0이 될 수 있다는 것은 자명하다.

x2+x+1은 사실 (x2+x)+1=Q(x)+P(x)로 나타낼 수 있다. 이 사실은 3단계에서 유용하게 쓰인다.

2. 3으로 나누어떨어지지 않는 정수를 생성하는 이차 이하 다항식

구하는 다항식을 P(x)=ax2+bx+ca, b, c는 정수, 0≤a,b,c<3라 한다. P(x)가 3로 나누어떨어지지 않는 정수만을 생성하려면 0≤n<3에 대해 P(n)이 3으로 나누어떨어지지 않아야 한다.

P(0)=c
P(1)=a+b+c
P(2)=4a+2b+c≡a+2b+c(mod 3)

따라서 c, a+b+c, a+2b+c가 3으로 나누어떨어지지 않아야 한다. 즉 나머지가 1 또는 2가 되어야 하는데 이렇게 경우를 여러 번 나누어야 할 때에는 표를 그리는 것이 유용하다.

a 0 1 2
cb 012 012 012
1 OXX OXX XOO
2 OXX XOO OXX

따라서 P(x)는 1, 2, x2+1, x2+x+2, x2+2x+2, 2x2+x+1, 2x2+2x+1, 2x2+2 이다. 여기에서 x22x+2=(x+1)2+1으로, x2+1과 같은 형태이므로 생략한다. 한편 3으로 나누어떨어지는 정수만을 생성하는 이차 이하 다항식 Q(x)를 1단계와 같은 방법으로 구하면 Q(x)=0뿐이다.

3. 6과 서로소인 정수를 생성하는 이차 이하 다항식

구하는 다항식을 P(x)=ax2+bx+ca, b, c는 정수, 0≤a,b,c<6이라 한다. 6과 서로소인 정수를 생성한다는 조건은 2로 나누어떨어지지 않으면서 3으로 나누어떨어지지 않는 정수를 생성한다는 조건과 동치이므로, m으로 나누어떨어지지 않는 정수를 생성하는 다항식 Pm(x), m으로 나누어떨어지는 정수를 생성하는 다항식 Qm(x)에 대해 P(x)를 다음과 같이 나타낼 수 있다.

P(x)=
P2(x)+q0Q2(x)+2q1x2+2q2x+2q3
P3(x)+q4Q3(x)+3q5x2+3q6x+3q7
qi는 임의의 정수

모든 P2(x)와 P3(x)에 대해 경우를 나누어 P(x)를 구한다. 단, P2(x)=x2+x+1=q2(x)+1이므로 P2(x)=x2+x+1은 생략한다.

P2(x) 1
P3(x)
11
25
x2+1 x2+3x+1
x2+x+2 x2+x+5
2x2+x+1 2x2+4x+1
2x2+2x+1 2x2+2x+1
2x2+2 2x2+5

이 중 단순화할 수 있는 다항식을 단순화한다.

x2+3x+1
=(x+32)2−54
⇒(x+12)2−54=x2+x−1
≡x2+x+5(mod 6)
2x2+4x+1
=2(x+1)2−1
⇒2x2−1
≡2x2+5(mod 6)

따라서 P(x)는 1, 5, x2+x+5, 2x2+2x+1, 2x2+5이다. 한편 6으로 나누어떨어지는 정수만을 생성하는 다항식 Q(x)는 Q2(x), Q3(x)를 이용해 만들 수 있다.

Q3(x) 0
Q2(x)
00
x2+x3x2+3x

표를 이용해 계산한 결과 Q(x)는 0, 3x2+3x이다. 결국 6과 서로소인 정수만을 생성하는 이차 이하 다항식은 다음의 식으로 만들 수 있다.

P(x+q0)+q1Q(x+q2)+6q3x2+6q4x+6q5
qi는 임의의 정수

이때 P(x)는 1, 5, x2+x+5, 2x2+2x+1, 2x2+5, Q(x)는 0, 3x2+3x이다.

4. 임의의 정수 m과 서로소인 정수만을 생성하는 다항식

  1. m의 소인수 p0, p1, p2 …를 알아낸다.

  2. 각각의 pi에 대해 pi로 나누어떨어지지 않는 정수만을 생성하는 다항식 Ppi(x)를 다음과 같은 방법으로 구한다.

    1. Ppi(x)의 계수를 다음과 같이 변수로 나타낸다.

      Ppi(x)=anxn+an−1xn−1+…+a2x2+a1x+a0

    2. 0≤k<pi에 대해 Ppi(k)를 전개한다.

      Ppi(0)=a0
      Ppi(1)=an+an−1+…+a2+a1+a0
    3. 표 등을 이용해 2번에서 전개한 식들이 모두 m으로 나누어떨어지지 않게 하는 ai의 조합을 구한다.
    4. 단순화할 수 있는 다항식들을 단순화한다.
  3. 각각의 pi에 대해 pi로 나누어떨어지는 정수만을 생성하는 다항식 Qpi(x)를 2번과 같은 방법으로 구하되, 2.3번에서 m으로 나누어떨어지게 하는 ai의 조합을 구한다.

  4. 모든 pi에 대해 다음을 만족하는 P(x)를 표 등을 이용해 찾고 단순화한다.

    P(x)=Ppi(x)+qQpi(x)+piR(x)
    q는 임의의 정수, R(x)는 임의의 정계수 다항식

  5. 모든 pi에 대해 다음을 만족하는 Q(x)를 표 등을 이용해 찾는다.

    Q(x)=q0Q′0(x)+q1Q′0+…
    qi는 임의의 정수, Q′j(x)는 임의의 Qpi(x)

  6. 앞의 결과들을 이용하면 다음 식으로 m과 서로소인 정수를 생성하는 모든 다항식을 구할 수 있다.

    P(x+q0)+Q(x+q2)+mR(x)
    qi는 임의의 정수, R(x)는 임의의 정계수다항식

5. 결론 및 제안

본 탐구에서는 6과 서로소인 정수를 생성하는 이차 이하 정계수 다항식을 구해보고, 그 과정에서 사용한 방법을 토대로 임의의 정수와 서로소인 정수를 생성하는 다항식을 구하는 방법을 알아보았다. 사실 6과 서로소라는 조건은 2로 나누어떨어지지 않고, 3으로도 나누어떨어지지 않는다는 조건을 단순히 한 것이다. 2와 3을 제외한 모든 소수는 2, 3으로 나누어떨어지지 않는다. 따라서 2, 3으로 나누어떨어지지 않는 수만을 추려내면 그 중 상당량의 소수가 있을 것이라고 유추할 수 있다. 나아가 2, 3, 5, 7 등 더 많은 소수로 나누어떨어지지 않는 수를 추리면 소수의 비율은 더욱 커질 것이다. 이는 ‘울람 나선’으로 확인되기도 한다.

울람 나선은 소수를 일정한 규칙에 따라 시각적으로 나타내 신비한 규칙성을 발견한 것이다. 울람 나선을 그리려면 중앙의 점을 1로 설정하고 나선 모양으로 돌아가며 각 점에 번호를 매긴다. 그리고 소수 번호가 매겨진 점을 색칠하면 첫번째 그림과 같은 무늬가 만들어진다.

울람 나선1
울람 나선2

두번째 그림과 같이 계속 나선을 그려나가면 사선이 더욱 뚜렷이 보이는 것을 확인할 수 있다. 여기에서 각 사선은 특정한 이차식을 나타낸다. 예를 들어 그림에 표시된 파란 사선은 x2+x+41에 짝수를 대입한 번호의 점들이다. 한편 x2+x+41은 x에 어떤 값을 대입해도 37 이하의 소수로는 나누어떨어지지 않는다. 본 탐구에서는 2, 3으로 나누어떨어지지 않는 다항식까지만 구했다. 2, 3, 5, 7 등 더 많은 소수로 나누어떨어지지 않는 다항식은 더 많은 소수를 생성할 것이며, 이는 울람 나선으로 확인 가능할 것이다.

6. 참고자료

이 글을 쓰기가 이렇게 어려운 것은 수학의 잘못은 아닐테다... 그래, 복사가 안 되는 한컴 탓으로 해두자.

글 목록
크리에이티브 커먼즈 라이선스
이 저작물은 크리에이티브 커먼즈 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용할 수 있습니다.