나머지 모듈러스가있는 부분

Question

나머지 모듈러스로 어떻게 나눗셈을 할 수 있습니까? 예를 들어

^2,012 9 모듈러 산술을 사용하여 11

로 나누었을 때의 나머지를 찾아 9 == 1 MOD (4)이므로 9^2,012 ==^2,012 1 (모드 4). 따라서, 9^2012 == 1 (mod 4). 또한, 11 == 3 (mod 4). 질문에 대답하기 위해 나는 1 (mod 4)/3 (mod 4)를하려고합니다. 이 일을 할 수있는 방법이 있습니까?

Answer 1

이이 문제를 해결하는 데 도움이 될 두 가지 중요한 이론 : -

1. 모듈러 지수화를
2. 페르마의 작은 정리

모듈 지수화 : -이 간단한 재귀 공식은 이해 만들려면 -

(a^n)%p = ((a^(n-1))%p*a)%p 

상기 화학식은^n이 클 경우 발생하는 오버플로를 방지하는 데 도움이됩니다. P 따라서 (a^n)%p = (a^(n%(p-1)))%p

에 공동 소수 그 어떤 A의 p는 귀하의 경우 소수 인 경우 11 다음 소수 (a^(p-1))%p = 1 - : 또한 빠른 exponention은 O를 (logn)

페르마의 작은 정리를 사용하여 수행 할 수 있습니다 귀하의 예 : -

9^2012 % 11 = ? 

11 is prime and 9 is co-prime to 11 then using fermat's theorem 

9^2012 % 11 = (9^(2012%10)) % 11 
2012%10 = 2 

9^2012 % 11 = 9^2 % 11 = 4