- ベストアンサー
数学、ｍｏｄ ｐのｋ乗の整数解
- ｘの２乗≡ａ（ｍｏｄ ｐのｋ乗）が整数解を持てばｘの２乗≡ａ（ｍｏｄ ｐのｋ＋１乗）も整数解を持つ
- ｘの２乗≡ａ（ｍｏｄ ｐのｋ乗）の整数解をｘ１とすると ｘ１の２乗－ａ＝（ｐのｋ乗）ｓ
- ｓ＋２（ｘ１）ｔ≡０（ｍｏｄ ｐ）となるようにｔを選ぶことができるというのがわかりません。ここを通過すればｐのｋ＋１乗を約数にもつことになって証明が終わります。
- 数学・算数
- 回答数4
- ありがとう数2
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (3)
- rnakamra
- ベストアンサー率59% (761/1282)
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の倍数の場合は元の式に戻って考え直してみましょう。
お礼
ありがとうございました。
- Tacosan
- ベストアンサー率23% (3656/15482)
u=0 なら問題なし. というか, a=0 のときは考えるまでもないよね.
お礼
確かにそうですね。 よくわかりました。ありがとうございました。
- Tacosan
- ベストアンサー率23% (3656/15482)
ん～と, 「p が奇素数」という条件はほとんど意味がありません. 「奇数じゃない素数」って 2 しかないし, そうすると a は 0 か 1 しかないからすぐわかるでしょ? で, なんですが, 「ａ＝０、ｋが偶数、ｓがｐと互いに素な平方数の場合にはどうするのでしょう？」とはどういうことでしょうか? 3つの条件が全部そろったときを問題にしているのかそれぞれの場合を問題にしているのかがわかりませんし, どちらにしても「どこにどう困っているのか」がさっぱりわからんのですが.
補足
ａ＝０、ｋ＝２ｊ、ｓ＝ｕの２乗が全部そろったとき ｘ１の２乗＝（ｐの２ｊ乗）（ｕの２乗）なので ｓ＋２（ｘ１）ｔ＝（ｕの２乗）＋２（ｘ１）ｔ ＝（ｕの２乗）＋２（ｐのｊ乗）ｕｔ ≡（ｕの２乗）（ｍｏｄ ｐ） となって≡０（ｍｏｄ ｐ）にならないような気がするのですがどこがおかしいのでしょう？
関連するQ&A
- modを使用した平方根の求め方
解き方が解からない問題があります。 どれだけ考えても解き方がわからないので、どなたかわかる方教えてください。 【解き方が解からない問題】 大きな素数の積n=pqが与えられた時、nを素因数分解するのは非常に難しい。 整数ｍと整数ｙ(<ｍ)が与えられた時y=ｘ2(xの二乗) mod mなる整数解xが存在すれば、yは mod mで平方剰余であるという。 xを mod mでのyの平方根という。 mが素数7の時、 12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7) 32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7) 52(5の二乗)≡4 (mod 7) 、 62(6の二乗) ≡ 1 (mod 7) となるので、1、2、4が平方剰余で、各平方剰余には２個の平方根がある。 mが二つの素数の積の場合、４個の平方根がある。 ここまでが参考書に載ってる説明です。 ここから私がわからない問題です。 102(10の二乗) mod 77＝23 n = 77 の素因数7と11から素因数の知識を利用してZのmod nでの平方根Sを計算する。 S2(Sの二乗) ≡ 23 mod 7 S2(Sの二乗) ≡ 23 mod 11 上の２つを解いて、mod 77での４つの平方根10、32、45、67を得る。 この２つの式から、何をどうやって計算して、４つの平方根10、32、45、67が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 離散数学の証明問題
離散数学の証明問題 合同でないことを≡×と表します。 Pを素数とし、a≡×0(mod p)とする。また、aの位数をdとする。 このとき、次のことを示せ。 (1)整数nに対して、a^n≡1(mod p)であるならば、かつそのときに限り、d|n (2)dはp-1の約数である。 (3)整数i,jに対してa^i≡a^j (mod p)であるならば、かつそのときに限り、i≡j(mod p) (1)はFermatの小定理を使うと思うのですが、いまいち解法が浮かびません。 (2)はFermatの小定理から自明に思えますが、厳密に証明しないといけないみたいです。 (3)は証明方法がまったく分かりません。 分かる方、証明お願いします。
- ベストアンサー
- 数学・算数
- 大学数学で、合同方程式の問題なんですが、
大学数学で、合同方程式の問題なんですが、 ｘ＾９７≡２２ ｍｏｄ ２２５ の解の求め方がわかりません。 どなたかおしえていただけないでしょうか それとｘ＾ｔ≡ａ ｍｏｄ ｎ の解を求める際に ｇｃｄ（ａ，ｍ）＝１ ｇｃｄ（ｋ、φ（ｍ））＝１を使うらしいのですが意味がわかりません。 このときのａ，ｍ，ｋは一般自然数です ｘ＾９７は指数でｘの９７乗のことです よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 任意のkに対し、f(m）がk個の素因数を持つ様なm
f(x)を整数係数のmonic polynomialとしたとき 任意の整数kに対して、f(m)がk個の異なる素因数をもつような整数mは存在するか という問題なのですが、 素数を小さい順にp_1 ,p_2, p_3, ...とし、 f(m)の素因数がp_1, p_2, ... , p_kとなるようなmが存在することを示す。 f(x)は問題文の条件より f(x)=(x-a_1)(x-a_2)....(x-a_n)とおける (a_iは整数） p_iは素数なので互いに素 中国の剰余定理より y≡a_1 (mod p_1) y≡a_2 (mod p_2) y≡a_3 (mod p_3) ... y≡a_k (mod p_k) を満たすｙが存在する。 y-a_1≡0 (mod p_1) y-a_2≡0 (mod p_2) y-a_3≡0(mod p_3) ... y-a_k≡0(mod p_k) となるためf(y)はp_1, p_2, ..., p_kのすべてで割り切れる。 間違いがあったら指摘ください。
- ベストアンサー
- 数学・算数
- Ｐ(０), Ｐ(１),Ｐ(２),・・・, Ｐ(ｎ)が整数ならば、全ての整数ｋに対してＰ(ｋ)は整数
『ｎを自然数, Ｐ(ｘ)をｎ次の多項式とする。Ｐ(０), Ｐ(１),Ｐ(２),・・・, Ｐ(ｎ)が整数ならば、全ての整数ｋに対してＰ(ｋ)は整数であることを証明せよ。』 数学的帰納法で解けるらしいのですが、分かりません。どなたか教えてください。
- ベストアンサー
- 数学・算数
- 最大公約数 gcd(a,b,c) と一次合同式の解の存在
初等整数の証明で困ってます。 (1)gcd(a,b,c)はgcd(a,b)の約数であることを証明せよ。 (2)gcd(gcd(a,b),c)はgcd(a,b,c)の倍数であることを証明せよ。 また合同式の定理の証明について gcd(a,b)=1ならばax≡c(mod b)は解をもつ。 さらにこの合同方程式の一つの解をpとすると、すべての整数kについてp+kb も解である。逆にこの合同方程式の任意の解はp+kb と表わされる。 ax≡c(mod b) は b | (ax-b) を導けばよいのでしょうか？ お願いします。
- 締切済み
- 数学・算数
- 素数の分類と無限性に関して。以前質問させていただいたことの延長になりま
素数の分類と無限性に関して。以前質問させていただいたことの延長になります。 ※＾は乗数の意味です。 8n+1型の素数が無限に存在することの証明 原始根の存在（素数 p を法とする整数環 Z/pZ の乗法群が位数 p - 1 の巡回群であること）を使う。 x を整数とする時x＾4 + 1 の奇素数因子を p とする。 x＾4 ≡ - 1 (mod. p) より、両辺を2乗することでx^8≡1となる。 x の p を法とする整数環 Z/pZ の乗法群での位数は 8 で有るから、 p ≡ 1 (mod. 8) となる。ここで、 p ≡ 1 (mod. 8) となる素数が有限個であったとする時、その総乗積を P として、 (2P)＾4 + 1 の奇素数因子を考えると矛盾が出る。 私は2PをX"とおいて上と同様に考えました。 同じ方法を用いることで証明することはできたのですが、 この証明の中で用いている「位数は 8 で有るから、 p ≡ 1 (mod. 8) となるの部分に関して ラグランジュの定理 位数nの有限郡Gの任意の部分郡Hの位数はGの位数の約数である を用いた場合、GとHに当たる部分はどこになるのでしょうか。今の段階では、nがｐ－１にあたり、Hの位数が８と考えています。ｐが素数で、８はｐ－１の約数になるとの考えは当っているでしょうか・・？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- 有理数解方程式
4x^3-(a-2)x-(a+4)=0 (a 整数）が整数でない有理数の解をもつとき、 この方程式の解をすべて求めよ。 次のようにかんがえましたが、挫折しました。アドバイスをお願いします。 解をｑ／ｐ 既約分数とおく。（ｐは１でない。）これを与式に代入して、4q^3-(a-2)p^2-(a+4)p^3=0 。 4q^3のｐは約数であるが、ｐとｑは互いに素だから、ｐは４の約数。 よって、ｐ＝２，４である。 ア、ｐ＝２のとき、 代入して、q^2-(a-2)q-2(a+4)=0,qはａ＋４の約数であるから、 qk=a+4とおくと、q^2-kq+6-2k=0 このあとの解答が続きません。よろしくお願いします。
- ベストアンサー
- 数学・算数
- √5≡y (mod p )が解を持つための条件は？
素数p に対し、√5≡y (mod p ) を 5≡y^2 (mod p )と定義したとき、√5≡y (mod p )が解を持つための必要十分な条件は p≡±1(mod 5)らしいのですが本当でしょうか？（必要あるいは十分だけ？）正しいときはどのように（あるいはどのような方針で）証明したらいいのでしょうか。また、参考文献があれば教えてください。
- ベストアンサー
- 数学・算数
- 体験版を使用中で受信できない一斉配信メールの問題が発生
- ホワイトリストに手動入力しても受信できず、解決方法を求める
- ESETセキュリティ ソフトウェア シリーズに関連する問題
補足
条件がひとつ抜けていました。ｐは奇数の素数です。 ａ＝０、ｋが偶数、ｓがｐと互いに素な平方数の場合にはどうするのでしょう？