2.3.3. relatively prime

Definition

$ \text{Given } a,b \in \mathbb{Z} \text{ (at least one of them is not zero), } $

$ a,b \text{ are called relatively prime } \overset{\text{def}}{\Longleftrightarrow} gcd(a,b)=1 $

Theorem 2.3

$ \text{Given } a,b \in \mathbb{Z} \left(a \neq 0 \text{ or } b \neq 0 \right) \text{, let } d=gcd(a,b) $
$ \Rightarrow \text{There exists } x,y \in \mathbb{Z} \text{ such that } ax + by = d $

이전에 증명했었다. 지금은 d=1 인 case

Theorem 2.4

$ gcd(a,b) = 1 \Longleftrightarrow \exists x,y \in \mathbb{Z} \text{ s.t. }ax+by = 1 $

Corollary of Theorem 2.4

2.4.1

2.4.2

• The condition “$gcd(a,b)=1$” is necessary

Note that $ 6\mid 24$ and $8 \mid 24$. BUT $ (6 \cdot 8) \nmid 24 $

Theorem 2.5 Euclid’s lemma

Theorem 2.6 The Gratest Common Divisor

그래서 $d=12$ 였다면 원래 정의에서는 d보다 작은 값이 다 될수 있었는데, 사실 d의 약수 $c=1,2,3,4,6,12 $ 만 생각하면 된다.

정리

• definition of relatively prime numbers
• $ gcd(a,b) = 1 \Longleftrightarrow $ $\text{there exists } x,y \in \mathbb{Z} \text{ with } ax+by=1$
• corollaries of Theorem 2.4
• Euclid’s lemma

문제

꼭 풀어보도록 하자…