#2-1. 기초 정수론(2)

 
 

기초 정수론 (2) 1. 모듈러 연산 & 합동 2. Zn & Zn*

 
 

1. 모듈러 연산 & 합동

 

합동 (Congruent) - a, b: 임의의 정수 - n ≥ 2: 정수 - a ≡ b (mod n) <=> n l (a - b) & n l (b - a) <=> a, b를 n으로 나눈 나머지가 같다.

 
계산 방법
 
- 정수처럼 연산한 뒤에 나머지 계산
20 + 2 (mod 5) = 22 = 2
7 x 3 (mod 5) = 21 = 1
 
- 중간에 나머지로 바꾼 다음 계산해도 무방
20 + 2 (mod 5) = 0 + 2 = 2
7 x 3 (mod 5) = 2 x 3 = 6 =1
 

합동의 성질 정리 a ≡ a (mod n) a ≡ b (mod n)이면 b ≡ a (mod n) a ≡ b (mod n)이고 c ≡ d (mod n) 이면      a + c ≡ b + d (mod n)      a - c ≡ b - d(mod n)      ac ≡ bd (mod n) a ≡ b (mod n)이고 m l n이면 a ≡ b (mod n)

 
-> 기본적인 덧셉과 곱셈에 대한 연산 성질을 만족하며 교환법칙, 결합법칙, 분배법칙이 성립한다.
 
 
항등원 & 역원
 
덧셈에 대한 항등원 : 0
덧셈에 대한 역원 : -a
곱셈에 대한 항등원 : 1
곱셈에 대한 역원 : 항상 존재하는 것은 아님
 
 
역원?
연산결과가 항등원이 나오게하는 값
 
 
 

Mod n에서 곱셈에 대한 역원

GCD 정리 - a, n: 임의의 정수 & d = gcd (a, n)0 => 1)  as + nt = d를 만족시키는 두 정수 s, t가 존재한다. (유일하지는 않음)      2) a, n을 위와 같은 방식으로 결합했을 때 gcd(a, n)이 얻을 수 있는 최소의 자연수이다.          (즉, 임의의 두 정수 s', t'에 대해  |𝑎𝑠 ′ + 𝑛𝑡 ′ | ≥ 𝑑)

곱셈에 대한 역원 존재성 - a: 임의의 정수, n ≥ 2: 자연수 - a가 mod n으로 역원이 존재할 필요충분조건은 gcd(a, n) = 1

 
 
 

곱셈에 대한 역원 구하기

 
ex)
a = 1180, n = 482

1) 1180 = 2 x 482 + 216      216 = 1180 - 2 x 482 2) 482 = 2 x 216 + 50      50 = - 2 x 1180 + 5 x 482 3) 216 = 4 x 50 + 16      16 = 9 x 1180 - 22 x 482 4) 50 = 3 x 16 + 2      2 = -29 x 1180 + 71 x 482 5) 16 = 8 x 2 + 0

=> gcd (a, n) = 2 = 1180 x (- 29) + 482 x 71
 
 
 
 
 

2. 𝒁n & 𝒁n*

 
잉여류
: 나머지들이 같은 숫자들의 집합
=> mod n 위에서 일반적으로 각 잉여류를 0, 1, 2, ..., n-1 로 표기함
 
 
𝒁n: 완전 잉여계
= { 0, 1, ... , n - 1}
 
𝒁n*: 기약 잉여계
: 𝒁n의 원소 중에서 곱셈에 대한 역원이 존재하는 숫자들의 집합.
(n과 서로소인 숫자의 집합)
 
𝒁n* 원소의 개수
오일러 ϕ 함수
n(𝒁n*) = ϕ(n)
 

페르마의 작은 정리 (Fermat's Little Theorem) p: 소수 a: p와 서로소인 임의의 정수 a^(p-1) = 1 (mod p)

 

오일러의 정리 (Euler's Theorem) n: 자연수 a: n과 서로소인 임의의 정수 a^(ϕ(n)) = 1 (mod n)

=> 오일러의 정리는 페르마의 작은 정리의 일반화이다. 오일러의 정리에서 n을 소수 p로 제한하면 페르마의 작은 정리와 같아진다.