Question

んにゃ

x=gcd(m,n)のとき
gcd(10^m-1,10^n-1)=10^x-1
(m,nともに整数)
となる証明方法を教えてください。

9で括るのかなと思ったのですが上手くいかないのでよろしくお願い致します。

Answer 1

✨ คำตอบที่ดีที่สุด ✨

Tak

エレガントではないですが、以下の方針はどうでしょうか。

まず、10^x - 1を公約数に持つことですが、これは以下の式変形からわかります。

10^m - 1 = (10^x - 1)(10^(m-x) + 10^(m-2x) + … + 1)

10^n - 1 も同様にできます。

残りは、10^(m-x) + 10^(m-2x) + … + 1 と 10^(n-x) + 10^(n-2x) + … + 1 が互いに素であることを示せばいいです。

これを示すために、以下の補題により導かれますので、補題の証明に帰着できます。

補題：
pを自然数, m, nをm≧nとなる自然数とし、
A:=p^m + p^(m-1) + … + 1
B:=p^n + p^(n-1) + … + 1
とする。このとき、ある整数Cが存在して、
A = BC + p^r + p^(r-1) + … + 1
を満たす。ただし、rはmをnで割った余りである。
特に、mとnが互いに素ならば、AとBも互い素である。

この補題の前半部分は項数を丁寧に数え上げれば証明できます。
後半部分はユークリッドの互除法を適用すればいいです。

Tak

私が最初に思いついた方法ですので、もっとエレガントにできるような気はします。

んにゃ

丁寧なご回答ありがとうございます。証明の過程が分かり易かったです。

Answer 2

Crystal Clear

mとnの最大公約数は以下のようにユークリッドの互除法で求められる。
r[0]=m
r[1]=n
i≧1のとき、r[i-1]をr[i]で割った余りをr[i+1]とする。
r[i-1]=q[i]r[i]+r[i+1], 0≦r[i+1]<r[i]
これを繰り返すといつかr[N+1]=0となり,
gcd([r[0],r[1])=gcd([r[1],r[2])=...=gcd([r[N],r[N+1])=gcd([r[N],0)=r[N]
となって、最大公約数がr[N]=xと求まる。

f(t)=10^t-1とすると求めたいものは、
gcd(10^m-1,10^n-1)=gcd(f(m),f(n))=gcd(f(r[0]),f(r[1]))
これが上の数列r[n]を用いて以下のように求まる。
gcd([f(r[0]),f(r[1]))=gcd([f(r[1]),f(r[2]))=...=gcd([f(r[N]),f(r[N+1]))=gcd([f(r[N]),f(0))=gcd([f(r[N]),0)=f(r[N])=f(x)=10^x-1

上の変形が成り立つためには

gcd(r[i-1],r[i])=gcd(r[i],r[i+1])⇒gcd(f(r[i-1]),f(r[i]))=gcd(f(r[i]),f(r[i+1]))
を示せばよい。
r[i-1]=q[i]r[i]+r[i+1], 0≦r[i+1]<r[i]だから
f(r[i-1])
=f(q[i]r[i]+r[i+1])
=10^(q[i]r[i]+r[i+1]) -1
=(10^r[i]-1){10^(r[i+1]) (1+10^r[i]+10^(2[ri])+10^(3[ri])+...+10^(q[i]-1)r[i])}+10^[r[i+1]]-1
=f(r[i])Q[i]+f[r[i+1]]
これでf(r[i-1])をf(r[i])で割った余りがf(r[i+1])となるので示せた。

ユークリッドの互除法,gcd

んにゃ

ご回答ありがとうございます。簡潔な解説で考え方を理解することができました。

Answer 3

緑茶

もしかして、x=gcd(m,n)ではなく、x=min(m,n)ではないでしょうか。
例えばm=4, n=6 のとき、x=2ですが、gcd(10^3, 10^5) = 10^3 ですので、x=4でないと辻褄が合いません。

間違えていたらすみません。