1からnまでの整数のうち,
N1の倍数 でもあり N2の倍数でもある数がいくつあるかは求められます.(ユークリッドの互除法などによって)

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

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

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

A 回答 (3件)

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。
    • good
    • 0

「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がともに偶数の場合、解はありません。(共通する数は無い)

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

以上。
    • good
    • 0

 


  まず、第一の問題は、「アルゴリズム的」には解けるのです。
  どういう風に解けるかと言いますと、
 
  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を使って表現でき、それはどうなるかという問いなのでしょうか? (何を尋ねておられるのか、非常に曖昧です)。
 
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング

おすすめ情報