CheatOS

오일러 정리 이론 :

a와 n이 서로소면,

이 성립한다.

오일러 피 함수란 : 1부터 n까지 n과 서로소인 양의 정수의 개수를 나타내는 것이다.

오일러 함수의 성질 :

• n=1일때 1
• 소수 n에 대하여, (오일러 피 함수 n) = n - 1
• n = pq인 합성수에 대하여, (오일러 피 함수 n) = (오일러 피 함수 pq) = (오일러 피 함수 p) * (오일러 피 함수 q) = (p-1)(q-1)

오일러 피 함수의 계산 :

p가 소수일때, 오일러 p^k의 계산은 

큰 수의 서로소인 양의 정수의 개수를 구해야 할 때는, 소인수분해를 하여 오일러 피 함수를 사용하여 계산할 수 있다.

공식을 정리하면,

페르마의 소정리 이론 :

p가 소수이고 a가 p의 배수가 아닐때,

이 성립한다.

이를 활용하면

이것 또한 가능하다.

증명 :

a가 0과 1일때는 성립한다.

이므로

이 가능하며, a = n + 1일 때 성립한다. 그러므로 수학적 귀납법에 의하여 모든 양의 정수 a에 대하여 정리는 성립한다.

그러므로 위의 식이 성립한다.

유클리드 알고리즘의 이론 :

A = BQ + R(Q, R: 정수) 이면,

gcd(A, B) = gcd(B, R) 이다.

유클리드 알고리즘의 증명 :

gcd(A, B) = G, gcd(B, R) = G' 이라고 했을 때, G = G'이면 증명이 된다.

A = aG, B = bG (단, a와 b는 서로소)이면, A = BQ + R 이므로,

aG = bGQ + R이고, R = (a-bQ)G 이다.

gcd(B, R)이 G가 되려면 (a - bQ) 와 b가 서로소이면 된다.

A = aG , B = bG, R = (a-bQ)G 이기 때문에, A와 B는 G가 최대공약수이고,

B와 R의 최대공약수 또한 G가 되어야 하기 때문이다.

귀류법을 사용하여 (a - bQ) 와 b가 공약수를 갖는다고 가정하면

b = nk, a-bQ = mk 라 했을 때 a = bQ + mk = (nQ + m)k

a - bQ 와 b 모두 k 라는 공약수를 가지기 때문에 모순이다.

따라서 b와 a - bQ 가 서로소임을 확인하였다.

확장 유클리드 알고리즘의 이론 :

as + bt = c 가 정수해를 갖는 c의 최솟값은 gcd(a, b)이다.

이를 통해 a와 b의 최대 공약수와 as + bt = gcd(a, b)를 만족하는 x, y를 구하는 알고리즘이다.

확장 유클리드 알고리즘의 동작원리 :

초기값 : 

진행 과정 : 

참고 : joonas.tistory.com/25