Proposition (명제)
참과 거짓을 판별할 수 있는 문장.
Axiom (공리)
증명이 필요없는 항상 옳다고 인정되는 명제.
Theorem (정리)
수학적으로 참인 공리 또는 정의를 기반으로 증명된 명제.
Lemma (보조정리)
다른 정리를 증명하는 데 쓸 목적으로 증명된 명제.
Corollary (따름정리)
추론이라고도 부른다. 이미 증명된 다른 정리에 의해 바로 유도되는 명제.
1. 정리와 보조 정리의 예
----------------------------------------------------------------------------
① 정리 1 (Theorem 1)
a와 b가 양의 정수이면, gcd(a, b) = sa + tb인 s와 t가 존재한다.
(즉, 양의 정수 a와 b에 대해, gcd(a, b)는 a와 b의 선형 결합으로 표현할 수 있다.)
증명
k가 xa + yb 형태(선형 결합)로 나타낼 수 있는 가장 작은 양의 정수라고 가정하자.
(이 때 q = a를 k로 나눈 몫이라고 가정한다.)
a mod k = a - qk = a - q(xa + yb) = a(1 - qx) + b(-qy)가 성립한다.
즉, a mod k 역시 a와 b를 이용한 선형 결합으로 나타낼 수 있다.
이 때, k가 a와 b의 선형 결합으로 만들 수 있는 가장 작은 양의 정수이므로,
(a mod k) ≤ 0, (a mod k) ≥ k (부등식ⅰ)가 성립한다.
또한 mod 연산의 정의에 따라 0 ≤ (a mod k) < k (부등식ⅱ) 역시 성립한다.
부등식ⅰ와 ⅱ를 모두 만족하려면 (a mod k) = 0 이다. (즉, k|a)
같은 방법으로 (b mod k) = 0 임을 보일 수 있기 때문에, k|b를 만족한다.
위의 결과에 따라 k는 a와 b의 공약수임을 알 수 있다. 따라서 gcd(a, b) ≥ k (부등식ⅲ)를 만족한다.
최대공약수의 성질에 따라 gcd(a, b)는 a와 b 공통의 약수이기 때문에, a와 b의 선형 결합인 k도 나눌 수 있다.
즉 gcd(a, b)|k 이 성립하며, gcd(a, b) ≤ k (부등식ⅳ)를 만족시킨다.
부등식 ⅲ와 ⅳ를 모두 만족하려면 gcd(a, b) = k가 된다.
∴ 따라서, gcd(a, b) = a(1 - qx) + b(-qy)인 x와 y가 존재하며, s = 1 - qx, t = -qy가 된다.
----------------------------------------------------------------------------
② 보조정리(Lemma)
양의 정수 a, b, c가 gcd(a, b) = 1 이고, a|bc 이면 a|c 이다.
증명
gcd(a, b) = 1이므로 정리 1에 의해 sa + tb = 1인 s와 t가 존재한다.
이 식의 양쪽에 c를 곱하면 sac + tbc = c이다.
a|bc 이면 a|tbc를 만족하며, a|sac 역시 만족한다.
∴ 따라서 a는 sac와 tbc의 선형 결합인 sac + tbc (= c) 역시 나누게 된다.
------------------------------------------------------------------------------------------
③ 증명 과정에 ②를 사용하는 정리 2 (Theorem 2)
m이 양의 정수이고 a, b, c가 정수이면 ac ≡ bc(mod m)이고 gcd(c, m) = 1이면 a≡b(mod m)이다.
증명
ac ≡ bc (mod m)이므로 m|(ac - bc) = c(a - b). 보조정리에 의해 gcd(c, m) = 1 이므로 m|(a - b) 이다.
즉, a ≡ b (mod m)이다.
-----------------------------------------------------------------------------
2. 정리와 따름 정리의 예
-----------------------------------------------------------------------------
① 나머지 정리 (Remainder Theorem)
x에 대한 다항식 f(x)를 x에 대한 일차식 (x-a)로 나눈 나머지는 f(a)이다.
증명
f(x)를 (x-a)로 나누었을 때 몫을 q(x), 나머지를 r이라고 하면, f(x) = (x-a)q(x) + r 이다.
이 때 x에 a를 대입해보면 다음과 같다.
f(a) = (a-a)q(a) + r = 0·q(a) + r = r
∴ f(a) = r
-------------------------------------------------------------------------------------------
② ①의 따름 정리(Corollary)
x에 대한 다항식 f(x)가 일차식 x-a로 나누어 떨어지기 위한 필요충분조건은 f(a) = 0 이다.
(이 따름 정리는 인수정리(Factor Theorem) 이라고도 부른다.)
증명
정리 ①에서 f(x) = (x-a)q(x) + f(a) 이므로, f(x)가 (x-a)로 나누어 떨어지려면, f(a) = 0이어야 한다.
------------------------------------------------------------------------------
참과 거짓을 판별할 수 있는 문장.
Axiom (공리)
증명이 필요없는 항상 옳다고 인정되는 명제.
Theorem (정리)
수학적으로 참인 공리 또는 정의를 기반으로 증명된 명제.
Lemma (보조정리)
다른 정리를 증명하는 데 쓸 목적으로 증명된 명제.
Corollary (따름정리)
추론이라고도 부른다. 이미 증명된 다른 정리에 의해 바로 유도되는 명제.
1. 정리와 보조 정리의 예
----------------------------------------------------------------------------
① 정리 1 (Theorem 1)
a와 b가 양의 정수이면, gcd(a, b) = sa + tb인 s와 t가 존재한다.
(즉, 양의 정수 a와 b에 대해, gcd(a, b)는 a와 b의 선형 결합으로 표현할 수 있다.)
증명
k가 xa + yb 형태(선형 결합)로 나타낼 수 있는 가장 작은 양의 정수라고 가정하자.
(이 때 q = a를 k로 나눈 몫이라고 가정한다.)
a mod k = a - qk = a - q(xa + yb) = a(1 - qx) + b(-qy)가 성립한다.
즉, a mod k 역시 a와 b를 이용한 선형 결합으로 나타낼 수 있다.
이 때, k가 a와 b의 선형 결합으로 만들 수 있는 가장 작은 양의 정수이므로,
(a mod k) ≤ 0, (a mod k) ≥ k (부등식ⅰ)가 성립한다.
또한 mod 연산의 정의에 따라 0 ≤ (a mod k) < k (부등식ⅱ) 역시 성립한다.
부등식ⅰ와 ⅱ를 모두 만족하려면 (a mod k) = 0 이다. (즉, k|a)
같은 방법으로 (b mod k) = 0 임을 보일 수 있기 때문에, k|b를 만족한다.
위의 결과에 따라 k는 a와 b의 공약수임을 알 수 있다. 따라서 gcd(a, b) ≥ k (부등식ⅲ)를 만족한다.
최대공약수의 성질에 따라 gcd(a, b)는 a와 b 공통의 약수이기 때문에, a와 b의 선형 결합인 k도 나눌 수 있다.
즉 gcd(a, b)|k 이 성립하며, gcd(a, b) ≤ k (부등식ⅳ)를 만족시킨다.
부등식 ⅲ와 ⅳ를 모두 만족하려면 gcd(a, b) = k가 된다.
∴ 따라서, gcd(a, b) = a(1 - qx) + b(-qy)인 x와 y가 존재하며, s = 1 - qx, t = -qy가 된다.
----------------------------------------------------------------------------
② 보조정리(Lemma)
양의 정수 a, b, c가 gcd(a, b) = 1 이고, a|bc 이면 a|c 이다.
증명
gcd(a, b) = 1이므로 정리 1에 의해 sa + tb = 1인 s와 t가 존재한다.
이 식의 양쪽에 c를 곱하면 sac + tbc = c이다.
a|bc 이면 a|tbc를 만족하며, a|sac 역시 만족한다.
∴ 따라서 a는 sac와 tbc의 선형 결합인 sac + tbc (= c) 역시 나누게 된다.
------------------------------------------------------------------------------------------
③ 증명 과정에 ②를 사용하는 정리 2 (Theorem 2)
m이 양의 정수이고 a, b, c가 정수이면 ac ≡ bc(mod m)이고 gcd(c, m) = 1이면 a≡b(mod m)이다.
증명
ac ≡ bc (mod m)이므로 m|(ac - bc) = c(a - b). 보조정리에 의해 gcd(c, m) = 1 이므로 m|(a - b) 이다.
즉, a ≡ b (mod m)이다.
-----------------------------------------------------------------------------
2. 정리와 따름 정리의 예
-----------------------------------------------------------------------------
① 나머지 정리 (Remainder Theorem)
x에 대한 다항식 f(x)를 x에 대한 일차식 (x-a)로 나눈 나머지는 f(a)이다.
증명
f(x)를 (x-a)로 나누었을 때 몫을 q(x), 나머지를 r이라고 하면, f(x) = (x-a)q(x) + r 이다.
이 때 x에 a를 대입해보면 다음과 같다.
f(a) = (a-a)q(a) + r = 0·q(a) + r = r
∴ f(a) = r
-------------------------------------------------------------------------------------------
② ①의 따름 정리(Corollary)
x에 대한 다항식 f(x)가 일차식 x-a로 나누어 떨어지기 위한 필요충분조건은 f(a) = 0 이다.
(이 따름 정리는 인수정리(Factor Theorem) 이라고도 부른다.)
증명
정리 ①에서 f(x) = (x-a)q(x) + f(a) 이므로, f(x)가 (x-a)로 나누어 떨어지려면, f(a) = 0이어야 한다.
------------------------------------------------------------------------------
