부등식 φ(30n+1) < φ(30n)을 만족하는 최소의 자연수

Euler totient function이라는 함수가 있다. 수론적 함수(arithmetic function)의 일종인데, 주어진 값 이하의 자연수 중에서 주어진 값과 서로 소인 것의 개수를 의미한다. 예를 들어, 8 이하의 자연수 중에서 8과 서로 소인 수는 1, 3, 5, 7 이므로 \phi(8) = 4 라고 할 수 있다.

Newman이라는 친구가 ad \ne bc 일 때, \phi(an + b) < \phi(cn + d) 를 만족하는 정수가 무한히 많음을 증명했다고 한다.[1] 근데 실제로 부등식 \phi(30n+1) < \phi(30n) 를 만족하는 수를 찾으려고 컴퓨터를 열라 돌려 계산해보니 2천만이 넘도록 답이 안 나오는 것이었다. 켁.

그리하여 Newman은 '아 이건 사람이 할 수 있는게 아니구나' 라고 생각할 즈음에 Martin이라는 친구가 위 부등식을 만족하는 최소의 정수가 다음의 수와 같다는 증명을 하였다.[2]

23290981017549679381404968420523378000485988596605123536334531107588
83445287231545279842601768958541826348029071092716104322876529769074
67574362400134090318355962121476785712891544538210966704036990885292
44615513567971756580806376638384622012060614382650943354025008511162
49704645413809344863756882089187506406746299424654993690365786403317
59035979369302685371156272245466396227865621951101808240692259960203
09133058929665688801179101141606263156532059377228711891372860899790
17912163561086654763060807401215282368886801201524791383274510884042
80929048314912122784879758304016832436751532255185640249324065492491
51107252158598054743874868930715936348123396580233172503366386261895
71689740435474488796632179710814456196187899854720743031003036360788
27273695551162089725435110246701964021045849081811604427331227553783
59082151009160756717884256957669954803821767317189538324932680066743
29935311864376599106328654198923709577221542663510398085481508288689
68820675198820381135523646361202383915218571017801463011491108784343
25328439351165025450659792396965361681389771062175669382747115470115
1222320443347408180047964860

켁 -_-;;;;;;;;;;;;;;;;; 이거 뭐야 -_- 무서워…

참고로 위 숫자는 이어져 있는 하나의 수이다. 이런 도깨비같은 수가 어떻게 나온건지 지금부터 증명해보겠다. ㅋㅋㅋ

 


part 1 > properties of Euler totient function
Euler totient function은 Euler \phi function 이라고도 불리는데, 주어진 자연수 이하의 수 중, 주어진 수와 서로 소인 자연수의 개수를 세는 함수이다. 예를 들어 9 이하의 자연수 중 9와 서로 소인 수는 1, 2, 4, 5, 7, 8과 같이 여섯 개이므로 \phi(9) = 6 이 된다. 이 함수는 각 자연수가 서로 소인지 일일이 체크하지 않고 다음과 같은 직접적인 공식을 통해 계산할 수 있다.

\displaystyle \phi(n) = n\prod_{p|n}\left(1-\frac{1}{p}\right)

주어진 수를 나누는 서로 다른 각 소인수에 대해 1-1/p 를 곱해주면 된다. 예를 들어 100의 경우 일일이 100개를 체크하지 않고 \phi(100) = 100(1 -1/2)(1-1/5) = 40 와 같이 계산할 수 있다.

그리고 서로 소인 두 수 a, b 에 대해 \phi(ab) = \phi(a)\phi(b) 가 성립한다.

이건 꽤 유명한 공식들이니 증명은 넘어가자. 사실 별로 어렵지도 않다. ㅋㅋ

part 2 > Claim 1
지금부터 문자와 정의를 잘 봐둬야 한다. 나중에 헷갈리더라 -_-
p_ii 번째 소수라고 가정하자. q = \prod_{i=r+1}^{r+s}p_i 라고 두고, m 은 소수 p_1 , \cdots , p_r 들로 나누어 떨어지지 않는 수라고 하면 다음 두 가지가 성립한다.

  1. m \le q 이면 m 은 많아야 s 개의 서로 다른 소인수를 가진다.
  2. m 이 많아야 s 개의 서로 다른 소인수를 가지면, \phi(m) / m \ge \phi(q) / q 가 성립한다.

part 2-1 > proof of Claim 1
첫 번째 것은 당연해 보인다. m \le q 인데도 p_r 이하의 소인수를 가질 수 없으니, q 보다 서로 다른 소인수를 더 가질 수 있을 리 만무하다.

두 번째 것은 위 part 1 에서 유도되는 다음의 식을 관찰하면 당연함을 알 수 있다. 즉,

\displaystyle \frac{\phi(m)}{m} = \prod_{p|m}\left(1-\frac{1}{p}\right)

m q 보다 소인수가 적으므로 곱하는 개수가 적고, 각각의 factor는 모두 \phi(q)/q 의 factor에 포함되므로 성립함을 알 수 있다.

part 3 > Claim 2
\phi(30n+1) < \phi(30n) 이 성립하면 다음 부등식이 성립해야 한다.

\displaystyle \frac{\phi(30n+1)}{30n+1} < \frac{4}{15} = 0.266666\cdots

part 3-1 > proof of Claim 2
part 1의 공식에서 \phi(ab) \le \phi(a)b 가 성립함을 알 수 있다. 그러므로 다음 일련의 부등식이 성립한다.

\displaystyle \frac{\phi(30n+1)}{30n+1} < \frac{\phi(30n)}{30n+1} < \frac{\phi(30)n}{30n} = \frac{4}{15}

