정수론

정수론이란?

소수, 약수, 배수, 나머지, 합동식, 디오판틴 방정식 등을 다루며, ‘수학의 왕자’ 가우스가 극찬했을 정도로 고대부터 이어져 온 가장 근본적인 학문

GCD와 확장 유클리드 알고리즘

최대공약수(GCD)

최대 공약수는 둘 이상의 수를 구성하는 수들중 공통적으로 들어가는 구성요소의 수 중 가장 큰 수를 의미합니다.

GCD(80,40) = 40

이떄 소인수 분해를 이용하면 쉽게 구할 수 있지만 컴퓨터 세상에서는 O(log N)의 시간 복잡도를 가진 해당 알고리즘은 조금 오래 걸릴수 있습니다.

유클리드 알고리즘

이때 유클리드 알고리즘을 활용하면 해당 수를 빠르게 구할 수 있는데요. 유클리드 알고리즘은 2가지 알고리즘을 가정하고 진행하겠습니다.

• a > b인 양의 정수 a,b에 대하여 a를 b로 나눈 나머지를 r로 정의하면, a,b의 최대공약수와 b,r의 최대공약수는 동일하다.
• a > 0 일때, a, 0의 최대공약수는 a로 정의된다.

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b);

확장 유클리드 알고리즘

def xgcd(a, b):
	if b == 0:
		return a, 1, 0
	
	g, x1, y1 = xgcd(b, a % b)
	x = y1
	y = (g - a * x) // b
	assert a * x + b * y == g
	
	return g, x, y

합동식과 중국인의 나머지 정리

합동(Congruence)

두 정수 a, b를 각각 양의 정수 m으로 나머지가 동일한 경우 “a, b를 m에 대하여 합동” $a\equiv b(\mathrm{mod}n)$