- ベストアンサー
あまりの問題
stomachmanの回答
- stomachman
- ベストアンサー率57% (1014/1775)
ANo.4へのコメントについてです。 しょーがねえなあ(~o~) 鳩は背番号1, 2, …を背負っていて、鳩の集合がN。一方、鳩の巣穴には「余り0」, 「余り1」, … の表札が掛かっている。そして、背番号iの鳩は「余りR(ia)」の巣穴に入るというルールである。 ここで仮に、「余り1」の巣穴にはどの鳩も入らない(つまり、どのiについてもR(ia)≠1である)と仮定しましょう。 すると、鳩が入れる巣穴がいくつあるかを考えれば、どれかの巣穴に2羽以上の鳩が入るという事態が生じることが分かります(鳩ノ巣論法)。このとき、その同じ巣穴に入った鳩たち(のうちの2羽)の背番号をi, jとすれば、R(ia)=R(ja)である。 後はわかるでしょ。
関連するQ&A
- 数学の問題2
aとbを2以上の互いに素な自然数とし、b個の自然数1、2、...、b全体の集合をNとする また、自然数tに対して、tをbで割った余りをR(t)で表す (1)j∈N、k∈Nに対して、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を自然数nで割ったら余りがそれぞれ7と9でした。 自然数nは何個でしょうか? 解)商をq1 q2として,727=q1n+7 153=q2+9で表す。 720=q1n 144=q2n 素因数分解して,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のとき {1、2・・k}の集合をA {k+1、k+2・・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のとき {1、2・・k}の集合をA {k+2、k+2・・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とbの最大公約数は1である。 (ii) ax(0)+by(0)=1となる2つの整数x(0),y(0)が存在する。 (i)の問題について 2つの整数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となる2つの整数x(0),y(0)が存在はどのように証明するのでしょうか?
- 締切済み
- 数学・算数
- 教えてください
1対1の対応の演習数学1のP94の7(1)です。 問題はaとbを2以上の互いに素な自然数とし、b個の自然数1,2,・・・,b全体の集合をNとする。また,自然数tに対して,tをbで割った余りをR(t)で表す。 (1)j∈N,k∈Nに対して,R(ja)=R(ka)ならば,j=kであることを示せ。とあって 解答 R(ja)=R(ka)より,ja-ka=(j-k)aはbで割り切れる。ところが,aとbは互いに素により,aはbと共通の素因数を1つも持たない。よって(j-k)aがbで割り切れるには,j-kがbの倍数でなければならない。他方,1≦j≦b,1≦k≦bより,-(b-1)≦j-k≦b-1となり,これを満たすj-kがbの倍数となるのは,j-k=0のときに限る。よって,j=kである。(証明終わり) とあるのですが、どうして-(b-1)≦j-k≦b-1となるのかわかりません。どうかよろしくお願いします。
- 締切済み
- 数学・算数
- 既約剰余類群の証明
1つめは剰余類の掛け算。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つめのわからない計算です。 ̄k× ̄l= ̄m 自分は、n=10,k=3,l=9,m=7 3×9=2×10+7として3を2で割った余り、9を2で割った余りそれらの積が、7を2で割った余りに等しいかを計算したのですが、2以降3,4,5・・・nについても成り立つと思っていました。しかし、n=10,k=3,l=9,m=7のとき、3と9を3で割った余りの積0、7を3で割った余り1と両辺は一致しません。この場合 ̄k× ̄l= ̄mは3を10で割った余り、9を10で割った余りそれらの積が、7を10で割った余りに等しいかを計算したときだけ成り立つことを書いているのかがわかりません。 ̄k× ̄l= ̄mの具体的な計算を教えてください。またこの後が、2つめのわからない点です。互除法の原理 a,bを自然数とするaをbで割った余りがrのとき、(a,b)=(b,r) より(m,n)=(kl,n)=1もわかりません。m=kl-qn よりmをnで割った余りkl(klはnと互いに素)から、(m,n)=(n,kl)と考えました。kl≡m (mod n)より単純にmをklに書き換えただけとも思いました。(m,n)=(kl,n)=1を説明してください。 本では、(m,n)=(kl,n)=1よりmもnも互いに素になります。ですから、×について閉じています。と続きます。
- 締切済み
- 数学・算数
お礼
なるほど!説明していただきありがとうございます!