나름 개발자의 IT블로그

얼마 전에 ChatGPT를 사용할 일이 있어서 가지고 놀다가 우연히 소수판정 알고리즘을 알려달라고 했는데 다음과 같은 코드를 뱉어냈다. def is_prime(num): if num

어렸을 때 이런 문제를 푼 기억이 있다. "사탕 $N$개를 나눠주는데 $a$개씩 나눠주면 $m_1$개가 남고 $b$개씩 나눠주면 $m_2$개가 남을 때 사탕의 수를 구하시오." 그때는 직접 대입하거나 식을 세워서 풀었던거 같은데 중국인의 나머지정리로도 풀 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem) >> Theorem) $\gcd(m,n) = 1$이고 $x \equiv b \mod m$이고 $x \equiv c \mod n$이면 $x \equiv d \mod mn$인 $d$가 유일하게 존재한다. proof $x \equiv b \mod m$은 $x = my + b$로 쓸 수 있고 이를 두번째 식에 대입하면 $my + b = nz + c$가 된다. 이는 곧 $my - n..

inverse modulo $ax \equiv 1 \mod p$일 때 $x$를 inverse modulo(모듈러 역원)라고 한다. 하지만 언제나 존재하는 것은 아니다. 예를들어 $2x \equiv 1 \mod 4$일 때는 존재하지 않는다. $ax - py = 1$로 나타낼 수 있으니 $\gcd(a,p) = 1$인 경우에만 inverse modulo가 존재한다. $p$가 소수라면 $0 < a < p$에서 $\gcd(a,p) = 1$이니 언제나 존재할 것이다. 고차 합동 방정식 $x^2+1 \equiv 0 \mod m$을 보자. $m = 5$일 때 $x = 2, 3$인 해를 가진다. 그런데 $m = 3$일 때는 해를 가지지 않는다. 이처럼 고차 합동방정식은 $m$이 소수이더라도 해가 존재하지 않을 수 있다...

합동 만약 $m | a-b$라면 $a \equiv b \mod m$이다. 꽤 심플한 정의이다. "$a,b$을 $m$으로 나눈 나머지가 같다"라고도 표현할 수 있다. 예를들어 $5 \equiv 12 \mod 7$이다. 특히 $m=2$라면 짝홀을 구분할 수 있다. 그리고 $0 \le a < m$이고 $a \equiv b \mod m$이면 $b = a+mk (k \in \mathbb{Z})$라고 나타낼 수 있다. 1차 합동방정식 $ax \equiv b \mod m$꼴의 방정식을 1차 합동방정식이라고 한다. 실수세계에서는 단순히 양변을 나눔으로써 해결할 수 있었다. 정수세계에서는 $(\mathbb{Z}, /)$이 이항연산이 아니기 때문에(현대대수 참고) 양변을 나눌 수 없다. 우선 합동방정식을 해결하는 가장 편..

디오판투스 방정식 이름이 거창해보이지만 내용은 정수 계수 부정 방정식이다. 예를 들면 $3x+2y=5$ 이런 것이다. 지난시간에 $ax+by=c$가 정수 해를 가지려면 $\gcd(a,b) | c$를 만족해야 한다고 했다. 이를 이용하여 다양한 작업을 해보자. >> Theorem) 소수 $p$에 대해서 $p | ab$ 이면 $p|a$이거나 $p|b$이다. proof case 1) $p | a$ 자명히 성립한다. case 2) $p \nmid a$ $p$는 소수이므로 $\gcd(a,p) = 1$ 그럼 유클리드 알고리즘에 의해 $ax + py = 1 (=\gcd(a,p))$를 만들 수 있다. 위 식은 해를 가지고 양변에 $b$를 곱하면 $abx + bpy = b$가 된다. $p | abx$이고 $p | bp..

기초부터 되짚어보자. 1. $m \mid n$ : m은 n을 나눈다. 2. $\gcd (a,b)$ : a,b의 최대공약수 3. 소수는 $1$과 자기 자신만으로 나누어 떨어지는 수 4. 나머지정리 : $a = qb + r$ $(0 \le r < b)$ 유클리드 호제법 $\gcd (a,b)$를 쉽고 빠르게(?) 구하는 방법이다. $a_1 = a, a_2 = b$라고 하자. 나머지 정리에 따르면 $a_1 = q_1a_2 + a_3$ $a_2 = q_2a_3 + a_4$ $\dots$ $a_n = q_na_{n+1}$ 같이 언젠가 나머지가 없어지는 때가 온다. 이때 $a_{n+1} = \gcd (a,b)$이다. $2a_{i+2} \le a_{i}$이기 때문에 $log$시간 안에 구할 수 있다. 예를들어 $\g..

학교에서 수학과의 정수론(학교에서의 과목이름은 수론)과목이 전공 인정이 되어 이번에 수강하게 되었다. 시험정리도 하고 알고리즘 정수론 태그 공부도 할 겸해서 포스팅을 하려고 한다. 피타고라스 정리 $a^2 + b^2 = c^2 (a,b,c \in \mathbb{R})$ 위 식은 잘 알려져 있다. 여기서 $(a,b,c) \in \mathbb{N}$으로 범위를 좁혀서 생각해보자. 피타고라스 정리에서 양변을 $c^2$로 나누면 식이 다음과 같이 된다. $\frac{a^2}{c^2} + \frac{b^2}{c^2} = 1$ 이는 단위원 $x^2 + y^2 = 1$에서 $x = \frac{a}{c}, y= \frac{b}{c}$인 점을 나타낸다. 여기서 $x,y$는 유리수가 나오므로 피타고라스 세 쌍은 단위원에서..