a,bは互いに素な正の整数とする。
1、kを整数とするとき、akをbで割った余りをr(k)で表す。k,lをb-1以下の正の整数とするとき、k≠lならばr(k)≠r(l)であることを示せ。
2、am+bn=1を満たす整数m,nが存在することを示せ。
という問題ですが、どう考えたらよいのか分かりません…。
1の方は、akとalをそれぞれbs+r(k),bt+r(l)みたいに表してみたのですが、どう解いていけばよいのか…。
2もa(m-m(0))+b(n-n(0))=0,-(am(0)+bn(0))=1とおいてみたのですが…。
考え方だけでもいいので、教えて頂けたら嬉しいです。
回答宜しくお願いします。
No.4ベストアンサー
- 回答日時:
#2です。
少し気になったこともあったので、補足しておきます。
1の背理法ですが、ak, alの「差」を考えると以下のようになります。
a(k- l)= b(s- t)+ r(k)- r(l)
ここで、r(k)= r(l)と仮定します。(背理法の仮定)
すると、
a(k- l)= b(s- t)
#2で示した「2点」を用いると、k- l= 0でなければならないことが示されます。
(k- lのとり得る範囲に、0以外の bの倍数が含まれていないことがポイントです)
これは k≠ lであることに反するので、r(k)= r(l)とはならないことがわかります。
2については、#1さんも示されているように一意性から r(m)= 1なる mが存在することを利用します。
am+ bn
= { bx+ r(m) }+ bn
= b(x+ n)+ r(m)
mは r(m)= 1 なる m、
nは x+ n= 0すなわち n= -x
とすれば、am+ bn= 1となります。
#3さんの回答では、少し「詰め」となる部分が弱いように感じました。
過去の質問で、同じような考え方を使った問題がありました。
時間があれば、類題として考えてみてください。
http://okwave.jp/qa/q5845581.html
No.3
- 回答日時:
1
背理法を使う
要するに、k≠lなのに、r(k)=r(l)となることがあると仮定する
r(k)=r(l)=r
このとき、整数M,Nを用いてak=bM+r,al=bN+rとかける。
このときa(k-l)=b(M-N)となるからa(k-l)がbで割り切れる。
a,bが互いに素だから、k-lがbで割り切れる。
ところがk,lは相異なるb-1以下の正の整数だから、
-b<k-l<0または0<k-l<bとなりk-lはbで割り切れないから不合理
以上よりk≠lならばr(k)≠r(l)であることが示された。
2
1より、a,2a,・・・,a(b-1)をbで割った余りはすべて異なる。
a,2a,・・・,a(b-1)はいずれもbでは割り切れないので、
a,2a,・・・,a(b-1)をbで割ったときの余りは1,2,・・・,b-1
のどれかがか必ず現れる。
それをmaとすると、整数nを用いてam=1-bnとかける。
したがってam+bn=1をみたす整数m,nの存在がいえた
・・・・・・・・・・(一応2の別解も)・・・・・・・・・・・
M={kは整数|整数x,yを用いてk=ax+byとかける}とおく
ここで1∈Mを示す。
Mの正の元のうち最小となるものをeとおく
Mから任意に元kをとる。
以下のようなことが言える。
kはeで割り切れる。…※
※の証明
kをeで割り切れないと仮定する。…◎
k,eはMの元だから、整数s,t,u,vを用いて
au+bv=k,as+bt=e…○
kをeで割り、商をq、余りをrとすると
k=eq+r,0<r<e…●
○よりr=k-eq=a(u-sq)+b(v-tq)だから、rもMの元となる。
●より0<r<eだから、rはMより小さな正のMの元となるが
これはMの正の元のうち最小となるものがeであることに反する。
したがって◎の仮定は誤りで、※が正しいことが示された。
※の証明ここまで
a=a*1+b*0,b=a*0+b*1だからa,bもMの元となる。
※よりa,bはeで割り切れることがいえる。
e≧2と仮定すると、eはa,bの2以上の公約数となり
a,bが互いに素であることに反する。
よってe=1
○よりas+bt=1をみたす整数m,nの存在が言えた。
(m=s,n=tとおけばよい)
No.2
- 回答日時:
こんにちわ。
^^>1の方は、akとalをそれぞれbs+r(k),bt+r(l)みたいに表してみたのですが、
そこまではいいと思いますよ。
考え方の大枠としては、「背理法」を使えばよいかと。
上の ak、alの式を「縦に並べて」書いてみてください。
そして、背理法を用いる上で大切になってくるのが、次の 2点です。
・aと bは互いに素であること
・1≦ k≦ b-1、1≦ l≦ b-1であることから、k- lは?
1の問題で帰結されていることをまとめると
1≦ k≦ b-1ですが、余りである r(k)も 1≦ r(k)≦ b-1を満たしています。
(∵aと bは互いに素なので割りきれることはない)
kも r(k)も b-1とおりあるので、「1対1対応」している(一意的である)ことがわかります。
(kが異なる値ならば r(k)も必ず違う値になっており、r(k)は 1~ b-1のすべての値をとり得る)
2は1の結果を応用することになりますね。
am= bx+ r(m)とでも表して、am+ bnに代入してみましょう。
あとは、この値が 1となるようにできるかどうかが示せれば終わりです。
その際に、先の「1対1対応(一意的)」を利用することになります。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 上三角行列のn乗の証明 2 2023/07/23 21:45
- 数学 どうか教えてください。 4 2022/07/02 20:18
- 数学 (1) 方程式 65x+31y=1の整数解をすべて求めよ。 (2) 65x+31y=2016 を満た 1 2022/06/29 11:02
- 数学 2次以上の多項式g(x)であって, 任意の無理数に対して無理数の値を取るものは存在しないことを示せ. 8 2022/06/27 11:28
- 数学 Zを整数の加法群とする。 M={7,8}はZの生成形になることを示せ。(Z=〈7,8〉となることを示 3 2022/11/20 22:14
- 数学 数学の質問 6 2022/08/28 07:49
- 数学 nは正の整数であり、偶数。 n(n+1)(n+2)(n+3)は素因数が3つ。 nを求めよ。 という問 8 2022/09/26 18:15
- 数学 教えてください。 2 2022/06/30 14:26
- 高校 mod 問題 2 2022/08/11 10:19
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
a>0、b>0⇔a+b>0、ab>0
-
n=3の倍数ならば、n=6の倍数で...
-
命題「PならばQ」でPが偽ならば...
-
高校数学、論理
-
強い仮定、弱い仮定、とは
-
数Ⅰで習う背理法についてです。...
-
背理法が成り立つ理由
-
逆、裏、否定、対偶
-
a[n]=Σ[k=0,n-1]a[k]+1,a[0]=1...
-
大学の数学の整数について
-
数学 x,yは実数とする。「xy+1=...
-
命題を証明せよとはどういう意...
-
数学の背理法について質問です...
-
この問題の逆 裏 対偶と真偽と...
-
有理数+無理数=無理数 の証明
-
ゴールドバッハの予想 関連
-
写真の命題を数学的帰納法で証...
-
証明をお願いします
-
3.141592653589793238462643383...
-
数学的帰納法の根本的な疑問な...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
不完全定理により、「ある命題...
-
命題「PならばQ」でPが偽ならば...
-
超越数は必ず無理数でないとい...
-
数学の背理法について質問です...
-
数学の問題です! 教えてくださ...
-
強い仮定、弱い仮定、とは
-
a>0、b>0⇔a+b>0、ab>0
-
命題を証明せよとはどういう意...
-
次の空欄に当てはまるものを以...
-
「逆もまた真なり」について
-
x≠1⇒xの二乗≠1の真偽
-
高校数学です!m,nを整数とする...
-
「逆は必ずしも真ならず」の証...
-
背理法と対偶証明の違いについて
-
n=3の倍数ならば、n=6の倍数で...
-
高校数学、論理
-
共分散の符号と相関係数の符号...
-
有理数を文字置き→互いに素な整...
-
カントールの対角線論法につい...
-
反対称的な2項関係の個数
おすすめ情報