資料の配布

第07回の Q & A

RDE でのプリント

講義の本筋とは関係ありませんが、参考までに。

1. File -> Print で "Printer Property" ウインドウを開く。
2. Preview(W) で印刷イメージを確認する。
3. Print(P) で実際に印刷。
4. 必要に応じて "Printer setting(R)" で出力するプリンタの指定をおこなうこと。

ユークリッド(Euclide)の互除法(続)

自然数(整数でもよいのですが) a, b に対して

• どちらの約数にもなっている最大の自然数を 最大公約数 gcd (greatest common divisor)
• どちらの倍数にもなっている最小の自然数を 最小公倍数 lcm (least common multiple)

a と b の最大公約数 = max { k | k は a を割り切る かつ k は b を割り切る }
a と b の最小公倍数 = min { k | a は k を割り切る かつ b は k を割り切る かつ k > 0 }

※ a,b のどちらかが 0 のときは gcd(a,0)=a, lcm(a,0)=0 と定義するのが便利なようです。

問22: 最大公約数を計算する関数 gcd(a,b) を定義してみましょう。

...              # 必要に応じて補助関数を定義してもよい(以後とくに明記しない)

def gcd(a,b)
  ....           # ここを考える
  return c       # c は a,b の最大公約数
end

a = 1234567
b = 7654321
printf("gcd(%d,%d)=%d\n", a, b, gcd(a,b))

gcd(a,0) = a  ... (1)

• k が a, b を割り切る -> k は r も割り切る
• k が b, r を割り切る -> k は a = nb+r も割り切る

{ k | k は a を割り切る かつ k は b を割り切る } = { k | k は b を割り切る かつ k は r を割り切る }

gcd(a,b) = gcd(b, a%b)  ... (2)

b > 0 ならば a%b < b であるから (2) 式を適用して a,b の値を小さくしていけば
最終的には (1) に帰着する。

上記にしたがって作ったプログラムは以下のとおり。

def gcd1(a,b)
  if b == 0
    c = a
  else
    c = gcd1(b, a%b)
  end
  return c           # 変数 c を使わずに直接 return してもよい
end

def gcd2(a,b)
  while b > 0
    # a, b <- b, a%b
    t = a
    a = b
    b = t % b
  end
  return a
end

a = 1234567
b = 7654321
printf("gcd1(%d,%d)=%d\n", a, b, gcd1(a,b))
printf("gcd2(%d,%d)=%d\n", a, b, gcd2(a,b))

演習:

gcd(3,5) = ?
gcd(6,21) = ?
gcd(15,21) = ?
gcd(14,22) = ?
gcd(30,56) = ?
gcd(49,91) = ?
gcd(8,40) = ?
gcd(208,117) = ?
gcd(12707,12319) = ?

def gcd(a,b)
  if b == 0
    return a
  else
    return gcd(b, a%b)
  end
end

for i in [[3,5], [6,21], [15,21], [14,22], [30,56], [49,91],
         [8,40], [208,117], [12707, 12319]] do
  a=i[0]
  b=i[1]
  printf("gcd(%d,%d)=%d\n", a, b, gcd(a,b))
end

問23: 最小公倍数を計算する関数 lcm(a,b) を定義してみましょう。

def lcm(a,b)
  ....           # ここを考える
  return c       # c は a,b の最小公倍数
end

a = 1234567
b = 7654321
printf("lcm(%d,%d)=%d\n", a, b, lcm(a,b))

G = gcd(a,b)
L = lcm(a,b)

とおくと、適当な互いに素である正数 X,Y を用いて

a = X*G
b = Y*G

と書ける。このとき a*b/G = X*Y*G は a と b 両方の倍数なので
最小公倍数 L の倍数になっている。そこで適当な正数 U,V を用いて

L = U*a = U*X*G
L = V*b = V*Y*G

すなわち

U*X = V*Y

が成立する。ここで X と Y は互いに素なので U は Y の倍数、V は X の倍数で
ある。もし U > Y ならば L = U*X*G > Y*X*G = X*Y*G となり最小公倍数Lより小
さな X*Y*G が a と b の公倍数であることになり矛盾。V > X と仮定しても同様
である。
したがって V=X かつ U=Y となるので L = U*a = Y*X*G 、すなわち a と b の最小
公倍数 L は a*b/G に等しい。

式を整理すると gcd(a,b) * lcm(a,b) = a*b となる。

※ 素因数分解の一意性を使うともっと簡単に証明できます。

上記にしたがって作ったプログラムは以下のとおり。

def gcd(a,b)
  if b == 0
    return a
  else
    return gcd(b, a%b)
  end
end

def lcm(a,b)
  return a * b / gcd(a,b)
end

a = 1234567
b = 7654321
printf("lcm(%d,%d)=%d\n", a, b, lcm(a,b))

演習:

lcm(3,5) = ?
lcm(6,21) = ?
lcm(15,21) = ?
lcm(14,22) = ?
lcm(30,56) = ?
lcm(49,91) = ?
lcm(8,40) = ?
lcm(208,117) = ?
lcm(12707,12319) = ?

