수학 유클리드 호제법(Euclidean algorithm)


유클리드 호제법에 대해서 알아보겠습니다.

유클리드 호제법을 사용하면, 최대 공약수(Greatest common factor)를 쉽게 구할 수 있습니다.


G(a, b) = G(b, r)
여기서 r는 a/b의 나머지

1024와 54로 예를 들어보겠습니다.
G(1024, 54) = G(54, 52) = G(52, 2) = G(2, 0) = 2
즉, 1024와 54의 최대 공약수는 2입니다.

1024 = 1, 2, 4, 8, 16, 32, 64, 128, ,256, 512, 1024
54 = 1, 2, 3, 6, 9, 18, 27, 54


증명은 아래와 같습니다.


G(a, b)를 a와 b의 최대 공약수로 정의를 내립니다.

유클리드 호제법은 a와 b가 정수(Ζ)이고, 조건 a ≥ b, b > r ≥ 0를 만족할 때, a = bq + r가 성립됩니다.
이때, G(a, b) = G(b, r)을 나타내고 있습니다.





















끝.


카테고리: Math

댓글

이 블로그의 인기 게시물

Python urllib.parse.quote()

Python OpenCV 빈 화면 만들기

Android Notification with Full Screen

tensorflow tf.random.uniform()

Android AVD Ram size change

Python bs4.SoupStrainer()

Android Compose automation for getting localized images to use on Play Store app image

Forensics .pyc 파일 .py로 복구하기

KiCad 시작하기 2 (PCB 만들기)

KiCad 시작하기 7 (FreeRoute 사용하기 2)