확장된 유클리드 알고리즘유클리드 알고리즘에서 다루었던 베주 항등식에 의해 최대 공약수는 $gcd(a,b)=g =ax+by$ 의 선형 결합꼴로 나타난다는 것을 알고있다. 확장된 유클리드 알고리즘은 유클리드 알고리즘을 따라가면서 이 선형방정식의 해 $x,y$를 구하는 방법이다. 예시를 따라가는게 이해하기 쉽다. $gcd(56,15)$을 유클리드 알고리즘을 이용하여 구해보자. $a=56,b=15$ 유클리드 알고리즘$56= 15\cdot3+ 11$$15 = 11 \cdot 1+ 4$$11= 4\cdot2 +3$$4= 3\cdot1 +1$$3= 1\cdot 3 +0$ $gcd(56,15)= 1 =56x+15y$ 확장된 유클리드 알고리즘확장된 유클리드 알고리즘은 $gcd(a,b)=g= ax+by$를 만족하는 $x,..

합동$a,b\in\mathbb{Z}, m\in\mathbb{N}$ 에 대해서 $m|(a-b)$ 이면 $a$와 $b$는 모듈러 $m$ 에 대한 합동이라고 하고 다음과 같이 쓴다. $a\equiv b \pmod m$ 대충 $m$에 대한 두 수 $a,b$의 나머지가 같다는 말이다. 합동 모듈로 $m$의 대수적 성질합동의 정의를 이용하여 유도하고 증명할 수 있다. $a,b,c,d \in \mathbb{Z}, n\in\mathbb{n}$ 에 대하여 $a\equiv b \pmod m, c\equiv d\pmod m$이면 다음을 만족한다. 1. $(a+c)\equiv (b+d)\pmod m$양변에 같은 모듈로 $m$에 대하여 합동인 수는 더하고 빼줘도 됨. 2. $ac\equiv bd\pmod m$양변에 같은 모듈로..

산술의 기본정리 (Fundamental Theorem of Arithmetic)산술의 기본정리는 모든 물질이 원자로 구성되듯, 모든 정수가 소수로 구성되는 것을 말해준다.1보다 큰 정수는 소수의 곱으로 표현되며, 이 표현이 유일하다.$1 증명1. ‘소수의 곱으로 표현된다’는 존재성을 증명해보자. 귀류법소수의 곱으로 표현되지 않는 정수가 있다고 가정하고 그 중에 가장 작은 수를 $n$이라고 하자. (well ordering pirinciple)$n$이 소수라면 거짓이므로 증명이 끝난다.따라서 $n$은 합성수인데, 소수의 나뉨성 정리에 의해 모든 정수는 소수에 의해 나누어 떨어지므로 $n = p_1r$ 이고 $r|n$이다.$r따라서 $n=p_1r$이므로 소수들의 곱으로 표현된다. 이는 $n$의 정의에 모순된..

나머지 정리$n \in \mathbb {Z}$, $d\in \mathbb{N}$, unique $\exists q,r\in \mathbb{Z}$ s.t $n=qd+r, \quad 0\leq r정수 $n$과 자연수 $d$에 대해서 $n=qd+r$을 만족하는 유일한 정수 $q,r$이 존재한다.$q$는 몫, $r$은 나머지라고 부르는데, 다음 표기법으로 몫과 나머지를 표현한다 :$q=a \ div \ d, \ r= a\bmod d$ 유클리드 알고리즘(유클리드 호제법)일반적으로 소인수 분해를 통해서 최대 공약수 구한다. 그런데 수가 존나게 크면 소인수분해에 많은 시간이 걸리기 때문에 최대 공약수를 구하는 것이 쉽지 않다. 유클리드 알고리즘은 이를 매우 단축시킬 수 있는 방법을 제공한다.$a,b(a>b)\in \..

소수와 약수현대 암호학은 정수론을 활용한다. 소수와 약수는 정수론의 논의를 시작하기 위한 첫걸음이다. 여기서는 소수와 약수에 대해서 정의하고, 결과적으로는 모든 물질을 이루는 원자와 같이 모든 정수는 소수로 이루어지는 것을 알아볼 것이다. (소인수 분해의 유일성(산술의 기본정리)). 약수(나누어 떨어짐)$n,d\in \mathbb{Z}, d\neq0 \\ d|n \Leftrightarrow \exists k \in \mathbb{Z}$ s.t. $n=dk$정수 $n,d$에 대해 $n=dk$를 만족하는 정수 $k$가 존재하면 $d$를 $n$의 약수라고 하고, 다른 말로 $n$이 $d$로 나누어 떨어진다고 한다. 나뉨성의 추이성(약수의 추이성)$a,b,c \in \mathbb{Z}, \quad a|b$ an..

