ベストアンサー
2 ^ 30 * 3 ^ 20
=（2 ^ 3）^ 10 *（3 ^ 2）^ 10
= 8 ^ 10 * 9 ^ 10
=（8 * 9）^ 10
= 72 ^ 10
72 mod 7 = 2なので、
72 ^ 10 mod 7
=（2 ^ 10） mod 7
= 1024 mod 7
= 2
回答
コンピュータを起動して尋ねれば、私は1091132094649を取得しましたが、これは最小限の鉛筆と紙の作業でどのように行われるのでしょうか、またはCPUサイクルを贅沢に使用せずに、コンピューターではるかに大きな問題がどのように行われるのでしょうか。
おそらくこのための中国の剰余定理が必要です。 20 = 2 ^ 2 * 5なので、20 ^ 10 = 2 ^ 20 * 5 ^ 10です。
3 ^ 30 mod 5 ^ 10とは何ですか？基数5の算術で動作します。 3 ^ 3 = 102、3 ^ 6 = 102 * 102 = 10404、3 ^ 12 = 114001231、3 ^ 3 = 102を掛けますが、5の10乗を超えるすべての桁を破棄します：12133131112は2133131112にトリミングされます。最後にこれを2乗します。出て、5の10乗を超えるものをすべて破棄します：4304012044。ベース10、おなじみの芝に戻るには、これは9047774です。
これで、3 ^ 30 mod 2 ^ 20が必要になります。同じドリルですが、今回はバイナリで作業しています。 686265 mod 2 ^ 20であることがわかります。
今度は、中国の剰余定理の時間です。これは、2つの互いに素な係数（ここでは2 ^ 20と5 ^ 10）があり、合同条件がそれぞれmodである場合、答えが最初の9047774modと他の686265modであるとすると、0との積の間に一意のnがあります。互いに素、1未満。そして、n = a modpおよびbmod qの場合、n = a + pk so（a + pk）= b modqであるという考えからわかります。したがって、pk =（b-a）mod qであるため、k =（pの逆）*（b-a）modqです。そして、p mod qの逆は、拡張ユークリッドアルゴリズムで見つけられます。 （pとqのgcdを抽出します。これは、最終的には1になることを十分に理解していますが、s * p + t * q =について学習した内容を、s *が得られるまで追跡します。 p + t * q = 1の場合、sはp mod qの逆数です。）