- 締切済み
証明の解説
証明 ｎ＝ｐｑ （pとqは異なる素数） rはgcd(r,Φ(n))=1 を満たす。 ｆ（a）=a^rで定義されたZn自身からの写像は全単射である。 またこの写像の逆関数はｇ（ｂ）＝ｂ＾ｒ’であたえられる。 ｒ’はｒｒ’≡１(modΦ(n)を満たす。 この定理の証明をどなたか教えてください！ 本には 本には rr' = 1+kΦ(n). g(f(a)) = f(g(a)) = a^rr' = a×a^kΦ（n）. Φ（ｎ） = Φ(p)Φ(q) = (p-1)(q-1) ⇒g(f(a)) = a×a^(p-1)k(q-1) 「 If a ≡ 0 (mod p), then g(f(a)) ≡ 0 (mod p). Otherwise, we may apply フェルマー定理 to conclude that a^(p-1)k(q-1) ≡ 1 (mod p) In either case, we have g(f(a)) ≡ a (mod p).同様に g(f(a)) ≡ a (mod q)」 よって中国剰余の定理よりg(f(a)) ≡ a (mod pq) と書いてありました。 「」の部分がよくわかんないです。 その部分が何故そうなるのか、何を言っているのか詳しく教えてください。 違うやり方の証明でもいいです。 RSA algorithmの項目に出てきたんでしつもんしました。 ぜひ回答よろしくお願いします
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- d3kk485
- ベストアンサー率41% (5/12)
- Tacosan
- ベストアンサー率23% (3656/15482)
- Tacosan
- ベストアンサー率23% (3656/15482)
え～と, どこがわからないんでしょうか? 前半 a ≡ 0 のとき? それともそうでないとき? 「そうでないとき」だとしたら, 「フェルマーの定理」とやらが何を主張しているのかわかりますか? それもわかるんだとしたら, 一体全体どこがわからない?
補足
もしa ≡ 0 (mod p)ならg(f(a))≡0 (mod p) そうでなければ、フェルマーの定理でa^(p-1)k(q-1) ≡1( mod p)が結論づけれるって訳したんですが、 まず、もしa ≡ 0 (mod p)ならg(f(a))≡0 (mod p) となるのがわかんないです。 その次にフェルマーの定理で結論づけられるって所。 最後の g(f(a))≡aっていうのがどこから来たのか。 わかりにくい質問ですがぜひお願いします(>_<)
関連するQ&A
- フェルマの小定理の証明方法について
フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、（式ａ）から（式ｂ）に移るのは妥当なのか、よくわかりません。 [蛇足] フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。 ●オイラーの定理 (a,m)=1のとき a^(φ(m))≡1 (mod m) 【フェルマの小定理】 a^(p-1)≡1 (mod p) ただし、aは正の整数（←条件を、少し制約しました。）、pは素数、ａとｐは互いに素（(a,p)=1） とする。 ■証明 数学的帰納法を用いる。 (1)a=1 のときは明らか。 (2)a=k のとき成り立つと仮定して、a=k+1のとき成り立つことを証明する。 言い換えると、mod p において、 k^p≡k ⇒ (k+1)^p≡k+1 を証明すればよい。 以下、合同式は mod p の場合のことを指す。 仮定より、 (k)^p≡k (k)^p-1≡k-1 F(k)=k^(p-1)+k^(p-1)…+1 とおくと、 (k-1)・F(k)≡k-1 よって、 F(k)≡1 ところで、F(k)はp個の元から構成されており、 p-1 Σ(k^m)≡1 （式ａ） m=0 と書き直せる。ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、 p-1 Σ((k)^m*(1)^m)≡1 （式ｂ） m=0 と書ける。これより、 p-1 k・Σ((k)^m*(1)^m)≡k m=0 p-1 (k*1-1)・Σ((k)^m*(1)^m)≡k m=0 よって、 (k*1)^p-1≡k 書き直して、 (k+1)^p≡k+1 <証明終>
- ベストアンサー
- 数学・算数
- 行列の写像のwell-definedの証明ができま
宜しくお願い致します。 N_n:={X;Xはn×n正規行列}とし,2つの写像f:R→R,F:N_n→R^{n×n}を f(x):=Σ_{k=0}^∞a_kx^kとし,Fは X=P^t diag(λ_1,λ_2,…,λ_n)P (但し,Pは直交行列,diag(λ_1,λ_2,…,λ_n)は対角行列)と書けるので, F(X):=P^t diag(f(λ_1),f(λ_2),…,f(λ_n))Pと定義するとFはwell-definedである事を示す問題です。 [証] 背理法を使って証明する。 X:=P^t diag(λ_1,λ_2,…,λ_n)P=Q^t diag(μ_1,μ_2,…,μ_n)Q…(*)の時 (ここで,λ_1,λ_2,…,λ_n,μ_1,μ_2,…,μ_nはXの固有値となりますね), P^t diag(f(λ_1),f(λ_2),…,f(λ_n))P≠Q^t diag(f(μ_1),f(μ_2),…,f(μ_n))Qとなったと仮定すると, 左辺=(Σ_{k=1}^n p_{ki} f(λ_k) p_{jk}), 右辺=(Σ_{k=1}^n q_{ki} f(μ_k) q_{jk}), なので ∃l,m∈{1,2,…,n}; Σ_{k=1}^n p_{kl} f(λ_k) p_{mk}≠Σ_{k=1}^n q_{kl} f(μ_k) q_{mk}で, (*)より, ∃r,s∈{1,2,…,n}; λ_r≠f(λ_r)または,μ_s≠f(μ_s)が言える。 従って, λ_r≠Σ_{k=0}^∞a_kλ_r^kまたは,μ_s≠Σ_{k=0}^∞a_kμ_s^k まで言えたのですが,ここからどうやって矛盾が引き出せますでしょうか?
- 締切済み
- 数学・算数
- p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq
p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq)になりますか? nがpともqとも互いに素であるときは、 Fermatの小定理を使えばn^{(p-1)(q-1)}≡1 (mod pq) が言えるので、標記の命題は言えると思うのですが pまたはqのいずれか一方がnと互いに素でないとき n^{(p-1)(q-1)}≡1 (mod pq)は言えないものの n^{(p-1)(q-1)+1}≡n (mod pq)は言えてしまっているように思えます (私がやったケースはp=3,q=11の場合です)。 これは正しいのでしょうか? 正しいとしたら何故ですか?
- ベストアンサー
- 数学・算数
- 離散数学の証明問題
離散数学の証明問題 合同でないことを≡×と表します。 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)は証明方法がまったく分かりません。 分かる方、証明お願いします。
- ベストアンサー
- 数学・算数
- 写像の証明問題を教科書の定理、定義を組み合わせながらやっていたのですが
写像の証明問題を教科書の定理、定義を組み合わせながらやっていたのですがうまく出来ません。 どなたか次の問題の証明過程を教えてください。 ｆ:A→B, g:B→Aをともに全単射とすれば、g。f （gとfの合成写像）: A→Cも全単射である。 このとき、（g。f）＾-1 (gとfの合成写像のインバース)＝f^-1。g^1（fのインバースとgのインバースの合成写像）であることを示せです。 お願いします。
- ベストアンサー
- 数学・算数
- 写像の単射全射のところの関係式に関する証明について
写像の単射全射のところの証明がわからないので、ご教授ください。 集合AからBへの写像をfとし、a∈A,P⊂A,b∈B,Q⊂Bとする。 １．fが単射のとき、a∈P ⇒ f(a)∈f(P)の逆が成り立つことの証明 2.fが単射のとき、Ｐ1⊂P2 ⇒ f(P1)⊂f(P2)の逆が成り立つことの証明 3.fが単射のとき、f(A-P) ⊃ f(A) - f(P) の逆が成り立つことの証明 4.fが単射のとき、f^(-1)(f(P)) = Pの証明 5.fが全射のとき、∃a'∈f^(-1)(Q), b=f(a') ⇒ b∈Qの逆が成り立つことの証明 6.fが全射のとき、Q1⊂Q2 ⇒ f^(-1)(Q1)⊂f^(-1)(Q2)の逆が成り立つことの証明 7.fが全射のとき、f(f^(-1)(Q)) = Qの証明 以上の7問です。 何個かだけでも構いませんので、回答して頂ければ嬉しいです。 また、はじめての質問ですので、ご迷惑をおかけするかもしれませんが、よろしくお願いいたします。
- 締切済み
- 数学・算数
- 中国剰余定理 3数
余りが条件式を満たすがわからないので質問します。 p,q,rどの2つをとっても、互いに素な自然数とする。a,b,cを任意の整数とする。このとき、 x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たす整数ｘが、0からpqr-1までの間に1つ存在する。この定理の証明は、 (qr)s≡1 mod(p),(rp)t≡1 mod(q),(pq)u≡1 mod(r),を満たすs,t,uを求めることから始まります。sであれば、(qr)s+py=1・・・(1)という１次不定方程式を解くことで、得られます。q,rがpと互いに素であるから、qr,pが互いに素なので(1)を満たすs,yは存在します。同様にt,uが得られます。x=a(qr)s+b(rp)t+c(pq)u・・・(2)とおけば、xは条件式を満たします。(2)をｐで割った余りは、a*1+0+0=aとなります。qで割れば余りb,rで割れば余りc,となります。ここからがわからない箇所です。このxをpqrで割った余りも条件式をみたします。 まず、自分の計算では、x=a(qr)s+b(rp)t+c(pq)u=pqr{as(1/p)+bt(1/q)+cu(1/r)}となり余りが出ません。そして条件式x≡a mod(p),x≡b mod(q),x≡c mod(r) を満たしているとも思えません。どなたか自分の考えの間違いを教えてください。お願いします。
- ベストアンサー
- 数学・算数
- K上のテンソル積P_2(×)RとP'_2:={a_0+a_1x+a_2x^2;a_i∈R}とは同型である事を示せ
K:={a+b√5;a,b∈Q},P_n:={Σ[i=0..n]a_ix^i;a_i∈K}とする。 K上のテンソル積P_2(×)RとP'_2:={a_0+a_1x+a_2x^2;a_i∈R}とは同型である事を示せと言う問題です。 P_2(×)RからP'_2への全単射な同型写像fとしてどのようなものが取れますでしょうか? P_2(×)R∋∀p(×)r→f(p(×)r):=????
- 締切済み
- 数学・算数
お礼
どうもありがとうございます！ 参考にさせてもらいます！