임의의 프로그램이 끝나지 않고 반복할지 정지할지 완벽하게 판별할 수 있는 알고리즘은 존재할 수 없다. 또한 정수는 컴퓨터로 표현할 수 있지만 실수는 표현할 수 없다. 이렇듯 만능일 법한 컴퓨터도 근본적인 한계에 의한 해결할 수 없는 문제들을 가지고 있다. 집합의 크기(기수)서수: 순서를 나타내는 수 (ordinal number)기수: 크기를 나타내는 수(cardinal number) 유한 집합의 크기는 원소의 갯수를 통해서 정의한다. 그렇다면 자연수, 정수 집합 같은 무한 집합은 크기를 어떻게 정의할까? 놀랍게도 무한집합도 크기가 존재하며 심지어 다르기도 하다. 무한의 개념에서 크기는 모호한 표현이기 때문에 이제부터 크기 대신 기수라는 표현을 사용한다. 기수는 원소의 갯수가 아니라, 원소들의 일대일 대..

함수함수를 정의하고 증명한다. 데카르트곱(cartesian product, 곱집합)$A,B$ : sets$A\times B = \{ (a,b)| a\in A, b\in B\}$ ; A cross B 관계곱집합에서 특수한 조건을 만족하는 부분집합을 관계라고 한다.A,B ; sets, $A\times B = \{(x,y)|x\in A, y\in B\}$$xRy\Leftrightarrow (x,y) \in R \subseteq A\times B$ 함수의 정의 두 집합 $X$(정의역, domain)와 $Y$(공변역, codomain) 사이의 곱집합에서 다음 조건을 만족하는 관계를 함수$f$라고 한다.$f:X\to Y$1 .$\forall x\in X, \exists y\in Y \ s.t.\ (x,y)\in f..

기초 집합론수학은 같은 성질을 가지는 수학적 대상을 모아서 연구하는 방향으로 발전했다. 우리가 흔히 사용하고 있는 함수도 집합으로부터 시작한다. 집합의 기본 정의집합$A = \{ x\in S| P(x)\}$; $P$를 만족하는 $S$의 원소를 모은 집합 부분집합$A\subseteq B \Leftrightarrow \forall x, x\in A \to x\in B$ 진부분집합$A\subsetneq B \Leftrightarrow A\subset B$ and $\exists x \in B$ s.t. $x\notin A$ 집합의 상등$A= B \Leftrightarrow A\subseteq B$ and $B\subseteq A$ 집합의 연산$A\subseteq U$ and $B \subseteq U$$A\..

술어(명제 함수)유한 개의 변수들을 가진 문장. 특정 변수를 대입하면 명제가 된다. 술어(predicate)를 명제함수(propositinal function)라고도 한다. 술어는 함수이므로 적절한 정의역이 있다. 공역은 참/ 거짓 두 가지 값을 가진다.$P(x):D\to${true, false} 진리집합(truth set)명제 함수의 결과가 참인 원소들의 집합을 진리집합이라고 한다.$P(x) :D\to$ {true, false} ; 명제함수{$x\in D| P(x)$ is true} ; 진리집합 한정화 명제전칭 한정자(unimersal quantifier, $\forall$) : forall (모든 x에 대해서)존재 한정자(existential quantifier, $\exists$) : there e..

논리와 증명수학이든 프로그래밍이든 올바른 논증을 해야 오류에 빠지지 않고 신뢰할 수 있는 올바른 결론에 도달할 수 있다. 주어진 명제들이 믿을 수 있는 진실인지, 주어진 논증이 과연 정당한지 파악할 수 있는 방법에 대하여 알아보자. 논리적 동치(logical equivalence)논리적 동치를 잘 알고 있다면 같은 말도 더 간단하게 할 수 있다. 예를 들면 복잡하게 얽혀있는 조건문을 더 간단하고 알아보기 쉽게 쓸 수 있다. 명제 변수 $p,q,r$, 항진명제 $t$, 모순명제 $c$ 라고 하자. 다음은 논리적으로 동치이다.1. 교환법칙 $p\land q \equiv q\land p, \quad p\lor q \equiv p\lor q$2. 결합법칙 ..