모듈러 산술 - 구분

Question

% m (a = x1 * x2 *)과 x1, x2, ..가 상당히 큽니다.

우리가 % m을 찾아야 만한다면 (x1 % m) * (x2 % m) * ...을 사용하여 쉽게 할 수 있었지만 우리의 경우에는 분모 'b' 어떻게 계산합니까?

이 작업은 (a % (m * b))/b와 같이 수행됩니다. 나는 이것이 사실인지 궁금해하고 있으며 어떻게 증명할 것인가?

Answer 1

최소한 여기까지 얻을 수 있습니다 : 그래서 내가 대답으로이주는 정당화, 이미 계산하기가 쉽습니다

b * ((a/b) % m) = (b * (a/b)) % (b * m) 
        = (a - (a % b)) % (b * m) 
        = (a % (b * m) - (a % b) % (b * m)) 
        = (a % (b * m) - (a % b)) 

hence, 

((a/b) % m) = ((a % (b * m)) - (a % b))/b 

합니다. 내가 생각하면 당신이 거기에서 제안한 더 간단한 수식에 갈 수 있지만 시간이나 성향이 그것을 밖으로 작동하지 않았습니다. (숙제 일 경우 너 자신을 위해서 조금 남겨둔다 :))