정수론1

1. Algebra, Group, Ring
 

1. Algebra(대수)
:  집합 K와 여러 연산자들로 이루어진 구조

• <R,+,−,×,÷> : 실수 집합 R과 덧셈, 뺄셈, 곱셈, 나눗셈 같은 연산자들로 정의되는 구조
• <{T,F},∧,∨,¬>: Boolean 대수에서 참(True)과 거짓(False)을 AND, OR, NOT으로 연산.
• K: 데이터의 집합으로 |K∣는 집합의 크기(유한 또는 무한)를 나타낸다.
• 연산자 op: 단항(Unary, i=1), 이항(Binary, i=2)연산으로 나뉜다.
• ("연산자"는 중요한 역할을 하는데, 연산자가 결합법칙이나 항등원 등의 성질을 만족시키는 지에 따라 다양한 수학적 구조로 구분한다.)

2. Identity(항등원)와 Zero(영원)

• 항등원은 어떤 연산 ⊕에 대해, 항등원 e는 e⊕a=a⊕e=a를 만족하는 원소

{Z,+}에서 항등원은 0이다. 즉, 0+a=a+0=a이다. {Z,x}에서 항등원은 1이다. 즉, 1*a=a*1=a이다.

• 영원 z는 z⊕a=a⊕z=z를 만족한다.

{Z,×}에서 영원은 0이다. 즉, 0×a=a×0=0이다.

 
3. Inverse(역원)
: 연산 ⊕에서 각 원소에 대해 역원이 존재한다. 역원은 항등원을 반환하는 원소를 의미한다.

{Z,+}에서 a의 역원은 −a로, a+(−a)=(−a)+a=0이 성립한다.

 
4. Binary Algebra (이항 대수)

Closure-닫혀있다(포함), Associative-결합법칙(우선순위X), Identity-항등원, Inverse-역원, Commutative-교환법칙(순서change ok)

• Semigroup(반군): 결합법칙을 만족하는 이항 연산을 가진 구조

<Z+,+>는 semigroup이다. 이 연산은 결합법칙을 만족한다. ex) 두 문자열 u와 v의 연결 순서는 상관없이 결과가 동일하다.

• Monoid (단위 반군): 결합법칙과 항등원이 있는 구조
• Group(군): 결합법칙, 항등원, 역원이 존재하는 구조
• Abelian Group(대수군): 결합법칙, 항등원, 역원, 교환법칙까지 만족하는 군

5. Ring and Field (환과 체)

• Ring(환): 2개의 이항연산자 ⊕와 ⊗로 이루어진 집합 K

Ring 조건 → <K,+,×> : 첫번째 연산 +는 abelian group을 이루고, 두번째 연산 x는 결합법칙을 만족하며 분배법칙을 만족한다.

• Field(체): 모든 원소가 곱셈에 대한 역원을 가지는 구조

실수, 유리수, 복소는 Field이지만 정수는 Field가 아니다: 정수는 곱셈에 대한 역원이 존재하지 않기 때문 (1/2는 정수가 아니다.)

2. Modular arithmetic
 

 
1. Modulo n
: 두 정수 a, b가 주어졌을 때 n으로 나눈 나머지가 같다면 a≡b(mod n)이라고 한다.

17≡2(mod 5). 여기서 17을 5로 나눈 나머지가 2이므로 성립한다.

• 모듈러 연산은 동치 관계를 형성하며, 이를 통해 집합을 여러 개의 동치류로 나눌 수 있다. 
• Theorem 1: 모듈러 연산(나머지)이 같다면 합동이다. 
• 모듈러 연산(나머지)이 같다 → n으로 나눈 Z 대해서 equivalence classes이다!

2. Zn 집합
: n으로 나눈 나머지를 동치류로 구성한 집합. 즉, Zn = {[0],[1],[2],...,[n-1]}

• 덧셈과 곱셈 연산 정의할 수 있다. [a]+[b]=[a+b] , [a]×[b]=[ab]

n=7, [2]+[6]=[2+6]=[8]=[1], [2][6]=[12]=[5]

 
3. Theorem 2: Zn은 n>1에서 2개의 연산(+,x)을 만족하는 commutative ring with unity 이다.

• 즉, 덧셈의 항등원인 0과 곱셈의 항등원인 1이 존재한다. 하지만 모든 z가 Field가 되는 것은 아니다.
• Z6에서 2x3=0과 같은 proper divisors of zero가 존재하면 Field가 아니다. Field는 0이 아닌 두 원소를 곱했을 때 0이 나오는 일이 없어야 한다. 

4. Unit

• 역원: Zn에서 a가 역원을 가진다면, a x b=1을 만족하는 b가 존재한다. 이를 a의 곱셈 역원이라고 한다. 
• a와 n이 서로소(공약수가 1)일 때만 Zn에서 a는 역원을 가진다. 이때 a를 Zn의 Unit이라고 부른다. 즉, 쉽게 말하자면 해당 역원(inverse)을 가지는 a를 unit이라고 한다.

5. Theorem 3: Zn이 Field가 되기 위한 조건은 n이 소수여야 한다는 것이다.

