模運算滿足的三個基本性質如下：(a + b) mod n = [ (a mod n + b mod n) ] mod n(a - b) mod n = [ (a mod n - b mod n) ] mod n(a * b) mod n = [ (a mod n) * (b mod n) ] mod n(a mod n) 就表示的是 (a 模 n)，即程式中(a%n)的意思。比如 (13*15) mod 7 = [ (13 mod 7) * (15 mod 7) ] mod 7 = (6 * 1) mod 7 = 6上面這三條基本的性質的證明，可以參考 @鄧毅 先生的回答中
a = c*k_a + z_a, b = c*k_b+z_b (z_a = a % c, z_b = b % c)的技巧，可以比較容易證明。記本問題中兩個很大的數分別為a、b，待求模的數字記為c。乍看之下即可用前面提到的第三條性質，分別計算a mod c、b mod c，然後計算其乘積，再對c求模即可。 但是，在@鍾宇騰先生回答中 @項昊凡先生的評論所提到的當a mod c、b mod c的結果都很大時，兩數相乘可能會產生資料溢位的情況，值得特別地考慮。一個直接的解決辦法是，將a mod c、b mod c的結果分別記為a1、b1，再利用同樣的思路對a1、b1做類似處理：(a * b) mod c = [ (a mod c) * (b mod c) ] mod c = [ (a1 * b1) mod c ] mod c = { [ (a1 mod c) * (b1 mod c) ] mod c } mod c若a1 mod c、b1 mod c仍然很大，其乘積仍然會溢位，則令a2=a1 mod c，b2=b1 mod c，再類似地處理即可。需要特別注意的是，在計算機處理中，不同語言對模運算的處理結果會不一樣。例如 -11 mod 7，按照一般數學上的定義，結果應該為 -4 mod 7 = 3，即結果總是為非負數；但在標準C中，總是有 x = (x / y) * y + x % y，則 -11 = -7 + (-11 % 7)，從而結果為 -4，但是在Python shell中則結果是3。在模數和被模數符號相異時，需要特別注意這一點。此外，基於上面的三條基本性質，還有很多解法可供參考。考慮到 2*a*b = a*a + b*b - (a-b)*(a-b) = (a+b)*(a+b) - a*a - b*b注意到當a、b同號時，a-b不會溢位；當a、b異號時，a+b不會溢位。因此總可以有一種不會溢位的方式完成上面等式右邊的運算。可以發現，a*a，b*b，(a+b)*(a+b)，(a-b)*(a-b)，都是完全平方的形式。而一旦得到(2*a*b) mod c的結果也可以方便得出(a*b) mod c的結果。因此，結合上面的三條基本性質，原問題被轉為：一個很大的數的平方，模上另外一個數，如何在保證資料不會溢位的前提下得到結果？注意到，[ (c-a)*(c-a) ] mod c = [ (a -c)*(a-c) ] mod c = [ a*a + c*c - 2*a*c] mod c = (a*a) mod c類似地，有[ (c+a)*(c+a) ] mod c = [ a*a + c*c + 2*a*c] mod c = (a*a) mod c因此，比如當a>c，且同號的時候，利用(a*a) mod c 與[ (a-c)*(a-c) ] mod c相等，用a不斷地去減c，直到該結果的平方運算不會溢位為止。具體地，分為以下4種情況，(相等的平凡情況不影響，為表述方便忽略之)：1）a > c，同號，已分析過；2）a > c，異號，此時a > 0，c < 0 採用 (a+c)*(a+c)運算，使a不斷地加上c，直至不會溢位；3）a < c，同號，類似採用(c-a)*(c-a)運算，直至不會溢位；4）a < c，異號，此時a < 0，c > 0，同情況 2）可以看到，類似地運用模運算的規律不難發現新的計算方法，上面談到的辦法也有許多可以最佳化的地方，比如在某些特殊情況下的簡便處理。此外模運算還有一個性質也是可以運用到該問題的求解中的：(a)(b) mod c = [ ((a) mod c)(b) ] mod c 其中(a)(b)表示數字地任意分割，12345=(12)345=(1)(2345)比如，125 mod 7 = (12mod 7)5 mod c = 55 mod 7這個結論也很容易證明，更多地相關性質可以參考 有限域 (finite field) 相關的內容。希望有所幫助，歡迎討論。
模運算滿足的三個基本性質如下：(a + b) mod n = [ (a mod n + b mod n) ] mod n(a - b) mod n = [ (a mod n - b mod n) ] mod n(a * b) mod n = [ (a mod n) * (b mod n) ] mod n(a mod n) 就表示的是 (a 模 n)，即程式中(a%n)的意思。比如 (13*15) mod 7 = [ (13 mod 7) * (15 mod 7) ] mod 7 = (6 * 1) mod 7 = 6上面這三條基本的性質的證明，可以參考 @鄧毅 先生的回答中
a = c*k_a + z_a, b = c*k_b+z_b (z_a = a % c, z_b = b % c)的技巧，可以比較容易證明。記本問題中兩個很大的數分別為a、b，待求模的數字記為c。乍看之下即可用前面提到的第三條性質，分別計算a mod c、b mod c，然後計算其乘積，再對c求模即可。 但是，在@鍾宇騰先生回答中 @項昊凡先生的評論所提到的當a mod c、b mod c的結果都很大時，兩數相乘可能會產生資料溢位的情況，值得特別地考慮。一個直接的解決辦法是，將a mod c、b mod c的結果分別記為a1、b1，再利用同樣的思路對a1、b1做類似處理：(a * b) mod c = [ (a mod c) * (b mod c) ] mod c = [ (a1 * b1) mod c ] mod c = { [ (a1 mod c) * (b1 mod c) ] mod c } mod c若a1 mod c、b1 mod c仍然很大，其乘積仍然會溢位，則令a2=a1 mod c，b2=b1 mod c，再類似地處理即可。需要特別注意的是，在計算機處理中，不同語言對模運算的處理結果會不一樣。例如 -11 mod 7，按照一般數學上的定義，結果應該為 -4 mod 7 = 3，即結果總是為非負數；但在標準C中，總是有 x = (x / y) * y + x % y，則 -11 = -7 + (-11 % 7)，從而結果為 -4，但是在Python shell中則結果是3。在模數和被模數符號相異時，需要特別注意這一點。此外，基於上面的三條基本性質，還有很多解法可供參考。考慮到 2*a*b = a*a + b*b - (a-b)*(a-b) = (a+b)*(a+b) - a*a - b*b注意到當a、b同號時，a-b不會溢位；當a、b異號時，a+b不會溢位。因此總可以有一種不會溢位的方式完成上面等式右邊的運算。可以發現，a*a，b*b，(a+b)*(a+b)，(a-b)*(a-b)，都是完全平方的形式。而一旦得到(2*a*b) mod c的結果也可以方便得出(a*b) mod c的結果。因此，結合上面的三條基本性質，原問題被轉為：一個很大的數的平方，模上另外一個數，如何在保證資料不會溢位的前提下得到結果？注意到，[ (c-a)*(c-a) ] mod c = [ (a -c)*(a-c) ] mod c = [ a*a + c*c - 2*a*c] mod c = (a*a) mod c類似地，有[ (c+a)*(c+a) ] mod c = [ a*a + c*c + 2*a*c] mod c = (a*a) mod c因此，比如當a>c，且同號的時候，利用(a*a) mod c 與[ (a-c)*(a-c) ] mod c相等，用a不斷地去減c，直到該結果的平方運算不會溢位為止。具體地，分為以下4種情況，(相等的平凡情況不影響，為表述方便忽略之)：1）a > c，同號，已分析過；2）a > c，異號，此時a > 0，c < 0 採用 (a+c)*(a+c)運算，使a不斷地加上c，直至不會溢位；3）a < c，同號，類似採用(c-a)*(c-a)運算，直至不會溢位；4）a < c，異號，此時a < 0，c > 0，同情況 2）可以看到，類似地運用模運算的規律不難發現新的計算方法，上面談到的辦法也有許多可以最佳化的地方，比如在某些特殊情況下的簡便處理。此外模運算還有一個性質也是可以運用到該問題的求解中的：(a)(b) mod c = [ ((a) mod c)(b) ] mod c 其中(a)(b)表示數字地任意分割，12345=(12)345=(1)(2345)比如，125 mod 7 = (12mod 7)5 mod c = 55 mod 7這個結論也很容易證明，更多地相關性質可以參考 有限域 (finite field) 相關的內容。希望有所幫助，歡迎討論。