Number Theory [정수론]

Source (참고문헌)

정수론의 가장 기본적인 내용으로 다음의 3 가지 성질을 살펴보자.

진법 - 자연수의 표현법 (The Representations of Natural Numbers)

물건의 포장방법으로 이해
예 : 주판
많이 사용하는 진법의 예
- 10진법 --- 일상생활에 가장 많이 사용하는 수의 표현법
- 2진법 --- switch, 논리 (2價 논리, 일종의 흑백논리), 컴퓨터 회로 등.
- 60진법 --- 나이 환산법 (환갑), 시간 (1시간=60분) 등.
- 12진법 --- 시간 (1년=12개월), 연필의 묶음 (1 다스=12자루) 등.
- 24진법 --- 시간 (하루=1일=24시간)
- 7진법 --- 시간 (1주=7일), 음계 (도,레,미, . . . , 1옥타브=7음)

진법의 변환

참고 : 수의 체계 (Number System)
실수(real numbers)는 유리수와 무리수로 이루어짐
유리수란 분수로 나타낼 수 있는 수
무리수는 분수로 나타낼 수 없는 수

실 수	유 리 수	무 리 수
분수인가?	Yes	Yes
순환소수인가?	No	No

실수는 정수부분과 소수부분으로 나눌 수 있고,
정수부분과 소수부분을 따로 따로 진법변환을 한 후,
그 결과를 더하여 실수의 진법변환을 한다.
진법으로 표현된 실수의 의미:
정수의 변환
소수의 변환
참고 또는 비교 : 무한 등비급수의 합

인수분해 (The Factorizations of Natural Numbers)
1. 소수 (prime numbers) :
  1 과 자기 자신 외의 다른 양의 정수로 나누어 떨어지지 않는 정수.
2. 소수는 정수를 구성하는 building block(기본 구성 요소, 성분)
  예: 소수는 화학에서의 원자(atoms)에 해당.
3. 소인수분해 정리 :
  임의의 양의 정수는 소수의 곱으로 표현되며,
  그 표현방법은 소수의 순서를 무시할 경우 유일한 방법으로 표현된다:
  여기서 은 서로 다른 소수들.
4. 정리 (Legendre, Gauss 에 의한 실험적 결과, 참고문헌 95쪽, 정리 4.10).
  자연수 이하의 소수의 개수는 약 개.
5. 정리 (Euclid, 참고문헌, 정리 4.11).
  소수는 무한히 많다.
6. 참고: 소인수분해를 효과적으로 할 수 있는 알고리즘이 없어서 암호학에도 이용됨.
7. 최대공약수가 1인 두 개의 정수는 서로 소(relatively prime)가 된다고 말한다.
8. 오일러 함수 (Euler function)
  보다 작은 정수 중 과 서로 소(relatively prime)인 정수의 개수
나머지 계산법 (Modulo Arithmetic) --- 법 (Modulus)
1. 을 정해진 정수라고 할 때,
  으로 나누어 나머지가 같은 두 개의 정수 와 를
  mod 으로 합동(congruent)이라 하고,
  (mod ) 으로 표현한다.
2. 임의의 정수 는 주어진 정수 으로 나누면
  으로 표현된다.
  (여기서 는 몫이고, 은 나머지로 이다)
  그러므로, 법(modulus)으로 계산하면 모든 정수는
  1 에서 의 정수 중 하나에 대응된다.
3. 나머지가 같은 정수들을 모아 하나의 집합으로 표현하자:
  예를 들면, 인 경우, 나머지가 2 인 정수들의 집합을 로 쓰기로 하자.
  그러면, (mod 이 된다.
  더 나아가, 또한 나머지가 2인 정수들의 집합으로 사용한다.
  즉, (mod 이다.
4. 이제, 나머지가 같은 정수들의 집합을 원소로 하는 집합을 생각할 수 있다.
  예를 들면, 인 경우, 가 그러한 집합으로
  이 집합 상에서 나머지만을 중요시하는 계산도 가능하다.
  예를 들면, 이며 이다.
  왜 그런지 살펴보고, 다른 계산도 스스로 몇 개 더 해보자.