質問: 77 の素因数7と11から素因数の知識を利用してzのmod nでの平方根sを計算する。 s2(sの二乗) ≡ 23 mod 7 s2(sの二乗) ≡ 23 mod 11 上の2つを解いて、mod 77での4つの平方根10、32、45、67を得る。 この2つの式から、何をどうやって計算して、4つの平方根10、32、45、67が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。
回答: #3です。 >s ≡ ±3 (mod 7)は、どの様にして導かれたのでしょうか?? あまり深くは考えていません。ご自分で(参考書に)書いてある通り、 --------------------------------------------------------------------------------- 12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7) 32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7) --------------------------------------------------------------------------------- 3^2≡2 (mod 7) から s≡±3 (mod 7)です。(3が見つかれば当然、-3≡4 mod 7もokです) 先に書いた通り、あらゆる整数の2乗はその整数の7における剰余の2乗と合同に なりますから7の剰余の2乗を調べれば s^2≡2≡3^2 (mod 7)からs≡3or4 (mod 7)が言えます。 s≡±1 (mod 11)はもっと簡単ですね。明らかに1^2=1 (mod 11)ですから。 p,qが互いに素なら mp+nq=1 となる整数の組(m,n)が必ず(無数に)存在します。 書き方を変えれば mp-(-n)q=1 11,7の場合は 11*2-7*3=1 ・・・・・・・(1) があります。(当然、9,18や-5,-8でも成立します) とにかくこれを1つ見つければ 11m-7k=2 を作るには(1)の両辺を2倍して 11*4-7*6=2 二つの式を見比べれば m=4,k=6 元の式に代入すれば s=7k+3=42+3=11m+1=44+1=45 です。