CT(수의 표현, 유클리드 호제, 페르마의 소정리)

- 수의 표현

1의 배수 
2의 배수 : 짝수
3의 배수 
4의 배수
5의 배수 : 2.5를 이용한 소인수 분해
6의 배수 : 어떤 수든 연속적으로 3번 곱하면 6의 배수가 됨 / (a-1)a(a+1)
7의 배수 : 요일(기준요일 + 경과일), 달력, 13일의 금요일
8의 배수 : 홀수의 제곱 % 8 = 1이 나오는 수(정수의 특징)

 

 

- 유클리드 호제 (큰 수나 어려운 숫자에 대한 GCD를 쉽게 구하는 방법)

1. 큰수를 작은수로 나누어 떨어지지 않기 때문에 큰수를 작은수로 나누어 나머지를 구한다.

2. 작은수를 나머지로 나누어 나머지를 구한다.

3. 2번을 계속 반복적으로 수행 

    ==> 나머지가 0이 나올때 까지

    ==> 나머지가 0이 될때는 제수가 GCD(최대공약수)이다.

 

ex) (120,150) -> 150%120 = 30 -> (120,30) -> 120 % 30 = 0 -> (0,30)

ex2) (1071,1029) -> 1071%1029=42 -> 1029%42(나머지를 나눠준다) =21 -> 42%21(나머지를 나눠준다, 제수) = 0 

      0이 되면 계산값의 제수가 GCD가 된다.

 

- 페르마의 소정리

만약 a가 정수, p가 소수일 때 

a^p 는 a가 나온다.(mod p를 하였을 때) - 진리

a^(p-1)은 1이 나온다.(mod p를 하였을 때) - 진리

a^(p-2)은 1/a 로 가정한다.(mod p를 하였을 때) - 가정

ex)

2^1 = 2 mod 5 = 2

2^2 = 4 mod 5 = 4

2^3 = 8 mod 5 = 3

2^4 (= 2^(p-1)) = 16 mod 5 = 1  :::: 1이 나온다.

2^5 (= 2^p) = 32 mod 5 = 2 :::: 2(a)가 나온다.

 

조합 문제를 풀 때 이용할 수 있다.(따로 추가적으로 더 공부하기)

7C5 = 7!/2!5! = 7! / 240 = 7! / 9 (mod11) = 7! x 9^9

7C5 = 7!/2!5! = 7! / 2x120 = 7! x 2^9 x 10^9(mod11)