• n이 소수라면 Zn의 모든 0이 아닌 원소는 역원을 가진다 → Zn은 Field가 된다.
• n이 소수가 아니면, Zn에는 0의 진약수(proper divisors of zero)가 존재하여 Field가 되지 못한다.
• Integral Domain: no zero divisor + commutative ring

Bezout's Identity: a와 n이 서로소이면, a×s + n×t = 1을 만족하는 s와 t가 존재한다. 이때, s가 a의 unit이 된다.  → a가 Zn에서 unit(역원)을 가지기 위한 조건은 gcd(a,n)=1, 즉 a와 n이 서로소여야 한다는 것을 알 수 있다.

[1] as + bt = gcd(a,b) [2] Field(inverse)→ Unity

 

Z6에서는 gcd(5,6)=1이므로, 5는 역원을 가지며, [5]의 역수=[5] 이다. 하지만 2×3=0과 같은 0의 진약수가 존재하므로 Z6 Field가 될 수 없다. 즉, proper divisor of zero가 1개라도 있으면 Field 안되고 commutative Ring with Unity에 속한다.

 
6. 오일러 피 함수
: n과 서로소인 n보다 작은 [양의 정수]의 개수를 나타낸다.

n=10일 때, 서로소인 숫자는 1,3,7,9이므로 φ(10)=4이다.

• φ(n)은 1 ≤ m < n인 양의 정수 m 중에서 n과 서로소인 숫자의 개수를 나타낸다.

n=72일 때, φ(72)=24이다.

• 서로소의 개수를 직접 알아내는 것이 아닌 공식을 이용하는 방법? → 소인수분해 이용 or 피 함수 공식 이용

φ(72) = φ(2^3 * 3^2) = (2^3 - 2^2)(3^2-3^1) = 4*6=24, OR 72 * (1 - 1/2)(1 - 1/3) = 24

 

• Corollary(따름정리): n이 소수의 거듭제곱인 경우 If n = p^e, φ (n) = p^(e-1) (p-1). If n = p, φ (n) = n-1

φ (27) = 3^2 (3-1) = 18, φ (11) = 11 – 1 = 10

• 두 수 m과 n이 서로소(gcd(m,n)=1)이면, φ(mn)=φ(m)×φ(n)

φ(270)=φ(10)×φ(27)=4×18=72

• Zn∗과 φ(n): Zn∗는 Zn에서 n과 서로소인 원소들로 구성된 집합 → Z10∗={1,3,7,9}이고, φ(10)=4

Zn​: 교환 환 (Commutative ring with unity) → prime: φ(n) units VS not prime: proper divisors of zero Zp: p가 소수일 때 Field. →  φ(p) = p-1 units Zn∗: Zn에서 n과 서로소인 원소들로 이루어진 Abelian Group (for multiplication)

 
3. Euclidean Algorithm (유클리드 알고리즘)
: 두 정수의 최대공약수(gcd)를 구하는 알고리즘
 

1. GCD 구하기 (Greatest Common Divisor)

• GCD(최대공약수)는 두 정수 a와 b의 공통된 약수 중에서 가장 큰 값을 의미한다.
• 예를 들어 84와 30의 GCD: 각각의 소인수 분해를 통해 공통 소인수인 2*3=6의 결과를 알 수 있다.

2. 유클리드 알고리즘의 아이디어

• 두 수의 GCD를 작은 수들의 GCD 문제로 축소하여 반복적으로 계산하는 것. 이 과정은 나머지 연산을 이용하며, 마지막 나머지가 0이 나올 때까지 반복한다.
• GCD(27,21)을 구하는 과정:
  1. 27=1×21+6 → 나머지 6
  2. 21=3×6+3 → 나머지 3
  3. 6=2×3+0 → 나머지 0
• 마지막 나머지가 0이므로, GCD는 3이다.

유클리드 알고리즘의 단계별 절차는 다음과 같습니다: A=a, B=b R=A mod  B A=B, B=R B=0이 될 때까지 이 과정을 반복하며, 최종적으로 A가 GCD가 됩니다. gcd(a,b) = gcd(b,a mod b) ex) GCD(55,22): 55=2×22+11 22=2×11+0 따라서 GCD는 11

 
3. Recursive Euclidean Algorithm (재귀적 유클리드 알고리즘)

• b=0이면 a를 반환, 그렇지 않으면 GCD(b, a mod b)를 구한다.

 
4. GCD와 Extended Eucludean Algorithm

• 확장 유클리드 알고리즘은 GCD를 구하는 과정에서 추가적으로 두 정수 a,b에 대해 as+bt=GCD(a,b)를 만족하는 계수 s와 t를 찾는다. 이때 s는 a의 inverse이다. 
• 모듈러 역원 구하기: Bezout's identity 이용해 a×s+n×t=GCD(a,n)을 만족하는 s와 t를 찾는다. GCD(a,n)=1 이면, s가 a의 모듈러n에 대한 역원이 된다. 
• B1 = 이전 A1-QB1, B2 = 이전 A2-QB2, B3 = 이전 A3-QB3 로 계산되며, 이렇게 계산 후 B3가 1이 될 때 해당 B2를 a의 모듈러 역원이라고 한다. 이 때 B3가 1이 나오지 않으면 모듈러 역원은 존재하지 않는다. 

s=355가 모듈러 역원이 된다.