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)$이 존재하므로 조건을 만족하는 쌍의 개수는 무한하다.