RMM11 P4

문제 링크

Community

문제.

 

\(n = p_{1}^{e_{1}}p_{2}^{e_{2}} \cdots p_{k}^{e_{k}}\)에 대해 \(\lambda(n)\)은 \((-1)^{e_1 + e_2 + \cdots e_k}\)로 정의된다. (Liouville's function) 다음을 증명하여라:

 

(a) \(\lambda(n) = \lambda(n+1) = 1\)인 \(n\)이 무한히 많다.

(b) \(\lambda(n) = \lambda(n+1) = -1\)인 \(n\)이 무한히 많다.

 

아이디어가 상당히 기초적이면서도 재밌다.

 

풀이.

(a)

편의를 위해, \(\lambda(n) = \lambda(n+1) = 1\)이 성립할 때 \((n,n+1)\)이 '조건을 만족한다'고 하자.

만약 조건을 만족하는 한 쌍에서 더 큰 또다른 쌍을 만들 수 있다면, 즉 \((n,n+1)\)이 조건을 만족할 때 \((f(n),f(n)+1)\)이 조건을 만족한다면 자명히 조건을 만족하는 쌍의 개수는 무한하다.

 

이 때 \(f(n) = 4n(n+1)\)로 잡으면,

- \(f(n)\)은 \(\lambda = 1\)인 3개의 수 \(4,n,n+1\)의 곱이므로 자명히 \(\lambda = 1\).

- \(f(n) + 1 = (2n+1)^2\)이므로 자명히 \(\lambda = 1\).

 

따라서 \((4n^2 + 4n, 4n^2 + 4n+1)\)도 조건을 만족함을 알 수 있다.

초기항으로, \((9,10)\)이 조건을 만족함을 알 수 있으므로 무한성이 보여진다.

 

(b)

반대로 \(\lambda(n-1) = \lambda(n) = -1\)이 성립할 때 \((n-1,n)\)이 '조건을 만족한다'고 하자.

이 경우는 조금 더 tricky하다. \((n,n+1)\) 대신 \((n-1,n)\)을 쓴 건 이유가 있다.

 

1) \(\lambda(n+1) = -1\)

이 경우 \((n,n+1)\)이 조건을 만족하므로 \((n-1,n)\)에서 \((n,n+1)\)을 만든 셈이다! 성립.

 

2) \(\lambda(n+1) = 1\)

이 때 \(\lambda(n(n+1)) = -1\)임을 알 수 있다.

이 때 만약 \(\lambda (n^2 + n + 1)\)도 -1이라면, \((n-1,n)\)에서 \((n^2 + n, n^2 + n + 1)\)을 만든 셈이다! 성립.

 

정말정말 운이 안좋아서 \(\lambda(n^2+n+1) = 1\)이라고 해보자. 그런데 저런 꼴의 식만 보면 \(n-1\)을 곱하고 싶어진다.

그렇다. \(\lambda(n^3 - 1) = \lambda(n-1)\lambda(n^2+n+1) = -1\)이다. 아싸!

\(\lambda(n^3) = \lambda(n)^3 = -1\)이다. 이번에는 실패하는 경우가 없다!

 

따라서 모든 case에 대해 더 큰 '조건을 만족하는 쌍'을 만들 수 있고, 초기항 \((2,3)\)이 존재하므로 조건을 만족하는 쌍의 개수는 무한하다.