Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

호제법1

유클리드 호제법 알아보기 유클리드 호제법이란? 양의 정수

$a, b$ 와

$a=bq+r$ 인 정수

$q, r$ 에 대해

$gcd(a, b) = gcd(b,r)$ 이다. (이때

$gcd(a,b)$ 는

$a, b$ 의 최대공약수이다.) 증명하기 유클리드 호제법을 이용해 두 양의 정수의 최대공약수 구하기 두 양의 정수

$a, b$ 에 대하여

$a$ 를

$b$ 로 나누면

$a=bq_1+r_1$ , (

$0 \leq r_1 < a$ )를 만족시키는 정수

$q_1, r_1$ 이 존재한다. (1)

$r_1 = 0$ 이라 하고

$b$ 를

$r_1$ 으로 나누면

$b=gcd(b,r_1) = gcd(a,b)$ 이다. (2)

$r_1 \neq 0$ 이라 하고

$b$ 를

$r_1$ 으로 나누면

$b=q_2r_1 + r2$ , (

$0 \leq r_2 < r_1$ )을 만족시키는 정수 .. 2023. 1. 12.

이전 1 다음

티스토리툴바