배수와 약수의 정의
Theorem 2.1
정수 c가 존재하여 b=ac 를 만족할 때, b는 0이 아닌 정수 a로 나누어 떨어진다고 하고, a ∣ b 라고 쓴다.
Theorem 2.2
정수 a,b,c 에 대하여 다음이 성립한다.
(a)
a ∣ 0,1 ∣ a,a ∣ a
∵0=a⋅0,a=1⋅a
(b)
a ∣ b 이고 c ∣ d 이면 ac ∣ bd 이다.
b=aq1,d=cq2 로 두면 bd=acq1q2 여서
ac ∣ acq1q2 이기 때문이다. □
(c)
a ∣ b 이고 b ∣ c 이면 a ∣ c이다.
(d)
a ∣ b 이고 b=0 이면 ∣a∣≤∣b∣이다.
b=ac 이므로 b=0 이여서 c=0 이다.
양변에 절댓값을 씌우면,
∣b∣=∣a∣∣c∣
이 때, ∣c∣≥1 이므로 ∣b∣=∣a∣∣c∣≥∣a∣ □
(e)
a ∣ b이고, a ∣ c 이면 임의의 정수 x,y 에 대해 a ∣ (bx+cy) 이다.
b=aq1 이고 c=aq2 라고 하면, bx+cy=aq1x+aq2y=a(q1x+q2y) 이므로 a ∣ (bx+cy)□
최대공약수의 정의
a,b 중 적어도 하나는 0이 아닌 정수일 때,
d ∣ a,d ∣ b이고 임의의 a,b의 공약수 c가 d≥c 를 만족하면,
d는 a와 b의 최대공약수 greatest common divisor라 한다.
최대공약수의 성질
Theorem 2.3 ⭐️
적어도 하나는 0이 아닌 정수 a,b에 대해 gcd(a,b)=ax+by 를 만족하는 정수 x,y가 존재한다.
증명
S={au+bv ∣ au+bv>0, u,v∈Z}
인 집합 S에 대해 S=∅ 임을 보이자.
일반성을 잃지 않고 a=0 일 때, ∣a∣=au+b⋅0 은 u=1 or u=−1 일 때 성립한다.
a=0 이라면 a와 b를 바꾸어 주면 되므로
둘 중 하나는 S에 존재하므로 S=∅
정렬성의 원리에 의해 S의 가장 작은 원소 d가 있고,
d=ax+by를 만족하는 정수 x,y가 존재한다.
d=gcd(a,b) 를 증명하자.
나눗셈 정리에 의해 a=qd+r (0≤r<d) (1) 를 만족하는 q,r이 유일히 존재한다.
r=a−qd=a−q(ax+by)=a(1−xq)+b(−qy) (2)
이 때, r은 S의 가장 원소 d보다 작다. (1)
r은 (2)에서 ax+by 꼴이 나왔으므로 집합 S에 속하지 않기 위해 0이 되어야 한다.
즉, a=qd 이고 d ∣ a 이고 마찬가지로 d ∣ b 를 보인다.
a와 b의 임의의 공약수 c에 대해 c ∣ ax+by인데, d=ax+by 이므로 c ∣ d 이고 ∣c∣≤d 이다.
즉, d는 a,b의 모든 공약수들보다 크거나 같으므로 d=gcd(a,b) □
Corollary 2-3 ⭐️
a,b 가 둘 중 하나는 0이 아닌 정수일 때,
c=ax+by를 만족하는 정수x,y가 존재하면, d ∣ c 이고 이는 필요충분조건이다. (d=gcd(a,b))
증명
d=gcd(a,b)⇒d ∣ a & d ∣ b⇒d ∣ (ax+by)
역으로, d ∣ c 이면 d=ax+by를 만족하는 x,y에서
양변에 정수인 dc 를 곱해주면,
∵d ∣ c
c=a⋅dcx+b⋅dcy □
서로소의 정의
둘 중 하나는 0이 아는 정수 x,y 에 대해 gcd(x,y)=1이면 a와 b를 서로소 (coprime, relatively prime) 이라고 한다.
Theorem 2.4
a,b를 둘 중 하나는 0이 아닌 정수라 할 때,
a,b가 서로소이면, 1=ax+by인 정수 x,y가 존재하고, 역도 성립한다.
증명
1=gcd(a,b)=ax+by 이므로 Theorem 2.3에 의해 성립한다.
역으로,
d=gcd(a,b)⇒d ∣ a & d ∣ b
a=dq1, b=dq2
ax+by=dq1x+dq2y=d(q1x+q2y) ∣ 1 이다.
d ∣ 1 이므로 ∣d∣≤1 이여야 하고, d≥1 이므로 d=1 이다. □
Corollary 2.4 - 1
gcd(a,b)=d이면, gcd(da,db)=1
증명
d=ax+by1=(da)x+(db)y
이므로 da와 db는 서로소이다.
Corollary 2.4 - 2
a ∣ c, b ∣ c 그리고 gcd(a,b)=1 이면 ab ∣ c
증명
c=aq1=bq2
1=ax+by를 만족하는 x,y가 존재하므로
c=acx+bcy=a(bq2)x+b(aq1)y=(⋯)ab
즉, ab ∣ c □
Theorem 2.5 - 유클리드 보조정리
a ∣ bc이고 gcd(a,b)=1 이면 a ∣ c 이다.
증명
1c=ax+by=axc+byc=axc+yaq ∵a ∣ bc=a(⋯)∴a ∣ c □
Comments