part 4 > Claim 3
z = (p_4 p_5 \cdots p_{383})p_{385}p_{388} 이라고 하자. (인덱스를 주의깊게 보시라!)
그러면 z\phi(z)/z < 4/15z\equiv 1\pmod{30} 을 동시에 만족하는 가장 작은 자연수이다.

part 4-1 > proof of Claim 3
일단 \phi(z)/z 를 작게 만들 궁리를 해 본다. part 1의 식을 보면 알겠지만 수의 크기는 작으면서 소인수는 많은 수가 값이 작게 된다. 그러므로 컴퓨터를 열라 돌려서-_- 일단 4/15 직전까지 붙여본다.

part 4-2 > proof of Claim 3
\phi(m)/m < 4/15m\equiv 1\pmod{30} 을 동시에 만족하는 가장 작은 자연수를 m 이라 하자. 조건상 m 은 2, 3, 5를 인수로 가질 수 없다.
q_{1} = \prod_{i=4}^{384}p_i 라고 두면 (q_{1})/q_{1} = 0.26671\cdots 이 되어 간당간당하게 4/15보다 크다. 그러므로 \phi(q_{1} )/q_{1} > \phi(m)/m 이므로 Claim 1의 두 번째 성질에 r = 3, s = 383 을 대입하면 m 은 적어도 서로 다른 인수가 381개 보다 많아야 함을 알 수 있다.

part 4-3 > proof of Claim 3
그리하여 p_4 p_5 \cdots p_{382} 에 소인수 세 개를 추가로 더 곱해서 30 으로 나눈 나머지가 1이 되는 가장 작은 수를 직접 계산으로 확인한다. 컴퓨터의 노동력을 빌면 m = (p_4 p_5 \cdots p_{383})p_{385}p_{388} 임을 알 수 있다. 즉,

\displaystyle \frac{\phi(z)}{z} = \left(\prod_{i=4}^{383}\left(1-\frac{1}{p_i}\right)\right)\left(1-\frac{1}{p_{385}}\right)\left(1-\frac{1}{p_{388}}\right) = 0.2666117\cdots

part 5 > direction
그리하여 사실 n_1 = (z-1)/30 이 실제로 정답이라는 증명을 하고 싶은 것이다. 일단 이 수 이하의 자연수들은 Claim 3 에 의해 부등식 \phi((30n+1) < \phi(30n) 을 만족하는 해의 후보가 될 수 없다. 이제 마지막으로 \phi((30n_1 +1) < \phi(30n_1) 이 성립함을 보이면 된다.

part 6 > Claim 4

\phi((30n_1 +1) < \phi(30n_1)

part 6-1 > proof of Claim 4
컴퓨터의 도움으로 n_1 은 60 과 p_{4874} = 47279 을 인수로 가짐을 알 수 있다. n_2 = n_1 /(60p_{4874}) 라고 두면, n_2 는 첫 8만개의 소수로 나누어 떨어지지 않는다.

이제, q_2 = \prod_{i=80000}^{80186}p_i 라고 두면 q_2 는 1,118 자리수로서 1,116 자리수인 n_1 보다 크다. Claim 1의 두 번째 성질에 r=80000 , s=186 을 대입하면 \phi(n_2 )/n_2 \ge \phi(q_2)/q_2 가 성립하므로, 다음을 계산할 수 있다.

\displaystyle \frac{\phi(30n_1)}{30n_1} = \frac{\phi(30\cdot 60 p_{4874})}{30\cdot 60 p_{4874}}\cdot\frac{\phi(n_2)}{n_2} \ge \frac{4}{15}\left(1-\frac{1}{47279}\right)\frac{\phi(q_2)}{q_2} = 0.2666124\cdots

오오!! 이건 아주아주 미묘하게 \phi((30n_1 +1) /(30n_1 +1) 보다 더 크다. 그러므로 우리는

\displaystyle \frac{\phi(30n_1 +1)}{30n_1 +1} \le \frac{\phi(30n_1)}{30n_1}

임을 알 수 있다. 그러므로 \phi(30n_1 +1) < \phi(30n_1 ) (1+1/(30n_1 )) 가 되는데, n_1 이 워낙 무지막지하게 큰 수라서 (1+1/(30n_1 )) 정도로는 영향도 못 준다. [2]에는 소수점 이하 1,100자리까지 변화가 없다고 한다.

여하튼 그리하여 부등식 \phi((30n+1) < \phi(30n) 을 만족하는 가장 작은 자연수는
23290981017549679381404968420523378000485988596605123536334531107588
83445287231545279842601768958541826348029071092716104322876529769074
67574362400134090318355962121476785712891544538210966704036990885292
44615513567971756580806376638384622012060614382650943354025008511162
49704645413809344863756882089187506406746299424654993690365786403317
59035979369302685371156272245466396227865621951101808240692259960203
09133058929665688801179101141606263156532059377228711891372860899790
17912163561086654763060807401215282368886801201524791383274510884042
80929048314912122784879758304016832436751532255185640249324065492491
51107252158598054743874868930715936348123396580233172503366386261895
71689740435474488796632179710814456196187899854720743031003036360788
27273695551162089725435110246701964021045849081811604427331227553783
59082151009160756717884256957669954803821767317189538324932680066743
29935311864376599106328654198923709577221542663510398085481508288689
68820675198820381135523646361202383915218571017801463011491108784343
25328439351165025450659792396965361681389771062175669382747115470115
1222320443347408180047964860
이다. -_- Maple 로 간단하게 계산 결과를 확인할 수 있다.

 


[1] D. J. Newman, “Euler’s \phi function on arithmetic progressions”, Amer, Math, Monthly 104 (1997) 256-257
[2] Greg Martin, “The smallest solution of \phi(30n+1) < \phi(30n) is …”, Amer, Math, Monthly 106 (1999) 449-451

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중