09-29 07:02
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- BFS
- selenium
- literal
- Unity
- 리눅스 기초
- Polymolphism
- 리눅스 마스터 1급
- 백준
- Inheritance
- Reference Type
- 자바
- Mac
- Operator
- python
- preprocessing
- X윈도우
- Binary Search
- X.org
- Java
- 셀레니움
- 리눅스
- OOP
- zsh
- Class
- Physical Scheme
- Entity Set
- Entity
- systemd
- External Scheme
- dbms
Archives
- Today
- Total
Byeol Lo
[Number Theory] Divisibility 본문
나누어 떨어지는 것을 중학교 때 배웠을 것이다. 정수 5가 10을 나눌 수 있다 라는 명제는 참이며, 이를 식으로 나타낼 수 있는 어떤 relationship 이 필요할 것이다. 여기서는 나누어 떨어짐을 고급스럽게 표현하는 방법과 성질들을 배운다.
Divisibility
∀ 𝑎, 𝑏 ∈ ℤ, (∃ 𝑐 ∈ ℤ, 𝑏 = 𝑎𝑐) ⇒ ( 𝑎 | 𝑏 ) ∨ ( "𝑎 가 𝑏 를 나눈다." ) ∨ ( "𝑎 는 𝑏 의 약수이다, 혹은 약수로 가진다." )
간단하게 b = ac 꼴로 나타낼 수 있으면 a 가 b 를 나눌 수 있다.
Tautology
- 0의 약수는 모든 정수이다.
- 1은 모든 정수의 약수이다.
- 0이 아닌 모든 정수는 자기 자신을 약수로 가진다.
- 1의 약수는 1, 0, -1 뿐이다.
Theorem
∀ 𝑎, 𝑏, 𝑐 ∈ ℤ 에 대해 다음이 성립한다.
- 𝑎 | 𝑎 (반사율, Reflexivity) ∵ a = a * 1 이므로 정수 1이 존재 ■
- 𝑎 | 𝑏 ∧ 𝑏 | 𝑐 ⇒ 𝑎 | 𝑐 (추이률, Trasitivity) ( ∵ ∃ k ∈ ℤ, b = ak 이고, ∃ r ∈ ℤ, c = br 이므로 ∃ t = kr ∈ ℤ, c = at ■)
- (𝑎 | 𝑏) ∧ (𝑏 ≠ 0) ⇒ | 𝑎 | ≤ | 𝑏 | ( ∵ b = ak 인 정수 k 존재, 따라서 |b| = |ak| ≥ |a||k| ≥ |a||1| = |a| ■)
- 𝑎 | 𝑏 ∧ 𝑎 | 𝑐 ⇒ ∀ 𝑠, 𝑡 ∈ ℤ, 𝑎 | 𝑠𝑏 ± 𝑡𝑐 ( ∵ b = ax, c = ay 이므로 sb + tc = asx + aty = a (sx + ty) ■)
- 𝑎 | 𝑏 ∧ 𝑎 | (𝑏 ± 𝑐) ⇒ 𝑎 | 𝑐 ( ∵ b = ak, b±c = ar 이므로 b±c - b = ar - ak = a (r-k) ■)
- 𝑎 | 𝑏 ∧ 𝑏 | 𝑎 ⇒ | 𝑎 | = | 𝑏 | ( ∵ a = bk ∧ b = ar ⇒ ar = rbk = akr^2 ⇒ r = kr^2 ⇒ 1 = kr, 이때 k와 r은 각각 1, 1 혹은 -1, -1 밖에 안된다. ■)
- 𝑐 ≠ 0 ∧ 𝑎 | 𝑏 ⇒ 𝑐𝑎 | 𝑐𝑏
- 𝑎 | 𝑏 ∧ 𝑏 ≠ 0 ⇒ 𝑏/𝑎 | 𝑏
Notation
한자리 정수 𝑎_𝑛, ..., 𝑎_0에 대해, 10^n * 𝑎_𝑛 + ... + 𝑎_0 을 다음과 같이 표기한다. $ \overline{\textit{a}_{n} \textit{a}_{n-1} \dots \textit{a}_{1} \textit{a}_{0}} $
Divisibility Rule
다음은 배수 판정법이다. $ N = \overline{\textit{a}_{n} \textit{a}_{n-1} \dots \textit{a}_{1} \textit{a}_{0}} $ 일때, 다음을 만족한다(나오는 모든 문자는 정수임을 가정하고, 3, 7, 11)에 대해서만 보자.
- $ 3 | ( \textit{a}_{0} + \textit{a}_{1} + \dots + \textit{a}_{n}) ⇒ 3 | 9 × 10^{n-1} × \textit{a}_{n} + ... + 9 × \textit{a}_{1} + \textit{a}_{0} $
- 7의 배수는 원리를 통해 보자. 7 | 1001 이므로, $ k (= n, n-1, n-2), 7 | \textit{a}_{k} - \textit{a}_{k-3} + \textit{a}_{k-6} + \dots $ 이면 된다.
- 11의 배수 또한 $ \overline{\textit{a}_{1} \textit{a}_{0}} $ 에서 $ 11 × \textit{a}_{1} $을 빼준 것이 11의 배수이면 되는 것을 알 수 있으므로 $ 11 | \textit{a}_{1} - \textit{a}_{0} $ 이면 된다. 확장시켜서, $ 11 | (\textit{a}_{n} - \textit{a}_{n-1} + \textit{a}_{n-2} - \textit{a}_{n-3} + \dots ) $ 이면 된다.
나머지는 위키를 참고하자.
https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95
'Math > Number Theory' 카테고리의 다른 글
[Number Theory] GCD, 유클리드 호제법 (0) | 2024.07.13 |
---|---|
[Number Theory] Well-Ordering Principle (0) | 2024.07.13 |
Comments