数列２（基本的な質問かもしれませんが）

質問

１からｎまでの整数のうち，
N1の倍数 でもあり N2の倍数でもある数がいくつあるかは求められます．（ユークリッドの互除法などによって）

一方
k×N1+1(kは自然数）で表され，N2の倍数でもある数がいくつあるかは求められるのでしょうか？

勿論具体的に数値例がある場合はできると思うのですが．

基本的な話かもしれないのですが，お願い致します．

回答No.3

stomachman

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の全ての値を丁度１度ずつ取ります。
（仮に、uが0～y-1の値のうちのどれかを取らないとするならば、
rを1～yまで変えたとき、uの値として0～y-1のうち少なくとも一つの数vが２度以上現れたことになります。つまり、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}は簡単に分かります。

かくて、１～ｎの内で、{k| ∃m(m∈N ∧ kx+1 = my)}の要素が幾つあるかを計算するのはもう、簡単な問題ですね。

★modの説明が必要かな？ a mod b = a-[a/b]b です。ここに[x]は「xを越えない最大の整数」のことです。従って、0≦a mod b＜b。

回答No.2

pancho

「Ｎ１とＮ２が互いに素である」という前提を置くと、
［１　～　Ｎ１＊Ｎ２］間にＮ１とＮ２の公倍数が１つのみ（Ｎ１＊Ｎ２）存在します。
同様に（証明は省きますが）、
［２　～　Ｎ１＊Ｎ２］間に　（Ｎ１の倍数＋１）とＮ２の倍数で共通なものが１つのみ存在します。
このことより、ｎ＝ｍ（Ｎ１＊Ｎ２）＋１＋ｌ［ｍ、ｌは自然数］とすると、ｍ個の共通倍数（？）が存在することになります。

次に、Ｎ１とＮ２が互いに素ではない場合、Ｎ１とＮ２の最大公約数をａとすれば、［２　～　ａ＋１］間に共通倍数（？）が何個あるか考えれば、同じ方法がとれます。
ここからは、ここのケースに依って分かれてくるでしょう。例えば、Ｎ１とＮ２がともに偶数の場合、解はありません。（共通する数は無い）

私にわかるのはここまでです。

以上。

回答No.1

starflora

まず、第一の問題は、「アルゴリズム的」には解けるのです。
　　どういう風に解けるかと言いますと、

　　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 の倍数であれば、ｎを、k×N1+1 で割って、小さい方の近似自然数を出せば、それがこたえでしょう。そうでない場合は、また別の条件次第で答えが変わって来ます。

　　それとも、第一の問題の解が、例えばｍとすると、第二の答えは、このｍを使って表現でき、それはどうなるかという問いなのでしょうか？　（何を尋ねておられるのか、非常に曖昧です）。