- 締切済み
整数論 合同≡
「自然数ｍが奇数とし、ｘｉ：＝２ｉ（１≦ｉ≦ｍ）とおく。このとき、任意の整数ｙに対して、ｙ≡ｘｉ（mod m）となるようなiがただ一つだけ存在することを証明せよ。」 証明をしたのですが、以下のようでいいのですか？ 添削して気づいたことを教えてください。 （証明） ｙ≡xi（mod ｍ）（１≦ｉ≦ｍ） 【1】ｍ＝１のとき、ｙ≡ｘ1≡２（mod １）より、明らかに成立。 【2】ｍ≠1のとき、i≠ｊとする。 xi≡ｘｊ（mod ｍ）と仮定すると 2i≡２ｊ（mod ｍ） i≡ｊ（mod ｍ） i≠ｊよりi≡/ｊ（mod ｍ） （←≡/は合同でない） 従って矛盾よりxi≡/ｘｊ（mod ｍ） 今、ｍ子の整数x1，x２，…，xmをｍで割った時の余りは全て異なる。 また、整数ｙをｍで割ったときの余りは0,1，…，m-1のｍ個。 よって任意の整数ｙに対して、ｙ≡ｘｉ（mod m）となるようなiがただ一つだけ存在する。
- 45han
- お礼率0% (0/2)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- graphaffine
- ベストアンサー率23% (55/232)
それでは、お言葉に甘えて添削しましょう。勿論、私の流儀で書かせてもらいます。 ｙ≡xi（mod ｍ）（１≦ｉ≦ｍ） （１行目） いきなりこれだけ書いても意味が不明です。ｙは何？ｍは何？と私なら言います。 問題からわかると言いたいなら、そもそもこの1行目は不要。 あえて書くとしたら、私ならば次のようになる。 奇数ｍが与えられたとき、任意の整数ｙに対しｙ≡xi（mod ｍ）（１≦ｉ≦ｍ）を満たすｉが一意に存在することを示す。 また、証明本体の構造は次のようになるでしょう。 「まず、存在することを示す。 存在証明を書く。 次に一意性を示す。 一意性の証明を書く。」 #1のかたの仰るように、確かに正しい存在証明 は書いてないですが ＞また、整数ｙをｍで割ったときの余りは0,1，…，m-1のｍ個。 は、存在証明を意図してるような感じですね。これを、きちんとした形にすればいいです。 一意性の証明は、#1の方に同感。
- eatern27
- ベストアンサー率55% (635/1135)
＞【2】ｍ≠1のとき、i≠ｊとする。 ＞ i≠ｊよりi≡/ｊ（mod ｍ） （←≡/は合同でない） まず、ここ。一般的には、i≠jならばi≡/jは成り立ちません。例えば、2≠5ですが、2≡5(mod 3)です。 したがって、1≦i,j≦mであると言う必要があるでしょう。 しかし、ここのi,jは「i≠ｊとする」という風に定義していますので、一般には1≦i,j≦mが成り立ちません。(もちろん、この範囲のを考えているのでしょうが)なので、最初から、1≦i＜j≦mなどとしておいた方がいいかと。(i,jの対称性からj＜iの場合は考えない) ＞ また、整数ｙをｍで割ったときの余りは0,1，…，m-1のｍ個。 細かいですが、ここも。 整数yをｍで割った時の余りは「余りの定義」から１つしかありません。(例えば、4を3で割った余りは1のみです) まぁ、おそらくは、yを整数全体で動かした時、「整数yをｍで割った時の余り」は、0,1，…，m-1のｍ種類の値を取りうる、という事を言いたいのでしょうが、それは不要です。(もちろん、書いてはいけない、というわけではないですが) 例えば、ｙをｍの倍数全体で動かしても、「任意のｙに対して、ｙ≡ｘｉ（mod m）となるようなiがただ一つだけ存在する」はやっぱり成り立ちますよね。だから、ｙがｍ種類の余りをとる事は重要ではありません。 で、一番重要なのは、 「ｙ≡xiとなるiが少なくとも１つは存在する」という事が書かれていないことでしょうか。 もちろん、この事は ＞今、ｍ子の整数x1，x２，…，xmをｍで割った時の余りは全て異なる。 から直ちに分かることです。が、この証明で示すべきことは 「ｙ≡xiとなるiが少なくとも１つは存在する」 「ｙ≡xiとなるiは存在したとしても１つだけ」 の２つですよね。 なので、「整数x1，x２，…，xmをｍで割った時の余りは、0,1,…,m-1の並び替え」など、２つをまとめて書いた形でも何でもいいですが、「整数x1，x２，…，xmをｍで割った時の余りが全ての余りを網羅している」という事を明らかな形で書いた方がいいと思います。 他は、問題ないかな、と。多分。 大枠は、45hanさんの方針でＯＫですので、参考程度ですが、 この問題に限らず、「ただ一つだけ存在する」を示す場合には、 「具体的に一つ提示する」(←この方針は使えない場合もある) 「２つあったら、その２つは同じもの」 の２つを証明する事が多いです。 前者の方はこの問題で言えば yをmで割った余りが2kの時は、i=kとすればよいし、 yをmで割った余りが2k+1の時は、i=(2k+1+m)/2とすればよい。 のように、具体的にiを一つとる、という方針ですね。 (具体的に見つからない場合は、別の方針で「少なくとも１つ存在する」を示すことになる) 後者の方は、割とよくやる証明ですね。この問題で言えば、 y≡xi≡xjとすると、2(i-j)≡0。0≦i-j≦m-1よりi=j という感じの証明になるでしょうか。(xi,xjの２つが条件を満たせば、xi=xjでなければならない、って事) 長文＆乱文失礼しました。
関連するQ&A
- 代数学の、整数の合同の問題を教えて下さい。
この問題がわからず困っています。 (1)n,mは互いに素な整数とする。 このとき、sn+tm=1となる整数s,tが存在する。 a,bを整数とする時、x=bsn+atmとおく。このとき、xは合同式 x≡a mod n x≡b mod m を満たすことを示しなさい。 (2)さらに、xをnmで割った余りをrとする。この時rは r≡a mod n r≡b mod m を満たすことを示しなさい。 という問題です。 分かる方、よろしくお願いいたします
- ベストアンサー
- 数学・算数
- こんな関数は存在する？存在しない？
とある理由で、以下のような問題を考えています。 しかしながら、どう証明（or反例）してよいのかいいアイディア が浮かばず、質問させていただきました。 -------------------------------------- 問い： ある関数f(x1,x2)が存在したとします。 この時下記条件を満足する関数g(x1,x2,...,xn)が存在できるか。 条件： まず、任意のiとj(j≠i)を選びます。 {xk}(k≠i,j)に対して任意の定数値{ck}を設定します。 こうして生成されたh(xi,xj)=g(c1,...,xi,...,xj,...,cn)を考えます。 この関数hがh(xi,xj) = a*f(xi,xj)を常に満足する。 ここでaは0以外の定数。 ------------------------------------- 一般的に証明するのは難しそうなので、g(x1,x2,x3)の場合などでもかまいません。 また、f(x1,x2)に対して拘束条件f(x1,x2)=f(x2,x1)をかけてもかまいません。 なにか「こういうアプローチで証明(or反例)できるのではないか？」といったアイディアをお持ちではないでしょうか？ ------------------------------------------- ちなみにこの問題は量子力学のN-representability問題に端を発しています。もしこの証明ができれば、N-representability問題に対してすこし切り込めるかなぁと考えている次第です。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 結合法則
M：空でない集合 φ：M×M→M φ(φ(x,y),z)＝φ(x,φ(y,z)) (∀x,y,z∈M)…☆ が成立しているとする。 X1,…,Xn∈Mが与えられたとき、Xi,X(i+1)に対しφを作用させる。次にn-1個の元X1,…,X(i-1),φ(Xi,X(i+1)),X(i+2),…,Xnを改めてY1,…,Y(n-1)と記し、またYj,Y(j+1)に対しφを作用させる。この操作を繰り返し最後に残った元をZとする。 このとき、X1,…,Xnに対しZを対応させる写像ψn:M^n→Mはφを作用させる場所によらず(つまりiやjなどによらず)well-definedである。 以上のことを証明してみたのですがあっているかどうかわからないので、教えて下さい。 (証明) nに関する帰納法で示す。 n=2…明らか n=3…☆により明らか。 ψ(n-1)までがwell-definedであると仮定する。 ψnがwell-definedであることを示すには ψ(n-1)(φ(X1,X2),X3,…,Xn)＝…＝ψ(n-1)(X1,…,X(n-2),φ(X(n-1),Xn)) (∀Xi∈M,i=1,…n)をいえばよい。 ψ(n-1)(X1,…,X(j-1),φ(Xj,X(j+1)),X(j+2),…,Xn)とψ(n-1)(X1,…,Xj,φ(X(j+1),X(j+2)),X(j+3),…,Xn)が等しいことをいえばOK。(j=1,…,n-2) ψ(n-1)のwell-defined性より ψ(n-1)(X1,…,X(j-1),φ(Xj,X(j+1)),X(j+2),…,Xn)＝ψ(n-2)(X1,…,X(j-1),φ(φ(Xj,X(j+1)),X(j+2)),X(j+3),…,Xn)…(1) ψ(n-1)(X1,…,Xj,φ(X(j+1),X(j+2)),X(j+3),…,Xn)＝ψ(n-2)(X1,…,X(j-1),φ(Xj,φ(X(j+1),X(j+2))),X(j+3),…,Xn)…(2) ☆より(1)＝(2)がわかるから ψ(n-1)(X1,…,X(j-1),φ(Xj,X(j+1)),X(j+2),…,Xn)とψ(n-1)(X1,…,Xj,φ(X(j+1),X(j+2)),X(j+3),…,Xn)が等しい。 したがってψnはwell-definedである。
- 締切済み
- 数学・算数
- 互換に関する定義
差積Δ（定義は下の通り）に互換をほどこすと、－１倍されることを 証明しようと思っています。 【差積Δの定義】 Δ＝Π（Xi－Xj) （※1≦i<j≦n） 【互換】 XiとXjの２つだけを交換するという置換のこと。（i,j)と表す。 つまり証明したい事を式で表すと （i,j)Δ＝－Δ です。 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ 今のところ次のような方針で証明をしようと考えました。 (1) となり同士の互換、つまり(i,i+1)Δ＝－Δを示す。 (2) 任意の互換は(i,i+1)を含む互換の積で表せることを示す。 (3) (1)(2)より（i,j)Δ＝－Δを示す。 ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ それぞれ感覚的には理解できたのですが、それをどう書いていいのか分からず、困っています。 どなたか、この方針で、証明を教えていただけないでしょうか。お願い致します。
- 締切済み
- 数学・算数
- オイラーの定理(整数)
nは自然数、aは整数とする。aとnが互いに素な時、a^{φ(n)}≡1( mod n)が成り立つ。 ここでφ(n)は「n以下の自然数でnと互いに素なものの個数を表す」"オイラーの関数"である。 この定理の例証で、例えばn=45=3^(2)*5のときa=7として考えます。 φ(45)=φ(3^2)*φ(5)となり、φ(3^2)=6、φ(5)=4です。 フェルマーの小定理よりmod 5 で、7^φ(45)={7^φ(5)}^φ(3^2)は {7^φ(5)}≡1 (mod 5)より、7^φ(45)≡1 (mod 5 )・・・(1)になり。 次に7^φ(3^2)≡1(mod 3^2)をしるします。フェルマーの小定理より mod 3 で 7^(3-1)≡1なので7^(3-1)＝3k+1、 7^φ(3^2)={7^(3-1)}^3＝(3k+1)^3=(3k)^3+3C1(3k)^2+3C2(3k)+1 3C1、3C2は３の倍数なので、7^φ(3^2)≡1(mod 3^2)・・・(2)です。 よって、7^φ(45)={7^φ(3^2)}^φ(5)≡1(mod 3^2)となります。 ここからが分からない箇所なのですが、中国の剰余定理から、 (1)かつ(2)⇔7^φ(45)≡■(mod 3^(2)*5)となる■が、1つだけ存在します。と書いてありますが、自分は中国の剰余定理は、m、nを互いに素な自然数とする。 x≡a(mod m)かつ x≡b(mod n)を満たす整数xはmnを法として、ただ1つ存在する。と書いてあることから、割る数が違えば、a,bのように余りもちがう場合に、整数xはmnを法として、ただ1つ存在する。と思っていたのですが、 この例証では、■≡7^φ(45) (mod 5)かつ■≡7^φ(45) (mod 3^2)のような余りが 一緒の場合を同時に満たす■を求めているような気がして、中国の剰余定理があてはまるか不安です。 自分の考えの間違いや、余りが一緒の場合でも中国の剰余定理が使えるかを教えてください。お願いします。 本では、■＝1のとき(1)、(2)が成り立つので、■＝1だとわかります。 よって7^φ(45)≡1(mod 45 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- 数値解析に関する実数列
ｋを1以上の整数とする。X0,X1,X2,X3,....,Xkを前もって与えられた数直線上に相異なる点列とし、y0,y1,...,ykを任意の実数列とする。各j=0,1,...,kに対してPjはPj(Xi)=yi,i=0,....,jを満たす高々j次の多項式とする。このとき、Pk(X)=Pk-1(X)であるための必要十分条件はPk-1(Xk)=ykであることを示したのですがどのように証明したらいいのかアドバイスお願いします（泣）
- ベストアンサー
- 数学・算数
