🤣

[Discrete Mathematics] 5. Introduction to Number Theory

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.

Divisor

정수 n,d,qn,d, q에 대해 n=dqn = dq 이면 d∣nd|n이라 한다.
•
d∣m,d∣n→d∣(m+n)d|m, d|n \rightarrow d|(m+n)
•
d∣m,d∣n→d∣(m−n)d|m, d|n \rightarrow d|(m-n)
•
d∣m,d∣n→d∣(m×n)d|m, d|n \rightarrow d|(m\times n)

Modulus Operator

a mod m=r↔a=mq+ra\ {\rm mod}\ m = r \leftrightarrow a = mq + r
a를 m으로 나눈 나머지가 r
•
ab mod z=[(a mod z)(b mod z)] mod zab \ {\rm mod} \ z = [(a\ {\rm mod} \ z)(b\ {\rm mod} \ z)]\ {\rm mod} \ z

Congrument (합동)

m∣(a−b)m | (a-b)일때, aa 와 bb는 mm에 대해 합동이고, 이는
a≡b(mod m)a \equiv b ({\rm mod}\ m) 로 쓸 수 있다.
•
ca≡cb (mod m)ca \equiv cb \ (\rm mod\ m)
•
c+a≡c+b (mod m)c+a \equiv c+b \ (\rm mod\ m)
•
나누기는 안됨

Prime Number and Composite Number

•
nn이 합성수일때, nn은 2≤d<n2 \leq d < \sqrt{n}을 만족하는 Divisor dd를 갖는다.
d′>nd' > \sqrt{n}에 대해 귀류법으로 보일 수 있음
•
소인수 분해는 유일하다 (정수론의 기본정리)
•
소수의 개수는 무한하다.
어떤 소수보다 작거나 같은 모든 소수들의 곱에 +1 하면 그것도 소수라서 소수는 무한함

GCD

Greatest Common Divisor
•
d≥0d \geq 0
•
d∣m,d∣nd|m , d|n
•
e∣m,e∣ne|m, e|n

LCM

Least Common Multiple
•
l≥0l \geq 0
•
m∣l,n∣lm|l, n|l
•
m∣t,n∣t→l∣tm|t, n|t \rightarrow l|t

Euclidean Algorithm

유클리드 호제법
a=bq+ra = bq + r 일때, gcd(a,b)=gcd(b,r)gcd(a,b) = gcd(b,r)
ex)
gcd(504,396)gcd(504,396)을 구해보자.
504 mod 396=108504\ {\rm mod}\ 396 = 108
396 mod 108=72396\ {\rm mod}\ 108 = 72
108 mod 72=36108\ {\rm mod}\ 72= 36
72 mod 36=072\ {\rm mod}\ 36= 0
36 mod 0=036\ {\rm mod}\ 0= 0
따라서 gcd(504,396)=gcd(36,0)=36gcd(504,396) = gcd(36,0) = 36
gcd(252,198)=18=4*252+(-5)*198

Special Result

gcd(a,b)=sa+tbgcd(a,b) = sa + tb (단, a,ba,b는 자연수, s,ts,t는 정수) 로 나타낼 수 있다.

Inverse Modulo

gcd(n,ϕ)=1gcd(n,\phi)=1 일때, ns mod ϕ=1ns\ {\rm mod}\ \phi = 1이 되는 ss를 찾는 계산 과정
gcd(n,ϕ)=1gcd(n,\phi)=1 이면 s′n+t′ϕ=1s'n + t'\phi = 1인 s,ts,t가 존재하고
ns′ mod ϕ=1ns' \ mod \ \phi = 1에서 적당히 s′s'를 조져서 양의 정수 ss로 만들면 됨...