[Number Theory] Divisibility

 나누어 떨어지는 것을 중학교 때 배웠을 것이다. 정수 5가 10을 나눌 수 있다 라는 명제는 참이며, 이를 식으로 나타낼 수 있는 어떤 relationship 이 필요할 것이다. 여기서는 나누어 떨어짐을 고급스럽게 표현하는 방법과 성질들을 배운다.

 

Divisibility

∀ 𝑎, 𝑏 ∈ ℤ, (∃ 𝑐 ∈ ℤ, 𝑏 = 𝑎𝑐) ⇒ ( 𝑎 | 𝑏 ) ∨ ( "𝑎 가 𝑏 를 나눈다." ) ∨ ( "𝑎 는 𝑏 의 약수이다, 혹은 약수로 가진다." )

간단하게 b = ac 꼴로 나타낼 수 있으면 a 가 b 를 나눌 수 있다.

 

Tautology

• 0의 약수는 모든 정수이다.
• 1은 모든 정수의 약수이다.
• 0이 아닌 모든 정수는 자기 자신을 약수로 가진다.
• 1의 약수는 1, 0, -1 뿐이다.

 

Theorem

∀ 𝑎, 𝑏, 𝑐 ∈ ℤ 에 대해 다음이 성립한다.

1. 𝑎 | 𝑎 (반사율, Reflexivity) ∵ a = a * 1 이므로 정수 1이 존재 ■
2. 𝑎 | 𝑏 ∧ 𝑏 | 𝑐 ⇒ 𝑎 | 𝑐 (추이률, Trasitivity) ( ∵ ∃ k ∈ ℤ, b = ak 이고, ∃ r ∈ ℤ, c = br 이므로 ∃ t = kr ∈ ℤ, c = at ■)
3. (𝑎 | 𝑏) ∧ (𝑏 ≠ 0) ⇒ | 𝑎 | ≤ | 𝑏 | ( ∵ b = ak 인 정수 k 존재, 따라서 |b| = |ak| ≥  |a||k| ≥ |a||1| = |a| ■)
4. 𝑎 | 𝑏 ∧ 𝑎 | 𝑐 ⇒ ∀ 𝑠, 𝑡 ∈ ℤ, 𝑎 | 𝑠𝑏 ± 𝑡𝑐 ( ∵ b = ax, c = ay 이므로 sb + tc = asx + aty = a (sx + ty) ■)
5. 𝑎 | 𝑏 ∧ 𝑎 | (𝑏 ± 𝑐) ⇒ 𝑎 | 𝑐 ( ∵ b = ak, b±c = ar 이므로 b±c - b = ar - ak = a (r-k) ■)
6. 𝑎 | 𝑏 ∧ 𝑏 | 𝑎 ⇒ | 𝑎 | = | 𝑏 | ( ∵ a = bk ∧ b = ar ⇒ ar = rbk = akr^2 ⇒ r = kr^2 ⇒ 1 = kr, 이때 k와 r은 각각 1, 1 혹은 -1, -1 밖에 안된다. ■)
7. 𝑐 ≠ 0 ∧ 𝑎 | 𝑏 ⇒ 𝑐𝑎 | 𝑐𝑏
8. 𝑎 | 𝑏 ∧ 𝑏 ≠ 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)에 대해서만 보자.

1. $ 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} $
2. 7의 배수는 원리를 통해 보자. 7 | 1001 이므로, $ k (= n, n-1, n-2), 7 | \textit{a}_{k} - \textit{a}_{k-3} + \textit{a}_{k-6} + \dots $ 이면 된다.
3. 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

배수 판정법 - 위키백과, 우리 모두의 백과사전