일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- GitHub
- architecture
- MiTweet
- Kotlin
- boj
- 쿠링
- 프로그래머스
- textfield
- pandas
- relay
- 백준
- AWS
- Python
- Codeforces
- ProGuard
- Coroutine
- Gradle
- android
- livedata
- 암호학
- TEST
- Coroutines
- Compose
- activity
- Hilt
- 코루틴
- 코드포스
- Rxjava
- androidStudio
- MyVoca
- Today
- Total
이동식 저장소
10주차 2차시 본문
Complete Residue System
우리는 곱셈과 나눗셈이 잘 정의되는 Residue System을 원한다.
Reduced Residue System Z∗m={a|gcd(a,m)=1, 0≤a<m}
∀a∈Z∗m, ∃ x ax=1modm
(ab)c=a(bc)modm (곱셈의 결합법칙) 증명
사실
Real Number System
Residue System이 어색할 수도 있으므로, 실수 집합에서 이야기해 보자.
실수란 무엇인가? 사실 실수라는 말 자체가 정의된 것은 아니다. 대신 실수 집합에서 성립하는 성질을 Axiom
, 즉 공리라고 하여 공리가 성립할 때 실수 집합에서 어떤 일이 일어나는지 관찰한다.
예를 들어
물론 아무거나 다 공리로 놓을 수는 없다. 예를 들어 서로 다른 역원이 2개 존재하는 System은 생각할 수 없다. 역원이 존재한다면 반드시 하나만 존재한다는 사실을 증명할 수 있기 때문이다. "내 시스템에서는 역원이 2개 존재해!"라고 우길 수는 있어도, 그 시스템에서 의미있는 사실을 이끌어낼 수는 없을 것이다.
다시 돌아와서
소수
오일러의 정리
그러면 등식이 성립하도록 하는
a∈Z∗m→aφ(m)=1modm (φ(m)=|Z∗m|)
예를 들어
증명
따라서
좌변을 정리하면
페르마의 정리
페르마의 정리는 오일러의 정리의 특수한 경우이다.
가 소수이고p 일 때a∈Z∗p 이다.ap−1=1modp
특수한 경우이므로 증명은 더 쉽다. 여기서는 생략.
중국인의 나머지 정리
중국인이는 말이 붙은 이유는 이 정리가 실제로 중국의 수학책에 쓰여 있었기 때문이다.
이때 임의의
증명
정말로 그러한가?
응용
중국인의 나머지 정리를 이용하여 큰 수의 곱셈을 빠르게 계산할 수 있다. 곱하고자 하는
정수론을 마무리한다. 다음 시간에는 실제로 사용되는 암호에 대해 알아보자.