あまりの問題

質問

aとbを2以上の互いに素な自然数とし、b個の自然数1、2、...、b全体の集合をＮとする また、自然数tに対して、tをbで割った余りをR(t)で表す
(1)i∈Ｎ、R(ia)＝1をみたすiが存在することを示せ

とりあえずia＝bq(iaをbで割ったときの商とする)＋R(ia)だからR(ia)＝ia－qより
ia－q＝1

ここからが全くわかりません！ヒントでもいいので教えてください！

回答No.5

eclipse2maven · ベストアンサー

a,b は　互いに素だから

ma + bn = 1 なる整数　m,n が存在する

従って

ma ≡　　1 - nb ≡　1 (mod b)

こういう話は　bで　割れるものは全部０だと思う方が見通しよくなります。それが　剰余類（あまりだけの世界です）

お礼

わかりました！アドバイスありがとうございます！

回答No.6

stomachman

ANo.4へのコメントについてです。

　しょーがねえなあ(~o~)

　鳩は背番号1, 2, …を背負っていて、鳩の集合がN。一方、鳩の巣穴には「余り0」, 「余り1」, … の表札が掛かっている。そして、背番号iの鳩は「余りR(ia)」の巣穴に入るというルールである。

　ここで仮に、「余り1」の巣穴にはどの鳩も入らない(つまり、どのiについてもR(ia)≠1である)と仮定しましょう。

　すると、鳩が入れる巣穴がいくつあるかを考えれば、どれかの巣穴に２羽以上の鳩が入るという事態が生じることが分かります(鳩ノ巣論法)。このとき、その同じ巣穴に入った鳩たち（のうちの2羽）の背番号をi, jとすれば、R(ia)=R(ja)である。

　後はわかるでしょ。

お礼

なるほど！説明していただきありがとうございます！

回答No.4

stomachman

あまりと言えばあまりの流れになってるようなので、大ひんと出しましょ。

i, j（i∈N, j∈N, i≠j）について、
　　(ia-R(ia))も(ja-R(ja))もbの倍数である。
だから、
　　(ia-R(ia))-(ja-R(ja))もまた、bの倍数である。
式を整理して
　　(i-j)a +(R(ja)-R(ia))はbの倍数である。

　ここで、もしR(ia) = R(ja)であったなら
　　 (i-j)aはbの倍数である。
でも「aとbは互いに素」という条件がありました。

ということで、あとは「余りが何通り生じるか」。ここからの考え方は「鳩ノ巣論法」と呼ばれたりします。

お礼

鳩ノ巣論法を調べたんですがよく分からないしこの問題にどう使うかもわかりません！
出来れば教えてください！

回答No.3

Tacosan

「対偶」について要確認

お礼

p⇒qの対偶は￢q⇒￢pですよね
じゃあ「jと kが等しいとき、余りも等しい」の対偶は「あまりが等しくないとき、jとkが等しくない」ではないのですか？

回答No.2

naniwacchi

最終的には式で示していくことになりますが、
何をしているのかをみるために敢えて言葉で書いてみると。

「jと kが等しいとき、余りも等しい」ということから、
「jと kが異なるときには、余りも異なる」ということが言えます（対偶）。

jと kはともに同じ 1～bの間の数でしたから、
結果として「i＝ 1～bの数に対する R(ia)の値は互いに異なる」ことになります。

ところで、R(ia)とは bで割った余りと定義されているので、
R(ia)がとり得る値の範囲は 0～ b-1という b個の数となっています。

上の内容をまとめていくと、次のような結論に至ります。
「ｉのとり得る数の候補が b個あり、R(ia)がとり得る値の候補も b個あり、
R(ia)は互いに異なる。」

お礼

「jと kが等しいとき、余りも等しい」ということから、
「jと kが異なるときには、余りも異なる」ということが言えます（対偶）。

対偶は「余りが異なるとき、jとkが異なる」じゃないのですか？

それにia－bq＝1との繋がりが全く分からないです！

回答No.1

naniwacchi

同じ内容の質問になってしまうので、少なくとも前の質問は締め切るべきかと。
解きたいということだったので、もうちょっと考えて欲しいですが。

そもそも「あまり」が持っている性質を知っていると、
これを示すことはさほど難しくないです。

先の質問で R(ja)＝ R(ka)ならば j＝ kを示していますが、
これの対偶をとるとどうなりますか？
『j≠ kならば（R(ja)と R(ka)の関係式）』

そもそも Rとは bで割ったあまりなので、とり得る値の範囲が決まっています。
上の対偶と組み合わせて範囲を考えておきます。
同様に、jや kもとり得る値の範囲が決まっています。
Rと jや kは範囲自体は微妙に違っていますが、「個数」は同じはずです。

最終的には、一意性（1対1対応）になることを示せれば終わりです。

お礼

締め切るべきでしたね すみません
考えてもわからなくなったら補足質問します！

補足

一意性とはどう示すのでしょうか？