![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67)
No.1ベストアンサー
- 回答日時:
「yはmod mでの平方剰余である」を「yはmod m で平方数であること」ということにする。
http://oshiete.goo.ne.jp/qa/6046417.html
1の「m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる」と2は俺がかつてした回答とほぼ一緒かな。
「平方根」を整数解といったりとか、言葉がちょっと違うけど、要するに初等整数論の問題なんだよね
mが素数の場合の平方剰余の判定法については
http://aozoragakuen.sakura.ne.jp/suuron/node41.h …
http://aozoragakuen.sakura.ne.jp/suuron/node44.h …
を参考にしてほしい
mが合成数の場合は以下のようになる
mの任意の素因数pに対してx^2≡y (mod p)となるとき
つまり、yがmod pで平方数となるとき
http://aozoragakuen.sakura.ne.jp/suuron/node25.h …の
定理15と定理16により、f(x)=x^2-yとすると、x^2≡y (mod m)が
整数解を持つことがいえるのでyはmod mで平方数となることがいえる。
つまりyが(mod p)での平方根が分かれば、定理15によりx^2≡y (mod p^k)
の平方根が構築できる、つまりyの(mod p^k)での平方根の存在がいえる。
mをm=(p_1)^(k_1)・...・(p_r)^(k_r)と素因数分解したとき
x^2≡y (mod (p_1)^(k_1) ),…,x^2≡y (mod (p_r)^(k_r) )が共に解をもつならば
定理16によりx^2≡y (mod m)の解を構築できる。
要するに、yがmod (p_1)^(k_1)、mod (p_2)^(k_2)、…、mod (p_r)^(k_r)での
平方根が求まれば、定理16によりyのmod mでの平方根が構築できる
つまりyのmod mでの平方根の存在がいえる。
定理16の証明で本質的な役割を果たす「中国剰余定理」については
http://aozoragakuen.sakura.ne.jp/suuron/node24.h …
の定理13および定理13のガウスの別証明
http://aozoragakuen.sakura.ne.jp/suuron/node24.h …
を見るとよい。
そうではないとき
つまり、yがmのある素因数qに対して平方数とはならないとき
yがmod mで平方数となると仮定する。
つまり整数nが存在して、n^2≡y (mod m)となる。
このとき整数k,hが存在してn^2-y=mk,m=qhと書ける。
n^2-y=qhkとなるから、n^2-yはqで割り切れる。
よってn^2≡y (mod q)となるから、yがmod qで平方数となってしまい
最初の仮定に反する。
したがって、このときyはmod mで平方数ではない。
つまりyの平方根は「存在しない」ことになる。
この回答へのお礼
お礼日時:2010/11/13 21:34
お返事が遅くなり申し訳ありませんでした。
理解するのに時間がかかってしまいまして…
でもようやく納得することが出来ました。
ありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 小学生がたった1日で19×19までかんぺきに暗算できる本、のおみやげ算。数学的に言うと何? 3 2023/04/07 09:35
- 高校 有効数字計算 確定した値を含む 2 2023/01/18 06:03
- その他(お金・保険・資産運用) 至急!【Wolt】各メニューの価格設定の簡単な計算方法 3 2023/03/05 11:58
- 数学 2次以上の多項式g(x)であって, 任意の無理数に対して無理数の値を取るものは存在しないことを示せ. 8 2022/06/27 11:28
- 統計学 t統計量とF統計量について 9 2023/01/05 14:23
- 数学 原始関数の存在性の証明について 数学科の3回生です。院試の勉強でつまづいたので助けてほしいです。 R 6 2022/11/13 19:19
- 数学 nC2=2016 の等式を満たす正の整数nの値を求める問題で n(n-1)/2=2016 n^2-n 4 2023/04/07 16:58
- その他(教育・科学・学問) 交流の実際の電圧は正確な平均値0.637が正しいですよね? 21 2022/06/21 13:22
- 数学 数2Bの数列の問題です。 自分は、 まず数列 an=ar^(n-1)と置き こちらの問題の、y= の 1 2022/07/07 16:26
- 数学 情報処理詳しい人!! A4縦のレポート文書に4:3の大きさの横向きの写真画像を貼り付けることにした。 2 2022/12/18 02:30
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
lim[x→+∞](x^n/e^x)=0 の証明
-
大学の記述入試で外積は使えま...
-
AとBはn次正方行列とする。 積A...
-
数A nは自然数とする。n , n+2 ...
-
ファルコンの定理は解かれまし...
-
直角三角形じゃないのに三平方...
-
二次合同式の解き方
-
実数の整列化について
-
至上最難問の数学がとけた
-
【遊びのピタゴラスイッチはな...
-
パップスギュルダンの定理について
-
特異点の3つのタイプについて
-
推論規則と定理、公理は違うもの?
-
高校の数学です。
-
『nを整数、pを素数とするとき...
-
複素関数と実関数のテーラー展...
-
ゼロ知識証明の勉強をしている...
-
曲線の束について質問です 「mf(...
-
完全数はどうして「完全」と名...
-
十分性の確認について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
ファルコンの定理は解かれまし...
-
至上最難問の数学がとけた
-
lim[x→+∞](x^n/e^x)=0 の証明
-
AとBはn次正方行列とする。 積A...
-
これは証明になってる
-
中国剰余式定理(一般形)の証明...
-
【遊びのピタゴラスイッチはな...
-
直角三角形じゃないのに三平方...
-
パップスギュルダンの定理について
-
大学の記述入試で外積は使えま...
-
定理と法則の違い
-
【線形代数】基底、dimVの求め方
-
奇数次の代数方程式
-
完全数はどうして「完全」と名...
-
二次合同式の解き方
-
オイラーの多面体定理の拡張
-
11・13y≡5(mod9)がy≡4(mod9)にな...
-
量子化定理とは?
-
A,Bの異なる2つの箱に異なる1...
-
11の22乗を13で割った余り...
おすすめ情報