[11] 이산수학(합동 풀기)

소인수 분해의 유일성 :

• (별 3개)m이 양의 정수이고, a,b,c를 정수라 하자. 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚)이고 gcd 𝑐, 𝑚 = 1이면 𝑎 ≡ 𝑏 mod 𝑚 .

베주의 정리 : 시험

중국인의 나머지 정리 : 

• 만약 선형합동 시스템이 주어져 있고, 나누는 수가 쌍으로 서로소라면, 이 수들의 곱으로 나눈 나머지 시스템은 유일한 해를 가진다.
• 시험문제에 나온다.(예제 4번)

 페르마의 작은 정리 :

• 𝑝가 소수이고 𝑎가 𝑝로 나눌 수 없는 정수이면 𝑎^(𝑝−1) ≡ 1 mod 𝑝 이다. 또, 모든 정수 𝑎에 대하여 𝑎
  ^𝑝 ≡ 𝑎 mod 𝑝 이다.
• 시험

의사소수(pseudoprime) :

• b가 양의 정수라 하자. 만약 n이 양의 합성수이고 b^(n-1) 1(mod n)이면, n을 b를 밑으로 하는 의사소수라고 한다.

이산로그 : 

• 수가 작을 때 사용한다. 계산하기 어려움