검색결과 리스트
글
※이 글을 읽기 전에 알아야 할 기호
gcd : '최대공약수'의 기호입니다.
표기 예시를 들어보자면,
gcd(x,y)는 x와 y의 최대공약수
gcd(l,m,n)은 l,m,n의 최대공약수
p.s.최소공배수는 lcm이고 쓰는 법은 같아요~
유클리드 호제법이란?
뭔가 이름만 들어도 여러모로 머리가 아픈 유클리드 호제법!
유클리드 호제법은 두 다항식 또는 자연수 사이의 최대공약수를 구할 때 자주 등장하는 유용한 녀석이에요!
(물론 수학 교육 과정에는 없습니다 쿨럭)
정수론 공부나 KMO 준비를 하시는 분들은 다들 한 번씩 접해보셨을 편리한 도구인데요!
일단 증명은 아래로 미루고 결과를 먼저 보도록 합시다앗!
"a>b인 두 양의 정수 a,b에 대하여,
a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)
이라 하면,
gcd(a,b)=gcd(b,r)
(a,b의 최대공약수=b,r의 최대공약수)이다."
'흐음 저게 어디가 유용하다는 거지..?'
싶으신 분들을 위해 예시를 몇가지 들어볼까요?
'1071과 1029 사이의 최대공약수는 21이다.'
이 상황에서 간단한 계산식 두 세 번이면
이를 계산할 수 있게 해주는 것이 바로
유클리드 호제법!!
정말 탐나지 않나요옷!
바로 증명 들어갑니다앗ㄱㄱ
유클리드 호제법의 증명
일단 a>b인 두 양의 정수 a,b를 잡아줍시다!
여기서 구하고 싶은건 바로 최대공약수니까
얘도 G로 잡아주도록 할게요!
따라서 이렇게 되면 a,b는 당연히
G의 배수가 되겠지요?
그러면 요렇게 되겠네요!
여기서 대문자인 A와 B는 몫입니다!
최대공약수 G로 나누니까 나머지는 없구요!
여기서 중요한 게 뭐냐면,
'A와 B는 서로소'
라는 사실이에요.
만약 A와 B가 서로소가 아니라면,
G는 더 이상 최대공약수가 아니니까요!
사실 당연한 말!
(최대공약수는 모든 공통 약수를 가져가야 하기 때문에, 남은 것에 공통 약수가 있을리는 없죠)
자아 이 정도 해두면 좋습니다!
다음 과정으로 넘어가볼까요?
a>b이기 때문에,
b로 a를 나눌 수 있으니까
계산식을 써주면 몫 q와 나머지 r이 나오네요!
이제 여기에 a=AG,b=BG를 대입해도
식이 성립하겠군요!
그러면 바로 대입 ㄱㄱ
이건 뭐 그냥 대입만 했으니까 별 거 없네요.
이제 식에 변형을 좀 줘봅시다.
자 이거는 아주 쉽게 이해하실 거에요!
1.qBG 이항
2.G로 묶기
가 되었네요!
근데 제가 아까 b=BG라고 했죠?
이렇게 되면 아래와 같아지겠군요!
아까 b의 정의에 따르면,
둘 사이에는 G라는 공통의 약수가 생기게 되는 것을 어렵지 않게 알 수 있군요!
자아 근데 유클리드 호제법을 증명하기 위해서는
b와 r에 있는 G 저 친구가
'최대공약수'가 되어야 하겠네요!
그래야지만 a,b의 최대공약수 G가
b,r의 최대공약수와 같아지니까요!
결국 그게 유클리드 호제법이죠?
자 그렇게 되면,
이 두 녀석이 서로소임을 증명하기만 하면
우리가 원하는 유클리드 호제법이 증명되는 겁니다!
근데 잘 생각해보시면,
1. 서로소가 아니다.
2. 서로소이다.
두가지 중 하나의 결과가 맞는 것 아니겠어요?
그러니까 우리는 2가 맞는 사실을 보이려면,
1) 2가 맞다.
2)1이 틀렸다.
둘 중 하나만 증명해도 결국 증명된 거 아니겠어요!
1과 2중 하나만 정답이라는 것인데,
1이 틀렸다면 당연히 정답은 2겠죠!
따라서 우리는 1번,
즉 '서로소가 아니다' 라는 사실이 틀렸음을 보이면 된다는 것이지요.
그렇다면 '서로소가 아니다' 라는 사실이 틀렸음을 알기 위해서는
서로소가 아니게 가정을 했을 때
'모순'이 발생한다면,
즉 논리적으로 안 들어맞는 개소리가 생긴다면,
곧 그 가정이 틀린 가정임을 알려주는 거 아니겠어요?
자 이제 그럼 그 놈의 모순이란 걸 보여보도록 합시다.
(참고로 이런 식의 논리 흐름을 통해 명제를 증명하는 것을 '귀류법' 이라고 합니다.
자주 쓰이는 중요한 개념이에요!)
두 수가 서로소가 아니라고 했으니,
1보다 큰 최대공약수인 t가 존재한다는 것이겠지요!
(물론 m,n은 당연히 몫입니다~)
그럼 이제 B를 대입해 보시면,
당연히 이렇게 나오겠네요!
이 식을 조금 변형시켜본다면,
자아 근데 여기서 모순이 발생합니다앗!!
우리가 A와 B는 서로소라고 했던 것 기억나시나요?
까먹으신 거 아니겠지!!
위에 진한 글씨로 강조했는데!
근데 결과는 서로소가 아니라고 나오네?
엥???
요것이 바로 모순입니다.
결과가 개소리니까 가정도 개소리가 되는 것이고,
따라서 우리는 유클리드 호제법을 증명해냈습니다! 짝짝
이제 증명도 했겠다, 위에 든 예시를 직접 계산해보며 사용법 감을 익혀보죠!
유클리드 호제법 사용 예시
아까 제가 1071과 1029 사이의 최대공약수가
21이라고 했던 사실 기억나시나요?
요것을 한 번 직접 계산해보자구요!
a=qb+r이라고 했었죠? 그럼 똑같이
1071=1×1029+42
여기서 a,b의 최대공약수,
즉 1071과 1029의 최대공약수는,
b,r의 최대공약수인,
1029와 42의 최대공약수와 동일합니다!
따라서 1029와 42 사이에 또 같은 방법을 취해주더라도,
새로 만들어지는 b,r의 최대공약수가 결국
gcd(a,b)와 동일해지겠죠!
따라서 또 한 번 적용해주면,
1029=24×42+21
그러면 gcd(b,r)=gcd(42,21)이 결국 답이 되네요!
(헷갈리실 까봐 적는 것인데 24는 그냥 몫이에요!
하던대로 나눠서 계산해보시면 됩니다.
유클리드 호제법에서 딱히 중요한 부분 아니에욧)
그러면 42와 21의 최대공약수는
너무 쉽게도 21입니다!
계산 끝!
"a>b인 두 양의 정수 a,b에 대하여,
a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)
이라 하면,
gcd(a,b)=gcd(b,r)
(a,b의 최대공약수=b,r의 최대공약수)이다."
어떠신가요? 이제 이 말이 좀 눈에 들어오시나요?
(참고로 나머지 r의 조건은 당연한 거에요!
나머지가 나눈 수보다 크면 덜 나눠진 거잖아요!)
지금까지 장문 봐가면서 이해하려 노력하신
독자 분들께 박수를 보냅니다.
오늘도 수학 지식이 더 풍부해지셨습니다앗!
저는 이만! 열공~
'수학' 카테고리의 다른 글
| [기초행렬] 3. 행렬의 의의 (0) | 2019.04.07 |
|---|---|
| [기초행렬] 2. 행렬의 연산 (0) | 2019.04.07 |
| [기초행렬] 1.행렬의 정의 (0) | 2019.04.07 |
| [고등수학]자연 상수 e에 대하여 알아보자! (1) | 2019.04.06 |
글
고등 미적분 파트에서 접하게 되는
중요한 수학적인 상수!
지수 함수 혹은 로그 함수의 미적분 과정에서 대표적으로 자주 거론되는,
여러모로 핵심적인 부분을 맡고 있는 자연 상수를 한 번 파헤쳐봅시닷!ㄱㄱ
먼저 정의를 툭 던져드려보자면..
차차 설명드리겠습니다 (찡긋)
자연 상수의 계산
우선 자연 상수는 '복리' 의 계산에서 언급되어지기 시작했습니다.
복리는 일종의 이자 계산법입니다.
예를 들어보죠!
A가 은행에 예금을 넣고
1년 뒤 원금의 100%를 이자로 받기로 해봅시다!(헐 개쩐다)
1만원을 넣었다고 했을 때,
1년 뒤에는 총 금액이 다음과 같아집니다.
원금 1만원에다가,
원금×이자율 즉 이자가 1만원×100%=1만원!
이제 원금에 이자까지 더하면 1년 뒤의 총 금액을 계산할 수 있겠네요!
자,여기서 우리 한 번 은행에 이벤트를 진행해봅시닷 (..?)
12개월 뒤에 100%가 딱 생기는 거에서
6개월 뒤에 50%,6개월 뒤에 50%로 두 번에 걸쳐서 받을 수 있게 규칙을 바꿨습니다!
이 규칙을 적용했을 때의 계산식도 어렵지 않게 아래처럼 구해집니다.
원금 1과 이자 1×50%=0.5의 합인
1.5로 계산될 수 있는 것 이해되시지요?
이 1.5가 또 다시 50% 증가해주면 되는 것이기 때문에,
1+50%=총 150%를 다시 곱해 다음과 같은 식이 만들어지게 됩니다.
좀 다르게 표현해본다면 아래와 같겠네요.
자 머리가 좋은 여러분들은 3번째로 뭘 해야할지 감이 오실 거에요.
1번째에는 100%를 한 번에 1만큼,
2번째에는 100%를 두 번에 1/2만큼씩,
즉 3번째에는 100%를 세 번에 1/3만큼씩
이겠지요?
그렇게 되면 당연스레 3번째에는 아래와 같은 계산식을 얻을 수 있어요.
(저기 물결이 넘실거리는 등호는
양변의 값이 비슷하다는 뜻의 기호에요.)
4번째 한 번에 그냥 가봅니다앗!
제가 좀 계산해드릴게욧
5번째,
어엇..뭐지? 점점 어느 숫자에 수렴하고 있는 것으로 보이죠?
이제 무한 번만큼 죤내 많이 곱하자!
n번째로 바꿔버린 다음 n을 무한으로 보낸다고 해주면,
바로 우리가 원하고 있는 자연 상수 e가 계산되는 것입니다앗!
이제 자연 상수를 계산해보았으니,
자연 상수가 가지는 의의에 대해서 말씀 드려볼게요~
p.s.시험에 의의 안 나온다고 갖다버리는 학생들 있는데 수학이라는 학문에서 상당히 중요한 부분이 바로 이런 부분입니다. 그냥 계산만 아는게 잘 아는 것이 절대 아닙니다.
자연 상수의 의의
일단 결론부터 말씀드리자면,
"100%의 성장률을 가지고 1회 연속 성장할 때,
최대로 성장할 수 있는 비율"
'이게 뭔 개소리일까 ㅎㅎ죤내 어이가 없다..'
싶지요? 아까부터 결론 먼저 던져서 멘붕드린 점 사과드립미다 주르륵..
일단 하나 하나 뜯어보자면,
"100%의 성장률을 가지고"
우리가 처음에 복리 얘기를 할 때에,
100%만큼 증가하는 걸로 정해두었지요?
자연 상수가 성장률 100%를 기준으로
만들어진 상수이기 때문에 저런 말을 한 겁니다!
"1회 연속 성장할 때"
100%를 연속 성장한다는 것이 무슨 의미냐면,
한 번 예를 들어 100원을 생각해봅시다.
1. 100%를 1번에,즉 100%를 계산하면 200원입니다.
2. 2번에 계산하면, 즉 50%,50%를 계산하면 225원입니다.
이 두 친구는 모두 불연속 성장을 한 겁니다.
딱 딱 끊겨서 증가하는 포인트가 보이기 때문에, 이를 불연속으로 성장한다고 하는 것이지요!
그러면 좀 더 부드럽게 하려면,
나누는 수, 즉 계산 횟수를 늘려주면 점점 더 부드럽게 계산되겠지요?
(횟수가 늘어날수록 각 포인트마다 증가하는 정도가 줄어들어서 부드러워지는 거지요!)
이해를 돕기 위해 그림을 좀 넣어볼까요?
즉 계산 횟수가 늘어날수록,
결론적으로 횟수 n이 무한대에 가까워질수록, 부드러워지게 되는겁니다!
따라서 n이 무한대로 갈 적의 성장을
'연속 성장'
이라고 말해줄 수 있는 거에요.
따라서,
'1회 수행된 연속 성장의 비율'
로 볼 수 있겠지요!
(2회 수행되면 당연히 자연 상수 e를 두 번 곱한 e의 제곱(e^2)이 성장 비율이 되겠네요~)
"최대로 성장할 수 있는 비율"
당연스레 1회 연속 성장의 비율을 초과해서
1회 연속 성장이 될 수 없으니까요!
당연한 말이라고 보시면 됩니다!
(우리가 지수 혹은 로그 함수의 미적분을 공부할 때 수도 없이 튀어나오는 자연 상수도, 이런 자연스러운 증가율의 의의를 가지다 보니 계속해서 엮여나오는 것으로 볼 수 있겠어요!)
이제 이해되셨나요?
"100%의 성장률을 가지고 1회 연속 성장할 때,
최대로 성장할 수 있는 비율"
지금까지 어려웠던 내용 읽어주신 여러분께 수고하셨다고 전해드리고 싶습니다~
작성한 내용 중 이해가 힘든 부분은 혼자 끙끙대지 마시고 댓글로 물어보셔도 돼요!
'수학' 카테고리의 다른 글
| [기초행렬] 3. 행렬의 의의 (0) | 2019.04.07 |
|---|---|
| [기초행렬] 2. 행렬의 연산 (0) | 2019.04.07 |
| [기초행렬] 1.행렬의 정의 (0) | 2019.04.07 |
| [대수학&정수론]유클리드 호제법의 증명 (1) | 2019.04.07 |
RECENT COMMENT