배수와 약수의 정의Permalink

Theorem 2.1Permalink

정수 cc가 존재하여 b=acb=ac 를 만족할 때, bb00이 아닌 정수 aa로 나누어 떨어진다고 하고, a  ba~\vert~b 라고 쓴다.

Theorem 2.2Permalink

정수 a,b,ca,b,c 에 대하여 다음이 성립한다.

(a)(a)

a  0,1  a,a  a\qquad a ~\vert~ 0,\quad1 ~\vert~ a,\quad a ~\vert~ a

0=a0,a=1a\qquad \because 0=a \cdot 0,\quad a=1 \cdot a

(b)(b)

a  b 이고 c  d 이면 ac  bd\qquad a ~\vert~ b \text{ 이고 } c ~\vert~ d\text{ 이면 } ac ~\vert~ bd 이다.

b=aq1,d=cq2b=aq_1,\,d=cq_2 로 두면 bd=acq1q2bd=acq_1q_2 여서

ac  acq1q2ac ~\vert~ acq_1q_2 이기 때문이다. \square

(c)(c)

a  b\qquad a ~\vert~ b 이고 b  cb ~\vert~ c 이면 a  ca ~\vert~ c이다.

(d)(d)

a  b\qquad a ~\vert~ b 이고 b0b \ne 0 이면 ab\lvert a \rvert \le \lvert b \rvert이다.

b=acb=ac 이므로 b0b\ne0 이여서 c0c\ne0 이다.

양변에 절댓값을 씌우면,

b=ac\lvert b \rvert=\lvert a \rvert \lvert c \rvert

이 때, c1\lvert c \rvert \ge 1 이므로 b=aca\lvert b \rvert=\lvert a \rvert \lvert c \rvert \ge \lvert a \rvert \square

(e)(e)

a  b\qquad a ~\vert~ b이고, a  ca ~\vert~ c 이면 임의의 정수 x,yx,\,y 에 대해 a  (bx+cy)a ~\vert~ (bx+cy) 이다.

b=aq1b=aq_1 이고 c=aq2c=aq_2 라고 하면, bx+cy=aq1x+aq2y=a(q1x+q2y)bx+cy=aq_1x+aq_2y=a(q_1x+q_2y) 이므로 a  (bx+cy)a ~\vert~ (bx+cy) \square

최대공약수의 정의Permalink

a,ba,\,b 중 적어도 하나는 00이 아닌 정수일 때,

d  a,d  bd ~\vert~ a,\, d ~\vert~ b이고 임의의 a,ba,\,b의 공약수 ccdcd \ge c 를 만족하면,

ddaabb의 최대공약수 greatest common divisor라 한다.

최대공약수의 성질Permalink

Theorem 2.3 ⭐️Permalink

적어도 하나는 00이 아닌 정수 a,ba,\,b에 대해 gcd(a,b)=ax+bygcd(a,b)=ax+by 를 만족하는 정수 x,yx,\,y가 존재한다.

증명

S={au+bv  au+bv>0,  u,vZ} S=\{ au+bv ~\vert~ au+bv > 0,\ \ u,\,v \in \Z \}

인 집합 SS에 대해 SS \ne \varnothing 임을 보이자.

일반성을 잃지 않고 a0a \ne 0 일 때, a=au+b0\lvert a \rvert = au+b \cdot 0u=1 or u=1u=1\ or\ u=-1 일 때 성립한다.

a=0a = 0 이라면 aabb를 바꾸어 주면 되므로

둘 중 하나는 SS에 존재하므로 SS \ne \varnothing

정렬성의 원리에 의해 SS의 가장 작은 원소 dd가 있고,

d=ax+byd=ax+by를 만족하는 정수 x,yx,y가 존재한다.

d=gcd(a,b)d=gcd(a,b) 를 증명하자.Permalink

나눗셈 정리에 의해 a=qd+r (0r<d)  (1)a=qd+r\ (0 \le r < d) ~~(1) 를 만족하는 q,rq,r이 유일히 존재한다.

r=aqd=aq(ax+by)=a(1xq)+b(qy)      (2) \begin{aligned} r&=a-qd\\ &=a-q(ax+by)\\ &=a(1-xq)+b(-qy) ~~~~~~ (2) \end{aligned}

이 때, rrSS의 가장 원소 dd보다 작다. (1)(1)

rr은 (2)에서 ax+byax+by 꼴이 나왔으므로 집합 SS에 속하지 않기 위해 00이 되어야 한다.

