4. Euclidean algorithm
유클리드 호제법
Euclidean
algorithm
"숫자만이 아니라
다항식도 되네요?"
" this algorithm works in
polynomials
as well as numbers! "
유클리드의 호제법은 일반적으로 두 자연수 사이의 최대공약수를 찾아내는 기법으로, 표준교과의 범위를 벗어 나는 내용입니다만, 소인수로 분해하는 방법보다 빠르고 편리하기 때문에 알아 두면 아주 편리합니다.
두 자연수의 나눗셈을 하고 남은 나머지에는, 그 두 수의 최대공약수가 인수로 들어 있다는 원리를 활용하는 심화 수준의 개념 유형이 종종 출제되므로, 보충 설명의 성격으로 게재합니다.
이 유클리드의 기법은 두 정수나 두 다항식의 경우에도 그대로 적용되니, 상위권 학생들은 개념과 원리를 정확히 이해하고, 응용력도 키워두면 좋습니다.
♧ ♧ ♧ ♧ ♧ ♧
스마트폰에서 수학 수식을 보시려면, 왼쪽 버튼을 누른 후
[데스크톱 보기] 를 설정하세요.
You can read math equations,
by selecting [desktop view] on the mobile.
♧ ♧ ♧ ♧ ♧ ♧
이번에는, 두
자연수를 소인수로 분해하지
않고도, 최대공약수를 쉽게
구해 낼 수
있는 '유클리드 호제법' 을 알아
보도록 할까요?
This time, I'd like to introduce 'Euclidean
algorithm', which is another simple method to find out GCF without prime
factorization.
우선, 198 과
120 의 최대공약수를 유클리드
호제법으로 구하는 요령을
설명한 다음에 그
원리를 알아 보도록
하지요.
As a first step, let me just show you how it
works, with two numbers - 198 and 120.
(1) 큰
수를 작은 수로
나누어 몫과 나머지를
구한 후에, 아래와
같이 식으로 적어
놓습니다.
Divide the larger number, 198 by the smaller
number, 120. Write down the algorithm equation as follows :
198 = 120 x 1
+ 78
(2) 이번에는, 나누었던 수 120 을 나머지인 78 로 나누고
나서, 같은 방법으로
식을 적어 넣습니다.
This time, divide the original divisor 120, by
the remainder 78. Write down the equation in the same way.
120 = 78 x 1 +
42
(3) 같은
계산과정을 반복해서, 최종
나머지가 0 이 될
때까지 계속합니다.
Repeat the same process until the final remainder
becomes zero.
78 = 42 x 1 +
36
42 = 36 x 1 +
6
36 = 6 x 6 + 0
(4) 나머지가
0 이 되었을 때의
나누는 수 (또는
그 직전
계산식의 나머지) 인
6 이 두 수의
최대공약수입니다.
When the remainder becomes zero, the divisor at
this point ( or the final non-zero remainder), 6 in this example, is GCF of 198
and 120.
그러면, 유클리드
호제법의 원리를 알아
보도록 할까요?
Then, let's investigate the principles behind 'Euclidean
algorithm'.
(1) 앞에서, A 를 B 로 나누면, 식으로는
아래와 같이 표현한다고
배웠지요?
As we learned before, when we divide A by
B, mathematical expression should be :
A = B x Q + R
(2)
여기서, A 와 B 의 최대공약수를
G 라고
하면, A = a x
G 그리고 B = b x G 이니까,
위의 식에다 대입을
하고 나서, 나머지
R 에
관해서 정리하면,
Here,
let G be GCF of A, B, and then we can express as A = a x
G, B = b x G, where a,
b are relatively prime.
a x G = b x G x Q + R
∴ R = a x G – b x G x Q
= G x (a – b x Q)
(3) 즉, 나머지 R 도 최대공약수
G 의
배수가 된다는 뜻이
됩니다.
This
means that the remainder R is also a multiple of G.
2400
년 전에
유클리드가 발견한 이
의미를 식으로 정리해
볼까요?
Let's
summarize what Euclide found out 2,400 years ago.
A
= B x Q + R 이라 할
때, A, B
의 최대공약수는, 나누는
수 B 와 나머지
R 의
최대공약수와 같다.
When
A = B x Q + R, the GCF of A and B is equal to the GCF
of B and R.
G (A, B) = G (B, R)
똑같은 문제를 도형의
문제로 바꾸어서 살펴보도록
할까요?
We'are
going to convert the same example into geometry question, as follows :
198 x 120 인
직사각형의 바닥을, 정사각형의
타일로 채우려고 한다. 최소의 타일을 사용하려면, 정사각형
한변의 길이를 얼마로
해야 하는가?
We're
going to cover a rectangular floor that measures 198 x 120 with square floor tiles.
What will be the side length of a square, if we'd like to use the minimum
number of floor tiles?
(1)
유클리드 호제법을 도형적으로
나타내면 아래의 그림과
같습니다.
Euclidean
algorithm can be visualized geometrically, as follows :
(2)
위 그림에서
가장 큰 직사각형이
198 x 120 인
바닥의 크기이고, 첫
번째의 빨간색 정사각형
한 변의
길이가 120 입니다.
The
largest rectangle is a floor that measures 198 x 120 and the first red shaded
square has side length of 120, as shown above.
(3)
이렇게 남는 변의
길이를 정사각형으로 채워나가다
보면, 위의 그림에서와
같이 마지막으로 주황색의
가장 작은 6 개의 정사각형으로
채워지게 됩니다. 이
때의 정사각형 한
변의 길이가 6 인 최대공약수입니다.
Repeat
dividing the remaining side length with smaller square, then we will finally
get six orange shaded squares, as shown above. This is the GCF that we're
looking for. Therefore, the side length of the square tile should be 6.
마지막으로,
연습문제를 하나 풀어
보도록 할까요?
Finally,
let's try a review exercise.
두 자연수 16082 와 4902 의 최대공약수를
구하여라.
Find
the greatest common factor of 16082 and 4902.
두 수가 짝수라는
것 외에는, 쉽게 소인수분해를 하기가
어렵지요? 이 때에는
[유클리드
호제법] 을 사용하면
쉽습니다.
It's
not easy to factorize these two numbers ... Then, we can use the technique of
'Euclidean algorithm'.
(1)
큰 수
16082 를 4902 로 나눈다.
Divide
the larger number 16082 by 4902.
16082 = 4902 x
3 + 1376
(2) 유클리드
호제법의 원리에 따라, G (16082, 4902) = G (4902, 1376) = ... 가 성립한다고
했으니까, 다시 4902 를 1376으로 나눈다.
Divide 4902 by 1376 according to the principles
of Euclidean algorithm, G (16082, 4902) = G (4902, 1376) = ...
4902 = 1376 x 3
+ 774
(4)
나누어 떨어질 때까지, 같은 방법으로 계속해서
계산해 나가면,
Repeat
the same process until we get zero remainder.
1376
= 774 x 1 + 602
774
= 602 x 1 + 172
602
= 172 x 3 + 86
172
= 86 x 2 + 0
(5)
유클리드 호제법의 원리에
따라서, 최대공약수는 86.
After a successive long division process, as
shown above, the answer is 86.
G (16082, 4902)
= G (4902,
1376)
︙
= G (172,
86)
= 86
이 방법은 다항식들의
최대공약수를 구할 때에도
사용됩니다. 뒤의 [다항식의
약수와 배수] 단원에서 공부하도록
합니다.
This
technique is also applicable to polynomials, which we're going to study later.
Comments
Post a Comment