A 回答 (3件)
- 最新から表示
- 回答順に表示
No.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。
No.2
- 回答日時:
「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.1
- 回答日時:
まず、第一の問題は、「アルゴリズム的」には解けるのです。
どういう風に解けるかと言いますと、
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が見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
2の810乗はいくつですか?
-
2024.8.31 00:04にした質問の20...
-
1/x + 2/y + 3/z =1/4 上記の式...
-
複素数平面 第9日目
-
「ベルヌーイ数とローラン展開...
-
4で割った余りが3でないときは...
-
平方完成
-
高校1数学の平行移動の理屈が分...
-
一般角
-
継続率80%が23連する確率
-
ノンアルコール飲料
-
縦、横、高さが3Cmのブロックが...
-
画像の図形において、AB=CDの...
-
質問したい事が2つあります。 ①...
-
曖昧な質問で申し訳ないです。...
-
アポロニウス
-
論理演算の式の導出過程について
-
g(z)=tan(z)/(z-π/2)^(n+1)のロ...
-
図のようにベクトルはOA+ABのよ...
-
3√(6) - 3√(2) < π< 24 - 12√(3...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
数学の問題で、「間に成り立つ...
-
「0 < x ≦ y ≦ zである整数x, y...
-
かんたんで不安
-
「互いに素であるA、B」と 「...
-
[x] は,正の整数xの正の約数の...
-
チャート式数学難問集の整数問...
-
x²+y²≦10を満たす整数x、yの組(...
-
正の数負の数でどうしてものこ...
-
困数分解と 云いたい
-
6-4 高校数学の確率の問題です
-
なぜ解答のf(1)=0やg(1)=0とい...
-
留数 ローラン級数
-
√3が無理数であることを用いて...
-
1≦k≦(2^m)-1を満たす奇数kは、2...
-
a人が1人400円ずつ出して、b円...
-
場合の数
-
青チャート 整数の性質 練習 (3...
-
aを正の定数とするとき、アステ...
-
逆関数を持つための条件につい...
-
ベクトルの存在範囲
おすすめ情報