제 22 회 한국수학올림피아드 1차 시험 (중등부)

2008년 5월 24일 ; 제한시간 4시간

문제 19. 양의 정수 에 대하여, 인 정수 중에서 도 과 서로 소이고, 도 과 서로 소인 것들의개수를 이라 하자. 를 만족시키는 가장 큰 양의 정수 의 값을 구하여라.

풀이 : lemma : 은 곱산술함수이다.

서로소인 자연수 에 대하여 임을 보이면 된다.

1 부터 까지의 자연수 중 과 서로소인 의 순서쌍을 다음과 같이 나타내자.

그러면, 1 부터 까지의 자연수 중 과 서로소인 의 순서쌍은 다음과 같다.

과 이 서로소이므로, 위의 행렬에서 각각의 열인 꼴과 꼴들은 각각 법 에 대하여 기약완전잉여계이다. 따라서 각각의 열에 대하여 순서쌍의 두 수가 모두 과 서로소인 순서쌍의 개수는 개다. 따라서 위의 순서쌍에서 과 모두 서로소인 수들로 이루어진 순서쌍은 개씩, 개의 열이므로 이 된다. 따라서 서로소인 ㄷ 자연수 에 대하여 이다.

lemma : 소수 에 대하여, 이다.

1 부터 까지중 와 서로소인 이웃인 두 수의 순서쌍은 (1, 2) 부터 까지 개다. 이것이 회 반복되므로 개.

이제 문제로 돌아가자. 15 의 약수는 1, 3, 5, 15 이다. 이제 소인수의 거듭제곱 에 대하여 이 위의 약수들이 되는 와 을 찾자.

1) ⇔ 이므로 일 수 밖에 없다.

2) ⇔ 이다.

이면,

이면,

3) ⇔ 이다.

이면, 인데, 인 이 존재하지 않는다.

이면,

4) ⇔ 이다.

이면, 인데, 일 수 없다.

이면,

이면, 인데, 일 수 없다.

이면, .

15는 다음과 같이 네 가지로 표현할 수 있다.

15 = 1×15 = 3×5 = 1×3×5

각각의 경우 가 되게 하는 최대값은 5², 3×5², 3²×7, 3×5×7 인데, 이 중 가장 큰 값은 105 이다.

답 : 105