OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
締切り
済み

数列2(基本的な質問かもしれませんが)

  • すぐに回答を!
  • 質問No.186042
  • 閲覧数39
  • ありがとう数1
  • 気になる数0
  • 回答数3
  • コメント数0

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

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

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

基本的な話かもしれないのですが,お願い致します.
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全3件)

  • 回答No.1
レベル13

ベストアンサー率 61% (647/1050)

    まず、第一の問題は、「アルゴリズム的」には解けるのです。   どういう風に解けるかと言いますと、     N1とN2が、素な関係にある時(つまり、N1, N2 が、仮に公約数があっても、その公約数の素数が、互いに共通性がない場合)、一般的な解は、N1^a*N2^b<=n を満たす、a, b の組み合わせの数を求めることになります(a,b は自然数)。しかし、これは、n, N1, N2 ...続きを読む
 
  まず、第一の問題は、「アルゴリズム的」には解けるのです。
  どういう風に解けるかと言いますと、
 
  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を使って表現でき、それはどうなるかという問いなのでしょうか? (何を尋ねておられるのか、非常に曖昧です)。
 

  • 回答No.2
レベル12

ベストアンサー率 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とN ...続きを読む
「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がともに偶数の場合、解はありません。(共通する数は無い)

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

以上。
  • 回答No.3
レベル14

ベストアンサー率 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 ...続きを読む
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。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