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