[10] 이산수학(정수의 표현과 알고리즘, 소수와 최대공약수)

정수의 표현 :

• 우리는 일상생활에서 10진법을 이용하여 정수를 표현한다.
• 하지만 컴퓨터는 연산할 때 2진법을 사용하고, 문자나 숫자 등을 표현할 때 8진법 또는 16진법을 사용한다.

• 정수 n을 위의 그림처럼 표현한 것을 n의 밑 b 전개(base b expansion of n)라 한다.

2진수 곱셈 : 

• 10진수가 10의 자리마다 들여쓰기를 하는 것처럼, 2진수는 2의 자리마다 들여쓰기한다.

소수 :

• 1보다 큰 모든 정수는 최소한 두 정수(1과 자기 자신)로 나누어 떨어진다.
• 정확히 두 개의 서로 다른 양의 정수가 약수인 양의 정수를 소수(prime)라고 한다.
• 대수학의 기본 정리 : 1보다 큰 모든 정수는 소수이거나, 둘 이상의 소수의 곱으로 표현할 수 있다.

소수 판별법 :

• 만약 n이 합성수라면, n의 소인수 중 하나는 √n보다 작거나 같다.
• 위의 정리를 이용해 제곱근 이하의 모든 소수로 나누어 보는 방법을 직접 나누어 보기(trial division)라 한다.
• 에라토스테네스의 체를 사용할 수도 있다.

최대공약수 :

• a,b가 0이 아닌 정수라 하자. d | a와 d | b인 정수 중 가장 큰 d를 a와 b의 최대공약수라고 한다. 이를 gcd(a,b)로 표현한다.
• 두 정수 a,b의 최대공약수가 1이면, 정수 a와 b는 서로소(relatively prime)라 한다.

최소공배수 :

• 양의 정수 a와 b의 최소공배수는 a와 b 모두로 나눌 수 있는 가장 작은 양의 정수이다.
• a와 b의 최소공배수는 lcm(a,b)로 표현한다.

유클리드 알고리즘 :

• a,b,q,r이 정수일 때, a=bq+r이라 하자. 그러면 gcd(a,b) = gcd(b,r)

gcd와 선형 결합 :

• 베주의 정리 : a와 b가 양의 저수이면, gcd(a,b) = sa + tb인 s와 t가 존재한다.
• 𝑎와 𝑏가 양의 정수이면, gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏인 정수 𝑠와 𝑡는 𝑎와 𝑏의 베주 계수(Bezout coefficients)라 부른다. 또한, 식 gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏를 베주의 동일성(Bezout's identity)이라 부른다.

 

소인수 분해의 유일성 :

• 양의 정수 a,b,c가 gcd(a,b) = 1이고 a | bc이면, a | c이다.
• 𝑝가 소수이고, 𝑎𝑖가 정수일 때 𝑝 | 𝑎1𝑎2 … 𝑎𝑛이면 𝑝 | 𝑎𝑖인 어떤 𝑖가 존재한다.
• (중요!!)  𝑚이 양의 정수이고 𝑎, 𝑏, 𝑐를 정수라 하자. 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚)이고 gcd 𝑐, 𝑚 = 1이면 𝑎 ≡ 𝑏 mod 𝑚 .