Hell World Coding and Math Hell World Coding and Math

Math/Number Theory

• [정수론] 합동식3. 중국인의 나머지 정리

  Math/Number Theory 2023. 8. 3. 22:02

  이전 글에서 합동식 $ax \equiv b \bmod n$을 푸는 방법을 알아보았다. 우선, 해가 존재할 조건은 바로 $d = \mathrm{gcd}(a, n)$에 대해 $d \mid b$인 것이다. 또, $x_0$이 위의 합동식의 한 해일 때 $x = x_0 + (n/d)t$ $($단, $t = 0, 1, ..., d-1$$)$가 다른 해임을 알아보았다. 이번 글에서는 여러개의 연립 합동식을 푸는 방법을 알아볼 것이다. 연립 합동식 이제, 다음과 같은 서로 다른 $r$개의 합동식을 생각해보자. $$a_1x \equiv b_1 \bmod m_1$$ $$a_2x \equiv b_2 \bmod m_2$$ $$...$$ $$a_rx \equiv b_r \bmod m_r$$ 이 연립 합동식을 풀어볼 것이다..

  Read More
• [정수론] 합동식2. 선형 합동식

  Math/Number Theory 2023. 7. 6. 21:43

  디오판토스 방정식 디오판토스 방정식은, 정수만을 해로 가질 수 있는 다항 부정방정식이다. 대표적으로 $x^2 + y^2 = z^2$과 같은 방정식이 있으며, 이는 당연히 $x=3,y=4,z=5$와 같은 해를 갖는다. 그 중에서 $ax+by=c$와 같은 형태의 디오판토스 방정식은 해의 존재성과 관련하여 한가지 정리가 있다. Theorem. 선형 디오판토스 방정식 $ax+by=c$는 $d=\mathrm{gcd}(a,b)$에 대해 $d \vert c$일 때만 해를 갖는다. Proof. 필요충분조건이므로, 두 경우에 대해 모두 증명해보겠다. $d=\mathrm{gcd}(a,b)$라면, 어떤 정수 $r, s$에 대해 $a=dr, b=ds$로 나타낼 수 있다. 이때, $ax+by=c$의 해가 존재한다면, 어떤 정수..

  Read More
• [정수론] 합동식1. 합동식의 정의

  Math/Number Theory 2023. 7. 4. 21:41

  합동식의 정의 Definition. 양의 정수 $n$과 두 정수 $a, b$에 대하여 만약 $n \vert (a-b)$라면, 법 $n$에 대하여 $a$와 $b$는 합동이라고 하며, 기호로는 $a \equiv b \bmod n$ 으로 나타낸다. 즉, 정수 $n$이 $a-b$를 나눈다면, 즉 $a-b$가 $n$으로 나누어 떨어진다면 $n$에 대하여 $a$와 $b$는 합동인 것이다. 반대로 $a-b$가 $n$으로 나누어 떨어지지 않는다면 $a$와 $b$는 합동이 아니다. 다르게 표현한다면, $\exists k \in \mathbb{Z}\, \mathrm{s.t.} \, a - b = nk$ 라면 $a \equiv b \bmod n$ 이다. 몇가지 예시를 생각해보자. $3 - 24 = -21$인데, $7 \ve..

  Read More