올림피아드 정수문제 접근법
1. "소수"단위로 생각해보자. 소수는 많은 정수론적 성질을 가진다. 2. 제곱수는 나머지 분류를 생각해보자. 3. 베주항등식은 매우 유용한 결과물이다. 정수 \(a, b\)에 대해 항상 다음 식을 만족하는 정수 \(x, y\)가 존재한다는 명제이다. $$ ax+by=gcd(a,b) $$ 4. 다루기 까다로운 함수들은 작은 문제부터 시작해보자. (최소공배수, 약수의 개수 등) 5. 페르마 소정리(!!), 오일러 정리를 잘 쓰자. 6. 거듭제곱과 mod로 1, -1인 경우 위수와 원시근등을 고려해보자. 7. 약수, 배수문제를 풀 때, 최대지수를 파악하는게 유용하다. 특히 고난도문제에서 LTE Lemma도 알아두자. (증명 필요) 8. 역원을 곱하여 문제를 간단히 해보자. (단, 역원이 존재할 조건, 서로소..
2024. 2. 11.
어려운 정수론 문제 2개
문제1: 소수 \(p\)와 양의 정수 \(a_1, a_2, ... , a_p\)에 대하여 다음 조건을 만족하는 양의 정수 \(k\)가 존재함을 보여라. $$ a_1+k, a_2+2k, ... , a_p+pk $$ 를 \(p\)로 나눈 나머지들이 적어도 \(p/2\)개 이상의 서로 다른 값를 갖는다. [2018 USAMO P4] (sol) 더보기 \(k=1, 2, ... , p\)에 대해 무향그래프 \(G=G_1, G_2, ... , G_p\) 를 구성하자. \(a_i\)에 해당하는 점을 \(i\)로 둔다. \(a_i+ik\equiv a_j+jk \quad(\textup{mod} \; p) \)를 만족하면 점 \(i\)와 \(j\)를 잇는다. (단, \(i < j\)) 이 때, $$ a_i+ik\equiv..
2023. 12. 26.