Ch5. Introduction to Number Theory

5.1 Divisors 나누는수

If n = d*k (k는 정수)로 표현된다면, d divide n이라고 표현할 수 있다.

📌 d divide n과 동치표현

• n is divisible by d
• d is a divisor of n
• n is a multiple of d
• d | n

⚡ 만약 d가 n을 나눌 수 없다면 d∤n 으로 표현함

⚡ 0은 0이 아닌 어떤 정수로도 나눌 수 있다.

📌 | 의 성질

1. d | n, d | m ⇒ d | n+m
2. d | n, d | m ⇒ d | n-m
3. d | m ⇒ d | mn

1번 증명과정은 다음과 같다. n = da, m = db ⇒ n+m = d(a+b) ⇒ d | n+m (2,3번도 비슷)

Prime 소수

1보다 큰 수 중에 1과 자기자신만이 나누는 수라면 소수(prime)다. / 그 외의 경우 모두 합성수(composite)

소수인지 아닌지 확인하는 방법

📌정리 : 2 ≤ d < √n 을 만족하는 d(n의 나누는 수)가 있을 경우 n은 합성수다!(iff)

• 반대로 없다면 n은 소수가 된다.
• 따라서, 2부터 시작해서 √n 까지의 정수를 하나씩 d에 대입해서 검사하면 된다.

⚡ 증명과정

• n = d*k라고 했을때 k도 나누는 수니까 나누는 수의 범위가 지정된다.

📌 따름정리 : 앞선 정리에서 조건에 맞는 d가 존재할 경우 n이 합성수라고 했는데, d가 소수인 경우만 검사하면된다. → 왜? d가 합성수라면 이미 그 전에 소수에서 나눠졌을거라서

🎯 예시