์๋ ํ์ธ์, ์ ๋์ฐ์ ๋๋ค. ์ ํด๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ๊ณผ ํ์ฅ ์ ํด๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฒ์ ๊ณต๋ถํ๋ฉด ์ดํด๊ฐ ์ด๋ ต๊ธฐ๋ ํฉ๋๋ค.๊ทธ๋ด ๋์๋ ์ํ์ ๊ด๊ณ๋ฅผ ์ค์ ์ ์ผ๋ก ์ดํด๋ณด๋ฉด ์ดํด์ ๋์์ด ๋ฉ๋๋ค.๋ณธ๋ฌธ์์ ์์ธํ ๋ค๋ฃฐ ํฐ์ด๋ ์ดํด์ ๋์์ด ๋์์ผ๋ฉด ์ข๊ฒ ์ต๋๋ค. 1. Euclidean Algorithm์ ํด๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ (์ ํด๋ฆฌ๋ ํธ์ ๋ฒ)์ ๋ ์์ ์ต๋๊ณต์ฝ์๋ฅผ ๋น ๋ฅด๊ฒ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ๋ค์๊ณผ ๊ฐ์ ๋ ๊ฐ์ง ์ฌ์ค์ ๊ธฐ๋ฐ์ ๋ก๋๋ค.1. $gcd(a, b) == gcd(b, r)$ ($r = a\: mod \: b$, $a > b > 0$์ธ ์ ์)2. $gcd(a, 0) = a$$gcd(a, b) = gcd(b, a \mod b)$ ์ฆ๋ช ๊ท๋ฅ๋ฒ์ ์ฌ์ฉํด 1์ ์์ด ์ฐธ์ด ๋จ์ ์ฆ๋ช ํ๊ฒ ์ต๋๋ค.[Proof]gcd(a, b) == gcd..
