(1)포함과 배제의 원리( 포배의 원리)

1)직관적으로 이해하기

그림에서 세 구역으로 이루어져 있다. 


 A 구역에만 들어 있는 A
 B
 A ^B 



A B A^B
1   1
  1 1
------
1 1 2



A B C A^B A^C B^C A^B^C
1      1   1       1
  1    1       1   1
    1      1   1   1
-----------------------
1 1 1  2   2   2   3

A  B  C  D A^B A^C A^D B^C B^D C^D 

4 개 인 경우


한 개자리 더해 A , B , C , D
두개 빼 주고 
세개 더해주고 
네개 빼주고 

• - 1 에서 100 사이 4 의 배수 이거나 6 의 배수인 수의 개수
• - 1 에서 100 사이 4 의 배수이거나 6 의 배수이거나 8 의 배수인 수의 개수
• - 1 에서 100 사이 4 의 배수이거나 6 의 배수이거나 8 의 배수이거나 10 의 배수의 개수

2)수학 적으로 증명하기

(2)오일러 파이 ( 오일러 totient ) 함수

• n 을 소인수 분해 하면

  

1 - n 사이의 n 과 서로 소인 개수는

• 20 의 오일러 파이 함수는

  

(3)페르마 소 정리(Fermat little theorem)

• a = 4 , p = 3 ... 4^(3-1)-1 = 15 는 3 의 배수이다.
• a = 6 , p = 5 ... 6^(5-1) -1 = 1295 는 5 의 배수이다.
• a , p 를 각각 4, 5

  은 5 의 배수이다.

• ...

• 소수 7 있고 ,
  1 , 2 , 3 , 4 , 5 , 6 에서 7 가 서로 소인 수인 수 중 임의의 수 6 을 곱하면

                 1 , 2 , 3 , 4 , 5 , 6
                 1*6 , 2*6 , 3 *6 , 4 *6 , 5*6 , 6*6
  7로 나눈나머지: 6  , 5   , 4    , 3    , 2   , 1
  

  
  1 , 2 , 3 , 4 , 5 , 6 에서 7 가 서로 소인 수인 수 중 임의의 수 8 을 곱하면

                 1 , 2 , 3 , 4 , 5 , 6
                 1*8 , 2*8 , 3 *8 , 4 *8 , 5*8 , 6*8
  7로 나눈나머지: 1  , 2  ,   3    , 4    , 5   , 6
  

  7 로 나눈 나머지 1 에서 6 까지가 나온다.

proof)

만약 p 미만의 수 n, m이 있을 때, (n < m) n*a 와 m*a 를 p로 나눈 나머지가 같다고 하자.

즉 두 수의 차인 (m-n)*a는 p의 배수이다.

서로소인 두 수 a, p의 최소공배수는 ap이므로 m-n은 p의 배수이어야 한다.

이 때 m은 최소 n+p인데, n+p >= p일 수밖에 없으므로 모순.

즉 a부터 (p-1)*a 중 mod p가 서로 같은 쌍은 존재하지 않는다.
즉 1부터 p-1까지의 모든 나머지가 나와야 한다. (0이 나올리는 없겠죠 

(p-1)! 은 p 와 서로 소이므로 (p-1)! 로 양변을 나누면 a^(p-1) = 1 (mod p)

(4)오일러 정리

출처: