xの2乗≡a(mod pのk乗)が整数解を持てばxの2乗≡a(mod pのk+1乗)も整数解を持つ
pは素数、kは0以上の整数、aは整数
この証明についての質問です。
xの2乗≡a(mod pのk乗)の整数解をx1とすると
x1の2乗-a=(pのk乗)s
sは整数
x2=x1+(pのk乗)tとおくと
x2の2乗-a=(x1+(pのk乗)t)の2乗-a
=x1の2乗+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗)-a
=(x1の2乗-a)+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗)
=(pのk乗)s+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗)
=(pのk乗)(s+2(x1)t+(pのk乗)(tの2乗))
ここまではいいのですが
s+2(x1)t≡0(mod p)となるようにtを選ぶことができるというのがわかりません。
ここを通過すればpのk+1乗を約数にもつことになって証明が終わります。
No.4
- 回答日時:
2*x1とpが互いに素であればフェルマーの小定理を使えば簡単です。
2*x1とpが互いに素であればフェルマーの小定理から
(2*x1)^(p-1)≡1 (mod p)
となります。
この両辺に-sをかけると
-s(2*x1)^(p-1)≡-s (mod p)
s-s(2*x1)^(p-1)≡0 (mod p)
s+(2*x1)*(-s)(2*x1)^(p-2)≡0 (mod p)
つまり
t=(-s)(2*x1)^(p-2) であれば s+2*x1*t≡0 (mod p) を満たします。
問題は2*x1がpと互いに素であるか、という点。
x1がpの倍数の場合は元の式に戻って考え直してみましょう。
No.2
- 回答日時:
ん~と, 「p が奇素数」という条件はほとんど意味がありません. 「奇数じゃない素数」って 2 しかないし, そうすると a は 0 か 1 しかないからすぐわかるでしょ?
で, なんですが, 「a=0、kが偶数、sがpと互いに素な平方数の場合にはどうするのでしょう?」とはどういうことでしょうか? 3つの条件が全部そろったときを問題にしているのかそれぞれの場合を問題にしているのかがわかりませんし, どちらにしても「どこにどう困っているのか」がさっぱりわからんのですが.
この回答への補足
a=0、k=2j、s=uの2乗が全部そろったとき
x1の2乗=(pの2j乗)(uの2乗)なので
s+2(x1)t=(uの2乗)+2(x1)t
=(uの2乗)+2(pのj乗)ut
≡(uの2乗)(mod p)
となって≡0(mod p)にならないような気がするのですがどこがおかしいのでしょう?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10の-9乗ってどういう意味ですか?
-
確率の問題で、「5人の中から3...
-
ベクトルの係数比較が一次独立...
-
計算過程を教えて下さい
-
最小二乗法 お願いします。テ...
-
接線の方程式
-
閉形式 (closed form)
-
【数学B】直線のベクトル方程...
-
log-logの補間式
-
分散について
-
数学A 2桁以上の自然数Nについ...
-
ベクトルの問題
-
シグマなど文字を含んだままで...
-
プラスとマイナスが入った比率...
-
3000円が3割なら10割はいくらで...
-
真割引とは?
-
滴定の実験で、結果をExcelで一...
-
【 数A 場合の数 】 問題 10円...
-
【数A 集合の要素の個数】 問題...
-
『戝』という漢字を使った熟語
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報