def gcd(a,b)
  if b == 0
    return a
  else
    return gcd(b, a%b)
  end
end

def lcm(a,b)
  return a * b / gcd(a,b)
end

for i in [[3,5], [6,21], [15,21], [14,22], [30,56], [49,91],
         [8,40], [208,117], [12707, 12319]] do
  a=i[0]
  b=i[1]
  printf("lcm(%d,%d)=%d\n", a, b, lcm(a,b))
end

問24(多少修正): 整数 a, b に対して m a + n b = gcd(a,b) となる m,n が必ず存在します。 この m,n と c=gcd(a,b) を計算する関数 egcd を定義してみましょう。

b = 0 であれば gcd(a,b) = a なので m = 1, n = 0, c=a とすればよい(*)。

さて b > 0 に対して b * m2 + (a%b) * n2 = gcd(b,a%b) となる整数 m2, n2 が存在したとすると

gcd(a,b) = gcd(b,a%b)

b * m2 + (a%b) * n2 = gcd(a,b) ... (1)

a = (a/b)*b + (a%b)

b * m2 + (a - (a/b)*b) * n2 = gcd(a,b)
a * n2 + (m2 - (a/b)*n2) * b = gcd(a,b)

m = n2
n = m2 - (a/b)*n2
gcd(a,b) = c

さらにこのような a*m' + b*n' = gcd(a,b) となる (m', n) の対は m, n と任意の 整数 k を用いて

m' = m + k*b
n' = n - k*a

a*m  + b*n  = gcd(a,b)
a*m' + b*n' = gcd(a,b)

def egcd(a,b)
  if b==0
    return [1,0,a]    # a*m+b*n = a*0+0*0 = a = gcd(a,0)
  else
    v  = egcd(b,a%b)
    m2 = v[0]         # m2,n2,c に v[0], v[2], v[2] を
    n2 = v[1]         # わざわざ代入しなくてもよい
    c = v[2]          # ここでは説明の都合上そうしているだけ
    m = n2
    n = m2 - (a/b)*n2
    return [m,n,c]    # a*m+b*n=c=gcd(a,b) となっている
  end
end

a = 1234567
b = 7654321
v = egcd(a,b)
m = v[0]         
n = v[1]
c = v[2]
check = a*m+b*n-c   # 0 になるはず
printf("%d*(%d)+%d*(%d)=%d | %d\n", a, m, b, n, c, check)

演習:

egcd(3,5) = ?
egcd(6,21) = ?
egcd(15,21) = ?
egcd(14,22) = ?
egcd(30,56) = ?
egcd(49,91) = ?
egcd(8,40) = ?
egcd(208,117) = ?
egcd(12707,12319) = ?

def egcd(a,b)
  if b==0
    return [1,0,a]    # a*m+b*n = a*0+0*0 = a = gcd(a,0)
  else
    v  = egcd(b,a%b)
    m2 = v[0]         # m2,n2,c に v[0], v[2], v[2] を
    n2 = v[1]         # わざわざ代入しなくてもよい
    c = v[2]          # ここでは説明の都合上そうしているだけ
    m = n2
    n = m2 - (a/b)*n2
    return [m,n,c]    # a*m+b*n=c=gcd(a,b) となっている
  end
end

for i in [[3,5], [6,21], [15,21], [14,22], [30,56], [49,91],
         [8,40], [208,117], [12707, 12319]] do
  a = i[0]
  b = i[1]
  v = egcd(a,b)
  m = v[0]         
  n = v[1]
  c = v[2]
  check = a*m+b*n-c   # 0 になるはず
  printf("%d*(%d)+%d*(%d)=%d | %d\n", a, m, b, n, c, check)
end

問25(発展課題): 問24 では関数 egcd の定義内で再帰的に egcd を呼び出して いますが、これを非再帰的に変更できるでしょうか。

問26(応用): 互いに素な自然数 a, b が与えられたときに a*x % b = 1 となる x を(1個)求めるプログラムを作ってみましょう。

def egcd(a,b)
  if b==0
    return [1,0,a]    # a*m+b*n = a*0+0*0 = a = gcd(a,0)
  else
    v  = egcd(b,a%b)
    m2 = v[0]         # m2,n2,c に v[0], v[2], v[2] を
    n2 = v[1]         # わざわざ代入しなくてもよい
    c = v[2]          # ここでは説明の都合上そうしているだけ
    m = n2
    n = m2 - (a/b)*n2
    return [m,n,c]    # a*m+b*n=c=gcd(a,b) となっている
  end
end

a = gets.to_i
b = gets.to_i
v = egcd(a,b)
if v[2] != 1   # gcd(a,b) != 1 である
  printf("%d と %d は互いに素ではありません。\n", a, b)
else
  printf("%d * x %% %d = 1 の解は %d です。\n", a, b, v[0])
end

冬季レポートについて