즉, a=qda=qd 이고 d  ad ~\vert~ a 이고 마찬가지로 d  bd ~\vert~ b 를 보인다.

aabb의 임의의 공약수 cc에 대해 c  ax+byc ~\vert~ ax+by인데, d=ax+byd=ax+by 이므로 c  dc ~\vert~ d 이고 cd\lvert c \rvert \le d 이다.

즉, dda,ba,b의 모든 공약수들보다 크거나 같으므로 d=gcd(a,b)d=gcd(a,b) \square

Corollary 2-3 ⭐️Permalink

a,ba,b 가 둘 중 하나는 00이 아닌 정수일 때,

c=ax+byc=ax+by를 만족하는 정수x,yx,y가 존재하면, d  cd ~\vert~ c 이고 이는 필요충분조건이다. (d=gcd(a,b))(d=gcd(a,b))

증명

d=gcd(a,b)d  a & d  bd  (ax+by) \begin{aligned} d&=gcd(a,b) \\ &\Rightarrow d ~\vert~ a ~\&~ d ~\vert~ b \\ &\Rightarrow d ~\vert~ (ax+by) \end{aligned}

역으로, d  cd ~\vert~ c 이면 d=ax+byd=ax+by를 만족하는 x,yx,y에서

양변에 정수인 cd\dfrac cd 를 곱해주면,

d  c\because d ~\vert~ c

c=acxd+bcydc=a \cdot \dfrac {cx}d + b \cdot \dfrac {cy}d \square

서로소의 정의Permalink

둘 중 하나는 00이 아는 정수 x,yx,y 에 대해 gcd(x,y)=1gcd(x,y)=1이면 aabb서로소 (coprime, relatively prime) 이라고 한다.

Theorem 2.4Permalink

a,ba,b를 둘 중 하나는 00이 아닌 정수라 할 때,

a,ba,b가 서로소이면, 1=ax+by1=ax+by인 정수 x,yx,y가 존재하고, 역도 성립한다.

증명

1=gcd(a,b)=ax+by1=gcd(a,b)=ax+by 이므로 Theorem 2.3에 의해 성립한다.

역으로,

d=gcd(a,b)d  a & d  bd=gcd(a,b) \Rightarrow d ~\vert~ a ~\&~ d ~\vert~ b

a=dq1, b=dq2a=dq_1,~b=dq_2

ax+by=dq1x+dq2y=d(q1x+q2y)  1ax+by=dq_1x+dq_2y=d(q_1x+q_2y) ~\vert~ 1 이다.

d  1d ~\vert~ 1 이므로 d1\lvert d \rvert \le 1 이여야 하고, d1d \ge 1 이므로 d=1d=1 이다. \square

Corollary 2.4 - 1Permalink

gcd(a,b)=dgcd(a,b)=d이면, gcd(ad,bd)=1gcd\left(\dfrac ad,\, \dfrac bd\right)=1

증명

d=ax+by1=(ad)x+(bd)y \begin{aligned} d=ax+by\\ 1=\Bigl(\dfrac ad\Bigr)x + \Bigl(\dfrac bd\Bigr)y \end{aligned}

이므로 ad\dfrac adbd\dfrac bd는 서로소이다.

Corollary 2.4 - 2Permalink

a  ca ~\vert~ c, b  cb ~\vert~ c 그리고 gcd(a,b)=1gcd(a,b)=1 이면 ab  cab ~\vert~ c

증명

c=aq1=bq2c=aq_1=bq_2

1=ax+by1=ax+by를 만족하는 x,yx,y가 존재하므로

c=acx+bcy=a(bq2)x+b(aq1)y=()ab \begin{aligned} c&=acx+bcy\\ &=a(bq_2)x+b(aq_1)y\\ &=(\cdots)ab \end{aligned}

즉, ab  c ab ~\vert~ c~\square

Theorem 2.5 - 유클리드 보조정리Permalink

a  bca ~\vert~ bc이고 gcd(a,b)=1gcd(a,b)=1 이면 a  ca ~\vert~ c 이다.

증명

1=ax+byc=axc+byc=axc+yaq  a  bc=a()a  c   \begin{aligned} 1&=ax+by\\ c&=axc+byc\\ & =axc+yaq ~~ \because a ~\vert~ bc\\ & =a(\cdots) \\ \\ &\therefore a ~\vert~ c~~\square \end{aligned}

Comments