[Mathematics for Computer Science][Division Algorithm] 스터디 07

The Division Algorithm

If one number does not evenly divide another, then there is a remainder" left over. More precisely, if you divide n by d, then you get a quotient q and a remainder r.

어떤 수가 나누어지지 않을 때 (즉 소수일 때?) 그 수는 나머지를 가진다. 그리고 몫도 알 수 있다. 이 말은 y = ax + b가 된다는 말.

Theorem 25 (Devision Algorithm)

Let n and d be integers such that d 0. Then there exists a unique pair of integers q and r such that n = qd + r and 0 ≤ r   d. 위의 y = ax + b와 비슷한 말이다. 여기서 문제는 저 여기서 a와 b의 조합이 단 하나라는 점이다. 어째서 그러한 지 보자. Proof. We must prove that the integers q and r exist and that they are unique.

For existence, we use the well-ordering principle. Fisrt, we show that the equation n = qd + r holds for some r ≥ 0. If n is positive, then the equation holds when q = 0 and r = n. If n is not positive, then the equation holds when q = n and r = n(1-d) ≥ 0. Thus, by well-ordering principle, there must exist a smallest r ≥ 0 such that the equation holds. Furthermore, r mush be less than d; otherwise, b = (q +1)d + (r-d) would be another solution with a smaller nonnegative remainder, contradicting the choice of r.

Well-ordering Principle 자연수의 정렬성 - 공집합이 아닌 모든 자연수 집합의 부분집합은 하나의 최소 정수를 포함한다는 정리 S is subset of T ∀S such that S ⊆ ℕ and S ∅,∃a ∈ S such that a ≤ b for all b ∈ S
즉, 최소항이 존재한다는 말 자연수 1 2 3 4 ... (공집합이 아닌 부분집합을 생각하라) 예를 들어 1.5보다 큰 자연수의 집합 -> 최소항 '2'가 존재한다.

Now we show uniqueness. Suppose that there exist two diffent pairs of integers q₁, r₁ and q₂, x₂ such that:

n = q₁d + r₁ (where 0 ≤ r₁ d)
n = q₂d + r₂ (where 0 ≤ r₂ d)

Subtracting the second equation from the first gives:

0 = q₁ - q₂d + (r₁ - r₂)

자연수의 정렬성(well-ordering principle)에 의하면 무조건 0보다 크거나 같은 r이 존재한다.(음수건 양수건) 그리고 r은 d보다 작아야 한다. (당연하지 나머지니까) 만약 아니면 값이 엄청 많아진다. 유니크하지 않다는 것! 유니크하다는 것을 말해주기 위해 같은 값에 두개의 조합이 있다고 가정하는 것이다. (바로 위에 만든 것처럼)

The absolute difference between the remainders r₁ and r₂ must be less than d, since 0 ≤ r₁, r₂ d. This implies that the absolute value of (q₁ - q₂)d must also be less than d, which means that q₁ - q₂ = 0. But then the equation above implies that r₁ - r₂ = 0 as well. Therefore, the pairs q₁, r₁ and q₂, r₂ are actually the same, which is a contradiction. So the quotient and remainder are unique.

나머지의 차는 d보다 작아야 한다.(r₁,r₂의 조건을 보라) 나머지가 d만큼 차이가 나지 않으니까 (q₁ - q₂)d 또한 0보다 작아야 한다. 이러면 어쩔 수 없이 저 값은 0 이 된다. 그리고 나머지의 차도 0이 된다. 둘은 같은 값인 것이고, 이것은 모순이 된다.(왜냐하면 처음에 두개의 조합을 가정했다.)