2.4.1 The Euclidean Algorithm


Lemma (will be proved)
Proof of

pf

example
숫자가 클수록 모든 positive divisor을 구하기는 어렵다

정리
- prove the Euclidean Algorithm
- We can compute the gcd(a,b) using Euclidean Algorithm (even for large a and b)
2.4.2 Find
유클리드 호제법의 응용


답중의 하나를 위의 방법으로 구할 수 있다.
Theorem 2.7

Euclidean Algorithm 이용해서 증명함
정리
- We can find using the Euclidean Algorithm
2.4.3 The Least Common Multiple
Definition 2.4
Given , the least common multiple of is the positive integer m satisfying
(a) and (common multiple)
(b) and (least)
In this case, we write )
Theorem 2.8
Corollary 2.8
For any
Proof of Theorem 2.8
정리
- We can write the definition of
- We can prove the relation between
Comments