- 締切済み
数列2(基本的な質問かもしれませんが)
1からnまでの整数のうち, N1の倍数 でもあり N2の倍数でもある数がいくつあるかは求められます.(ユークリッドの互除法などによって) 一方 k×N1+1(kは自然数)で表され,N2の倍数でもある数がいくつあるかは求められるのでしょうか? 勿論具体的に数値例がある場合はできると思うのですが. 基本的な話かもしれないのですが,お願い致します.
- 数学・算数
- 回答数3
- ありがとう数1
- みんなの回答 (3)
- 専門家の回答
みんなの回答
- stomachman
- ベストアンサー率57% (1014/1775)
N1とN2じゃ読みにくいのでx,yとしましょう。そして正の自然数の集合をNと書くことにします。 [1] y=1の場合には、(kx+1)/yは常に自然数です。だから、 {k| ∃m(m∈N ∧ kx+1 = my)}= N です。 [2] x=1の場合には、(kx+1)/yが自然数になるのは(k+1)がyの倍数の場合であり、その場合だけです。従って、 {k| ∃m(m∈N ∧ kx+1 = my)} = {(h+1)y-1| h∈N} です。 [3] x>1,y>1であり、xとyが互いに素ではない場合には、kx+1=my となる正の自然数の対<k,m>は存在しません。 (仮にそのようなk,mが存在したとすれば、最大公約数をg>1とするとき x=pg, y=qg となるp,q(p∈N ,q∈N)が存在して、しかもkx+1=myですから (kp)g+1=(mq)g よって、両辺をgで割れば (kp)+1/g=(mq) 1/g=(mq)-(kp) ですから1/g (g>1)が整数ということになってしまいます。) [4] x>1,y>1であり、しかもxとyが互いに素である場合。このとき、 (1) rxをyで割った余りu(つまり u=rx mod y)は、rを1~yまで変えると0~y-1の全ての値を丁度1度ずつ取ります。 (仮に、uが0~y-1の値のうちのどれかを取らないとするならば、 rを1~yまで変えたとき、uの値として0~y-1のうち少なくとも一つの数vが2度以上現れたことになります。つまり、1≦r≦y, 1≦s≦y, r>sであって、しかもv = rx mod y = sx mod y となるr,sが存在することになる。すると (rx-sx) mod y = (rx mod y - sx mod y) mod y= (v-v) mod y = 0 だから (r-s)x mod y = 0であり、しかも1≦(r-s)≦y-1<yです。 よって、(r-s)xはxとyの公倍数であって、しかもx≦(r-s)x<xy。つまりxとyは互いに素ではないことになってしまいます。) 従ってu=y-1となるrを選べば、 (rx+1) mod y = 0 すなわち((rx+1)/y∈Nです。 (2) さて、((rx+1)/y∈N, 1≦r≦yとしますと、任意の自然数cについて ((r+c)x+1)/y = ((rx+1)/y + cx/y ですが、xとyは互いに素ですから、cx/yが自然数になるのはcがyの倍数である場合に限られます。 であり、しかも {k| ∃m(m∈N ∧ kx+1 = my)}= {r+(u-1)y | u∈N} となります。 だから、rを具体的に求めさえすれば、{r+(u-1)y | u∈N}は簡単に分かります。 かくて、1~nの内で、{k| ∃m(m∈N ∧ kx+1 = my)}の要素が幾つあるかを計算するのはもう、簡単な問題ですね。 ★modの説明が必要かな? a mod b = a-[a/b]b です。ここに[x]は「xを越えない最大の整数」のことです。従って、0≦a mod b<b。
- pancho
- ベストアンサー率35% (302/848)
「N1とN2が互いに素である」という前提を置くと、 [1 ~ N1*N2]間にN1とN2の公倍数が1つのみ(N1*N2)存在します。 同様に(証明は省きますが)、 [2 ~ N1*N2]間に (N1の倍数+1)とN2の倍数で共通なものが1つのみ存在します。 このことより、n=m(N1*N2)+1+l[m、lは自然数]とすると、m個の共通倍数(?)が存在することになります。 次に、N1とN2が互いに素ではない場合、N1とN2の最大公約数をaとすれば、[2 ~ a+1]間に共通倍数(?)が何個あるか考えれば、同じ方法がとれます。 ここからは、ここのケースに依って分かれてくるでしょう。例えば、N1とN2がともに偶数の場合、解はありません。(共通する数は無い) 私にわかるのはここまでです。 以上。
- starflora
- ベストアンサー率61% (647/1050)
まず、第一の問題は、「アルゴリズム的」には解けるのです。 どういう風に解けるかと言いますと、 N1とN2が、素な関係にある時(つまり、N1, N2 が、仮に公約数があっても、その公約数の素数が、互いに共通性がない場合)、一般的な解は、N1^a*N2^b<=n を満たす、a, b の組み合わせの数を求めることになります(a,b は自然数)。しかし、これは、n, N1, N2 が具体的に決まらなければ計算できません。そうではないでしょうか? n, N1, N2 から、例えば、(n+N1+N2)/N1*N2 などという式が出てくるのではなりません(これは出鱈目な式ですが。また N1, N2 が互いに素でなければ別の解法になります)。 第二の問題も、解法のアルゴリズムはありますが、具体的にどうなるかは、具体的に変数が決まらないと解けません。 解き方のアルゴリズムとしては、例えば、k×N1+1 が N2 の倍数であれば、nを、k×N1+1 で割って、小さい方の近似自然数を出せば、それがこたえでしょう。そうでない場合は、また別の条件次第で答えが変わって来ます。 それとも、第一の問題の解が、例えばmとすると、第二の答えは、このmを使って表現でき、それはどうなるかという問いなのでしょうか? (何を尋ねておられるのか、非常に曖昧です)。
関連するQ&A
- 数列
連続で投稿してしまうことをお許しください 2の倍数でも3の倍数でもない自然数全体を小さい順に並べてできる数列を a_1,a_2,a_3,・・・・・,a_n,・・・とする (1)a_100をもとめる (2)1003は数列{a_n}の第何項か? (3)mを自然数とするとき数列{a_n}の初項から第2m項までの和を求めよ。 (1)a_100=300かしら?適当にやったらうまくいった? (2)1003-500-334-167=169 169項?(n(2)=500,n(3)=334,n(6)=167) (3)1から2mまでの和から2の倍数の和を引いて、3の倍数の和を引いて6の倍数の和を足す。 2の倍数や3の倍数、6の倍数のシグマの計算式が立てられない。 mが3kのとき、3k+1のとき、3k+2のときで場合分け?
- ベストアンサー
- 数学・算数
- ユークリッドの互除法について
ユークリッドの互除法を使って最大公約数、整数解を求められると聞いたのですが、イマイチ要領がつかめません。 もしよろしければ、どなたかユークリッドの互除法での最大公約数、整数解の求め方を教えてください。
- 締切済み
- 数学・算数
- 最大公約数について
ユークリッドの互除法について勉強していて 途中で疑問に思ったことがあるのですが 例えば 288と108という数について 288と108の最大公倍数は36 288÷108=2余り72 ここから 108と72を取り出して この二つの数の最大公倍数も36 108÷72=1余り36 ここから72と36を取り出して、 この二つの数の最大公倍数も36 となりますが、なぜ割る数と余りの最大公倍数が、初めの数の最大公約数とずっと同じであり続けるのでしょうか? ユークリッドの互除法自体はある程度理解できています。 ユークリッドの互除法は、この数の動きを利用して最大公約数を求めていくようですが、なぜこのようなことになるのかが知りたいです。 難しい内容では理解できないので、できれば中学生レベルでも理解できるように説明してもらえればありがたいです。
- ベストアンサー
- 数学・算数
- 数I数と式の問題
【問題】nが5の倍数でない自然数の時、「n^4を5で割ると1余る」ことを証明せよ これを解くときに、いろんなやり方があると思うんですがまず 「nは5の倍数でないので、n=5k±1、n=5k±2(kは整数)」と置くとしますね? このとき、問題にはnは”自然数”ってあるんだから、kは「整数」ってだけだとnが負になることも出てこないでしょうか… 問題集の解答には整数、と書いてあるのですが、私は「kは自然数」か「kは正の整数」とかってしなくていいのかなぁ…と思ってしまうのですが、「kは整数」だけでいいならその理由をどなたか教えてください(> <) 些細なことなんですが、解答するとき、この部分だけがどうしても気になって…
- ベストアンサー
- 数学・算数
- 数列の問題でわからないことが・・・
200以上500以下の自然数の中で7で割ると5余り 13で割ると11あまるものは何個あるか?(黄色チャートの問題です) という問題について質問です。解答では 「7で割ると5あまる数は7(K-1)+5=7K-2 13で割ると11あまる数は 13(Lー1)+11=13Lー2 よって7K-2=13Lー2(K,Lは自然数) を満たす。よって7K=13L 7と13は互いに素であるからKは13の倍数である。 ゆえにK=13n(nは自然数)とあらわされて 題意の数は7×13n-2すなわち91n-2 条件を満たす自然数は初項89公差91の等差数列の各項となっている。 200以上500以下の自然数のなかでは、3,4,5 が該当し、答えは3個である」 とあったのですが、前半部分がわかりません。 「7で割ると5あまる数は7(K-1)+5=7K-2 13で割ると11あまる数は 13(Lー1)+11=13Lー2」 とあらわしていますが、7で割ると5あまる数は7K+5 13で割ると11あまる数は13L+11 ではないんでしょうか?なぜ7(K-1)+5=7K-2 、13(Lー1)+11=13Lー2とあらわしているのでしょうか? どこからの7(K-1)+5、13(Lー1)+11はきたのでしょか? もしかして、その後の計算で 7K-2=13Lー2(K,Lは自然数) とあらわすことによって、共通のマイナス2が消去できて 「7K=13L 7と13は互いに素であるからKは13の倍数である。 ゆえにK=13n(nは自然数)」と表すために、 両方に共通の数字がでるような式に変形したのでしょうか?
- ベストアンサー
- 数学・算数
- ユークリッドの互除法についての問題です。
ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき ax≡b (mod5) (2)aが4の倍数でないとき ax≡b (mod4) 誰か教えてください。
- ベストアンサー
- 数学・算数
- 数列の和の問題です。
以下の2問にお答え願いますでしょうか? かなり時間かけたんですが解答がないんで困ってます。ご協力お願いいたします。 自然数xに対して√xの整数部分をf(x)で表す。 (1)kを自然数とするとき、f(x)=kを満たす自然数xの個数をkを用い て表せ。 (2)nを自然数とするとき、次のn^2個の整数 f(1),f(2),f(3),・・・・・・,f(n^2)の和をnを 用いて表せ。
- 締切済み
- 数学・算数
- 余りが〇である時の連続する数の和の説明
(1)連続する2つの自然数があります。小さい方を5で割った余りが2であるとき、2つの数の和は5の倍数になります。そのわけを説明しなさい。 説明:nを整数とすると、小さいほうの数は5n+2と表せる。このとき、大きい方の数は、(5n+2)+1=5n+3と表せるから、これらの和は、(5n+2)+(5n+3)=10n+5=5(2n+1) ここで、2n+1は整数だから 5(2n+1)は5の倍数である。 よつてこの2つの自然数の和は、5の倍数である。 ここの2n+1は整数だから5(2n+1)は5の倍数であるという部分が解りません。 よろしくお願いします。
- ベストアンサー
- 数学・算数