a,bは互いに素な正の整数とする。

質問

a,bは互いに素な正の整数とする。
１、kを整数とするとき、akをbで割った余りをr(k)で表す。k,lをb-1以下の正の整数とするとき、k≠lならばr(k)≠r(l)であることを示せ。
２、am+bn=1を満たす整数m,nが存在することを示せ。

という問題ですが、どう考えたらよいのか分かりません…。
１の方は、akとalをそれぞれbs+r(k),bt+r(l)みたいに表してみたのですが、どう解いていけばよいのか…。
２もa(m-m(0))+b(n-n(0))=0,-(am(0)+bn(0))=1とおいてみたのですが…。

考え方だけでもいいので、教えて頂けたら嬉しいです。
回答宜しくお願いします。

回答No.4

naniwacchi · ベストアンサー

#2です。

少し気になったこともあったので、補足しておきます。

１の背理法ですが、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)とはならないことがわかります。

２については、#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

yoikagari

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

naniwacchi

こんにちわ。＾＾

＞１の方は、akとalをそれぞれbs+r(k),bt+r(l)みたいに表してみたのですが、
そこまではいいと思いますよ。
考え方の大枠としては、「背理法」を使えばよいかと。

上の ak、alの式を「縦に並べて」書いてみてください。
そして、背理法を用いる上で大切になってくるのが、次の 2点です。
・aと bは互いに素であること
・1≦ k≦ b-1、1≦ l≦ b-1であることから、k- lは？

１の問題で帰結されていることをまとめると
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のすべての値をとり得る）

２は１の結果を応用することになりますね。
am＝ bx+ r(m)とでも表して、am+ bnに代入してみましょう。
あとは、この値が 1となるようにできるかどうかが示せれば終わりです。
その際に、先の「1対1対応（一意的）」を利用することになります。

回答No.1

Tacosan

1: 対偶
2: 1 から r(k) = 1 となる k が存在することを示す.