- ベストアンサー
あまりの問題
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 ここからが全くわかりません！ヒントでもいいので教えてください！
- 数学・算数
- 回答数6
- ありがとう数6
- みんなの回答 （6）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (5)
- stomachman
- ベストアンサー率57% (1014/1775)
ANo.4へのコメントについてです。 しょーがねえなあ(~o~) 鳩は背番号1, 2, …を背負っていて、鳩の集合がN。一方、鳩の巣穴には「余り0」, 「余り1」, … の表札が掛かっている。そして、背番号iの鳩は「余りR(ia)」の巣穴に入るというルールである。 ここで仮に、「余り1」の巣穴にはどの鳩も入らない(つまり、どのiについてもR(ia)≠1である)と仮定しましょう。 すると、鳩が入れる巣穴がいくつあるかを考えれば、どれかの巣穴に２羽以上の鳩が入るという事態が生じることが分かります(鳩ノ巣論法)。このとき、その同じ巣穴に入った鳩たち（のうちの2羽）の背番号をi, jとすれば、R(ia)=R(ja)である。 後はわかるでしょ。
お礼
なるほど！説明していただきありがとうございます！
- stomachman
- ベストアンサー率57% (1014/1775)
あまりと言えばあまりの流れになってるようなので、大ひんと出しましょ。 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は互いに素」という条件がありました。 ということで、あとは「余りが何通り生じるか」。ここからの考え方は「鳩ノ巣論法」と呼ばれたりします。
お礼
鳩ノ巣論法を調べたんですがよく分からないしこの問題にどう使うかもわかりません！ 出来れば教えてください！
- Tacosan
- ベストアンサー率23% (3656/15482)
「対偶」について要確認
お礼
p⇒qの対偶は￢q⇒￢pですよね じゃあ「jと kが等しいとき、余りも等しい」の対偶は「あまりが等しくないとき、jとkが等しくない」ではないのですか？
- naniwacchi
- ベストアンサー率47% (942/1970)
最終的には式で示していくことになりますが、 何をしているのかをみるために敢えて言葉で書いてみると。 「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との繋がりが全く分からないです！
- naniwacchi
- ベストアンサー率47% (942/1970)
同じ内容の質問になってしまうので、少なくとも前の質問は締め切るべきかと。 解きたいということだったので、もうちょっと考えて欲しいですが。 そもそも「あまり」が持っている性質を知っていると、 これを示すことはさほど難しくないです。 先の質問で R(ja)＝ R(ka)ならば j＝ kを示していますが、 これの対偶をとるとどうなりますか？ 『j≠ kならば（R(ja)と R(ka)の関係式）』 そもそも Rとは bで割ったあまりなので、とり得る値の範囲が決まっています。 上の対偶と組み合わせて範囲を考えておきます。 同様に、jや kもとり得る値の範囲が決まっています。 Rと jや kは範囲自体は微妙に違っていますが、「個数」は同じはずです。 最終的には、一意性（1対1対応）になることを示せれば終わりです。
お礼
締め切るべきでしたね すみません 考えてもわからなくなったら補足質問します！
補足
一意性とはどう示すのでしょうか？
関連するQ&A
- 数学の問題2
aとbを2以上の互いに素な自然数とし、b個の自然数1、2、...、b全体の集合をＮとする また、自然数tに対して、tをbで割った余りをR(t)で表す (1)j∈Ｎ、k∈Ｎに対して、R(ja)＝R(ka)ならばj＝kであることを示せ このとき、「なにかの数二つ(m、nとします)をなにか(qとします)で割ったときのあまりが同じ⇔m－nもqで割りきれる」ことからa(j－k)がbで割りきれることになり、またaとbが互いに素だからj－kがbで割りきれます 一方1≦j≦b、1≦k≦bより数直線で考えて1－b≦j－k≦b－1 というところまできました！ なのに答えはいきなりbの倍数になるのはj－k＝0のときだけと言ってます！これはなぜですか？
- ベストアンサー
- 数学・算数
- 自然数nはいくつですか？ の問題
問題 727，153を自然数ｎで割ったら余りがそれぞれ7と9でした。 自然数ｎは何個でしょうか？ 解）商をq1 q2として，727＝q1n+7 153=q2+9で表す。 720＝q1ｎ 144＝q2ｎ 素因数分解して，720＝2^4×3^2×5 144＝2^4×3^2 で・・・・・ このあとすぐに答えがでるとは思うのですが，わからなく・・。 またはこんなことしなくても解答でるかもしれません。 どのように考えればいいですか？
- ベストアンサー
- 数学・算数
- 論理的な誤りがあるなら指摘して
いまnを3以上の自然数、mを自然数とする。 f(n)を「nと互いに素でnよりも小さい自然数の個数」と定義します。 f(6)なら、1、2、3、4、5のなかで互いに素なのは、1、2、4、5の4個よりf(6) = 4です。 さてm<nのときにmとnが互いに素なら、n-mとnも互いに素です（これは証明されたとします） このときf(n)が偶数であることを証明します。 ------------ k∈Nとして n = 2k＋1のとき ｛１、２・・k｝の集合をA ｛k+１、k+２・・2k｝の集合をBとする。集合Aでnと互いに素な自然数をrとすると、 1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+1≦ n-r ≦ 2kより互いに素なn-rは必ず集合Bに存在するので、集合Aの互いに素な個数とBの個数は同数なので、f(n)は偶数になる n = 2k＋2のとき ｛１、２・・k｝の集合をA ｛k+2、k+２・・2k+1｝の集合をBとする。 ｛k+1｝の集合をCとする 集合Cにおいて、n =2(k+1)とk+1は因数としてk+1(≧2)を持つので互いに素ではないのは 明らか。 集合Aでnと互いに素な自然数をrとすると、 1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+2≦ n-r ≦ 2k+1より互いに素なn-rは必ず集合Bに存在し、さきほどと同じ議論になるので、f(n)は偶数になる qed で何か誤りがあるかね？
- 締切済み
- 数学・算数
- 証明について
a,bを整数とするとき次の2つの条件(i),(ii)について(i)と(ii)は同値であることを証明する問題です。 (i) a,bはお互いに素である。すなわち、aとｂの最大公約数は1である。 (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在する。 (i)の問題について ２つの整数aとbの最大公約数をGとおくと a=a'G,b=b'G(a',b'はお互いに素）とする。 (1)aをbで割ったときの商をq,余りをrとするとa=bq+r rについて解くと r=a-bq 2つの整数はaとbはa=a'G,b=b'G(a',b'とおけるので r=a'G-b'G この後どのように証明するのでしょうか？ (ii) ax(0)+by(0)=1となる２つの整数x(0),y(0)が存在はどのように証明するのでしょうか？
- 締切済み
- 数学・算数
- 教えてください
１対１の対応の演習数学１のＰ９４の７（１）です。 問題はaとbを２以上の互いに素な自然数とし、b個の自然数１，２，・・・，b全体の集合をＮとする。また，自然数ｔに対して，ｔをbで割った余りをＲ（ｔ）で表す。 （１）ｊ∈Ｎ，ｋ∈Ｎに対して，Ｒ（ｊa)＝Ｒ（ｋa）ならば，ｊ＝ｋであることを示せ。とあって 解答 Ｒ（ｊa）＝Ｒ（ｋa）より，ｊa－ｋa＝（ｊ－ｋ）aはｂで割り切れる。ところが，aとｂは互いに素により，aはｂと共通の素因数を１つも持たない。よって（ｊ－ｋ）aがｂで割り切れるには，j－kがｂの倍数でなければならない。他方，１≦ｊ≦ｂ，１≦ｋ≦ｂより，－（ｂ－１）≦j－ｋ≦ｂ－１となり，これを満たすｊ－ｋがｂの倍数となるのは，ｊ－k＝０のときに限る。よって，ｊ＝ｋである。（証明終わり） とあるのですが、どうして－（ｂ－１）≦ｊ－ｋ≦ｂ－１となるのかわかりません。どうかよろしくお願いします。
- 締切済み
- 数学・算数
- 既約剰余類群の証明
１つめは剰余類の掛け算。2つめは互除法の原理がわからないので質問します。 読んでいる本では、(a,b)でaとbの最大公約数を表すことにし、(k,n)=1⇔ kとnは互いに素。￣0(本では0の上に￣)を余りが0の類としています。 定義 Z/nZの部分集合 {￣K|(k,n)=1,1≦k≦n-1}は×に対して群になっている。これを(Z/nZ)*と書き、既約剰余類とよぶ。と書かれていて。 ×に関して閉じていることを確認しましょう。nと互いに素であるk,lがあるとき、その積klもnと互いに素になります。klをnで割った商をq,余りをmとすると、 kl=qn+mと書くことができます。kl≡qn+m (mod n) ∴kl≡m (mod n)より、ここからが1つめのわからない計算です。￣ｋ×￣ｌ=￣ｍ 自分は、n=10,k=3,l=9,m=7 3×9=2×10+7として3を２で割った余り、9を２で割った余りそれらの積が、7を２で割った余りに等しいかを計算したのですが、２以降3,4,5・・・nについても成り立つと思っていました。しかし、n=10,k=3,l=9,m=7のとき、3と9を３で割った余りの積0、7を３で割った余り1と両辺は一致しません。この場合￣ｋ×￣ｌ=￣ｍは3を10で割った余り、9を10で割った余りそれらの積が、7を10で割った余りに等しいかを計算したときだけ成り立つことを書いているのかがわかりません。￣ｋ×￣ｌ=￣ｍの具体的な計算を教えてください。またこの後が、2つめのわからない点です。互除法の原理 a,bを自然数とするaをbで割った余りがrのとき、(a,b)=(b,r) より(m,n)=(kl,n)=1もわかりません。m=kl-qn よりｍをnで割った余りkl(klはｎと互いに素)から、(m,n)=(n,kl)と考えました。kl≡m (mod n)より単純にｍをklに書き換えただけとも思いました。(m,n)=(kl,n)=1を説明してください。 本では、(m,n)=(kl,n)=1よりmもnも互いに素になります。ですから、×について閉じています。と続きます。
- 締切済み
- 数学・算数
お礼
わかりました！アドバイスありがとうございます！