개념지도 / 중등 / 수와 연산

소인수분해

prime factorization 중1 앞으로

수를 소수의 곱으로 유일하게 쪼개기

한 문장 직관 — 이것만 남으면 성공

소인수분해는 수의 유전자 검사다. 이 결과 하나로 약수의 개수, 최대공약수, 최소공배수가 전부 나온다.

소수 찾기 — 배수를 지우면 남는 것소인수분해는 그 수의 지문. 유일하게 하나뿐이다.

지우는 단계

2의 배수, 3의 배수… 차례로 지우면 더 이상 쪼개지지 않는 수만 남는다.

산술의 기본정리. 인수분해·암호의 뿌리

360=2³×3²×5. 약수 개수 = (3+1)(2+1)(1+1)=24

큰 수 하나(예: 1001)를 트리로 쪼개기 → 7×11×13. 어떤 순서로 쪼개도 결과 같음 확인

핵심 식

N = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}

유일 분해

d(N) = (a_1+1)(a_2+1)\cdots(a_k+1)

약수의 개수 — 각 소수를 0~aᵢ개 쓸 수 있으므로

✗ 큰 수는 소인수분해가 어렵지만 컴퓨터는 금방 한다.

왜 이렇게 생각하나
컴퓨터가 다 빠르다고 생각.

어떻게 깨뜨리나
600자리 두 소수의 곱을 되돌리는 건 현재 컴퓨터로 수억 년이 걸린다. 이게 RSA 암호의 근거다.

중3 인수분해(식을 쪼개기)로 이름과 아이디어가 그대로 넘어간다.