- 締切済み
証明の説明
GCD(m,n)=1 cは任意の整数 ⇒ ｆ(a)=ma+cで定義されたZn自身からの写像は全単射である。 この証明の単射性の証明ですが ｆ(a)=f(b)とする。 このとき ma+c≡mb+c (mod n)これはnが(ma+c)-(mb+c)を割り切る。 したがってnはm(a-b)を割り切る。 GCD(m,n)=1よりnは（a-b）を割り切る。 しかしｎが(a-b)を割り切るのは(a-b)=0の場合つまりa=b なぜなら a,b∈Znだから。 最後の 「しかしｎが(a-b)を割り切るのは(a-b)=0の場合 なぜなら a,b∈Zn」という所がいまいちわかりません。 なぜそうなるのかどなたか教えてください！
- susuken23
- お礼率12% (1/8)
- 数学・算数
- 回答数3
- ありがとう数0
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- alice_44
- ベストアンサー率44% (2109/4759)
←A No.2 m と n が素でないとき、例えば m=6, n=10 のとき 何が起こるかを見れば、ただ「一次関数だから」では 済まないことが解るよ。 m=6, n=10, c=1 のとき、f(2)=f(7)=3 だが、 Z10 において 2 と 7 は異なる。
- snorioo
- ベストアンサー率54% (103/188)
この証明問題そもそもの意味が分かりません。 f(a) = ma + c であればこれは一次関数ですから、f(a) = f(b)であれば a=b であるのは自明ではないのでしょうか？？？ Znや合同式を持ち出す意味が分かりません。
- alice_44
- ベストアンサー率44% (2109/4759)
a-b が n で割り切れるところまでは ok ですね？ a-b=nk となる整数 k があるのだから、a=b+nk です。 a と b を n で割った余りは等しいということ。 それって、Zn の元が等しいことの定義ですよね？
関連するQ&A
- 合成問題の証明教えてください(＞＜)
背理法を使ってみたんですがよくわかりませんでした。 写像f:A→B,g:B→Cとその合成写像g。fについて示せ。 １ f,gともに全単射であればg。fはまた全単射である。またこのとき(g。f)＾-1=f＾-1。ｇ^-1である。 ２ g。fが全単射ならばgは全射である。もしこのとき、さらにgが単射でもあれば、fは全射である。 ３ g。fが単射ならば、fは単射である。もしこのとき、さらにfが全射でもあれば、gは単射である。 わかる方よろしくお願いします。
- ベストアンサー
- 数学・算数
- 証明の解説
証明 ｎ＝ｐｑ （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の項目に出てきたんでしつもんしました。 ぜひ回答よろしくお願いします
- 締切済み
- 数学・算数
- 写像の証明問題です。よろしくお願いします。
写像の問題です。よろしくお願いします。 (1)２つの写像f:Ｘ→Y、f:Ｙ→Zがある。g・fが全射ならばgは全射であるとする。ここでさらにgが単射であると仮定すればfも全射となることを証明せよ。 (2)自然数Nと零を合わせた集合N∪{0}から整数の集合Zへの写像で、全単射となるものを構成し、その理由を説明せよ。
- 締切済み
- 数学・算数
- 自身への写像が全単射となることの証明
(1) 写像f:Ａ→Ａとする。Aが有限集合であるとき、写像fが単射ならばfは全単射である事を示せ。 (2) Aが無限集合であるとき、fは全単射か。そうであれば証明せよ。そうでないなら反例を示せ。 上の問題の(1)は以下のように考えました。 f(A) は A の部分集合。 f(A)≠A と仮定すると、A とその真部分集合との間に全単射が存在したことになる。これは、無限集合の定義であるため、有限集合は全単射である。 このような証明で十分なのでしょうか？また、上のように考えたのでAが無限集合であるときはfは全単射ではないと思うのですが、反例が思いつきません。 わかる人がいれば教えてください。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 写像の証明問題を教科書の定理、定義を組み合わせながらやっていたのですが
写像の証明問題を教科書の定理、定義を組み合わせながらやっていたのですがうまく出来ません。 どなたか次の問題の証明過程を教えてください。 ｆ:A→B, g:B→Aをともに全単射とすれば、g。f （gとfの合成写像）: A→Cも全単射である。 このとき、（g。f）＾-1 (gとfの合成写像のインバース)＝f^-1。g^1（fのインバースとgのインバースの合成写像）であることを示せです。 お願いします。
- ベストアンサー
- 数学・算数
- 線形代数の写像の問題です
教科書の問題ですが、 「集合Ａ，Ｂがそれぞれm,n個の元からなるとする。 1)AからＢへの写像の個数を求めよ。 2)ＡからＢへの単射の個数を求めよ。 3)ＡからＢへの全単射の個数を求めよ。」 質問です。f：A→Bが写像なので、m個だと思いましたが、1)の答えはn^m、2)の答えはm≦nの時、nPm、3)の答えはm=nの時m!となっています。 どのように理解したらよいのか分かりません。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 写像の問題をお教え下さい。
いくら考えても全くわかりません。 お教えいただければ大変嬉しいです。お願いします。 問題 Ａをm×n行列とし、行列とベクトルの積で与えられる線形写像A:R＾n →R＾m：x ↦ Axを考える。 以下の問いに答えよ。 (1) 写像Aが単射であるならば、n ≤ mであることを示せ。 (2) n ≤ mであって、写像Ａが単射でない例をあげよ。 (3) 写像Aが単射であるならば、rankA = nであることが必要十分であることを示せ。 (4) 写像Aが全射であるならば、n ≥ ｍであることを示せ。 (5) n ≥ mであって、写像Aが全射でない例をあげよ。 (6) 写像Aが全射であるならば、rankA = mであることが必要十分であることを示せ。 (7) もしn = mならば、写像Aが全単射であることとAが正則であることが必要十分であることを示せ。
- 締切済み
- 数学・算数
