나름 개발자의 IT블로그

인터넷을 찾아보다가 우연히 Online Math Contest라는 사이트를 알게 되었다. 일본에서 운영하는 온라인으로 수학문제을 푸는 대회사이트이다. 딱 앳코더의 수학버전이다. 앳코더나 코드포스처럼 콘테스트에 참여하면 레이팅을 얻고 닉네임에 색을 입힐 수 있는 시스템인 것 같다. 재밌어보여서 바로 가입하고 가장 최근에 있었던 OMC 207 (for beginners)에 도전해봤다. 결과는 2솔하고 손도 못댔다. ㅋㅋ 출제 범위는 고등 ~ 대학 수학정도이고 아직 많이 보진 않았지만 대수학, 정수론, 기하학 위주로 출제되는 것 같다. 스코어보드를 봤는데 사람들 푸는 속도가 어마어마했다. 그리고 수학 대회이기 때문에 코드를 작성하면 부정행위이다. (애초에 코딩으로 해결할 수 있는 문제가 많지 않다.) 대신에 ..

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

지난 시간 가볍게 알아본 Resultant를 활용해보자. 가환대수학에 포함되는 Elimination Theory에 있는 매개변수 함수를 음함수로 나타내는 법을 알아볼 것이다. 아직 Resultant의 성질은 알아보지 않았지만 그래도 충분하다. 음함수와 매개변수 함수 수학적인 함수를 표현하는 다양한 방법이 있다. $y = f(x)$같이 나타내는 양함수(Explicit function), $F(x,y) = 0$같이 나타내는 음함수(Implicit function), $x = f(t), y = g(t)$로 나타내는 매개변수 함수(Parameterized function)가 그 예시이다. 각 표현에 있어서 장단점이 있고 여기에서는 음함수와 매개변수 함수에 주목한다. 우리의 질문은 "매개변수로 표현된 함수를 음함..

다항식의 공통 근 두 다항식 $f, g$가 주어질 때 공통 근이 존재하는지 판단하려면 어떻게 해야 할까? 가장 쉬운 방법은 각각의 근을 모두 구하고 겹치는게 있는지 확인하는 것이다. 하지만 이는 2차 다항식까지는 근의 공식으로 편리하게 확인할 수 있지만 3차 이상으로 올라가게 되면 자명한 근 아니면 찾기 힘들어진다. 한 번 알 방법이 있는지 알아보자. 다항식이 공통 근을 가지려면.. $r$차 다항식 $f(x) = a_r x^r + a_{r-1} x^{r-1} + ... + a_1 x + a_0$과 $s$차 다항식 $g(x) = b_s x^s + b_{s-1} x^{s-1} + ... + b_1x^1 + b_0$이 있다. 다항식이 어떤 근 $\alpha$를 가진다는 것은 $x-\alpha$를 인수로 가진다..

어렸을 때 이런 문제를 푼 기억이 있다. "사탕 $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$는 유리수가 나오므로 피타고라스 세 쌍은 단위원에서..