2.3.3. relatively prime

Definition

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

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

Theorem 2.3

Given a,b∈Z(a≠0 or b≠0), let d=gcd(a,b)\text{Given } a,b \in \mathbb{Z} \left(a \neq 0 \text{ or } b \neq 0 \right) \text{, let } d=gcd(a,b)
⇒There exists x,y∈Z such that ax+by=d\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⟺∃x,y∈Z s.t. ax+by=1gcd(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.1

2.4.2

서로소 정리 2.4.2

  • The condition "gcd(a,b)=1gcd(a,b)=1" is necessary

Note that 6∣24 6\mid 24 and 8∣248 \mid 24. BUT (6⋅8)∤24(6 \cdot 8) \nmid 24

Theorem 2.5 Euclid’s lemma

유클리드 보조정리

Theorem 2.6 The Gratest Common Divisor

최대공약수 정리 2.6

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

정리

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

문제

꼭 풀어보도록 하자…

Discussion

Comments