올림피아드 정수문제 접근법

 

 

1. "소수"단위로 생각해보자. 소수는 많은 정수론적 성질을 가진다. 

 

2. 제곱수는 나머지 분류를 생각해보자.

 

3. 베주항등식은 매우 유용한 결과물이다.

   정수 \(a, b\)에 대해 항상 다음 식을 만족하는 정수 \(x, y\)가 존재한다는 명제이다.

          $$ ax+by=gcd(a,b) $$

 

4. 다루기 까다로운 함수들은 작은 문제부터 시작해보자. (최소공배수,  약수의 개수 등)

 

5. 페르마 소정리(!!), 오일러 정리를 잘 쓰자. 

 

6. 거듭제곱과 mod로 1, -1인 경우 위수와 원시근등을 고려해보자. 

 

7. 약수, 배수문제를 풀 때, 최대지수를 파악하는게 유용하다. 특히 고난도문제에서 LTE Lemma도 알아두자. (증명 필요)

 

 

8. 역원을 곱하여 문제를 간단히 해보자. (단, 역원이 존재할 조건, 서로소는 잊지 말자)

 

 

9.  논리적 서술에서 최소성을 만족하게 잡는 테크닉은 매우 자주 쓰인다. 

 

 

10.  이차대칭식의 나누어떨어짐 문제는 비에타 점핑 테크닉을 써보자.

 

 

11. 겉보기와 다르게 매우 어려울 수 있으니 잘 피해가자