d = gcd(n, m), n > m のとき gcd(3m, n − m) = gcd(3d, n − m)であることの証明
白石 啓一∗

清水 共†

On a proof of gcd(3m, n − m) = gcd(3d, n − m) where d = gcd(n, m), n > m
Keiichi SHIRAISHI

Tomo SHIMIZU

Abstract
The purpose of this study is to prove “gcd(3m, n − m) = gcd(3d, n − m) whered = gcd(n, m), n > m.” The source of this problem is structure of a single-wallcarbon nanotube. The problem is proved using properties of greatest common
divisor. A numerical approach is shown to help students understanding the problem.

Keywords: Single-Wall Carbon Nanotube, Chiral Vector, Translational Vector, Greatest Common Divisor

1

はじめに造のように六方格子として炭素原子が配置した層

現代社会は，高度な情報機器であふれている．携状物質であるグラフェンを円筒状に丸めた立体構

帯電話を筆頭に，パソコンから生活家電製品，産業造) を取り入れた量子効果を過不足なく考慮する必界から身近な個人生活環境に至るまで，ありとあら要がある 1) ．この電子状態の解析において，初等的ゆる分野に電子機器が投入されている．近年の産業な代数学ないし数論を真面目に学んだ者には簡単界を牽引するキーワードは「ナノテクノロジー」でに証明可能である「d = gcd(n, m), n > m のとき

以来，様々な分野で基盤技術として研究・開発が進gcd(3m, n − m) = gcd(3d, n − m)」の関係が利用されるが，CNT 分野の専門書で，この関係の証明が説明されていることは少ない．そこで，CNT 分野められている．特にエレクトロニクスにおいては，を研究する学生の一助として，また初等数学と最先「ナノエレクトロニクス」として盛んに研究・開発

端エレクトロニクスを結びつける一例として，本稿されている．中でも注目される代表的素材の一つとに証明を示す．

して，1991 年に飯島澄男博士が発見した「カーボ2ある．1974 年に谷口紀男教授が，国際生産技術会議において「ナノテクノロジー」の概念を提唱してンナノチューブ (CNT)」があり，原子間力顕微鏡の記法

gcd(a, b)

カンチレバー，電子銃，電界効果トランジスタ等と正 整 数 a, b の 最 大 公 約 数 (GCD)．

gcd(a, b) = gcd(b, a) である．

して将来の技術研究が続けられている．

a | b 正整数 a は，正整数 b を割り切る．つまり，最先端のデバイスとして用いられる CNT の電子状態を解析するためには，CNT の構造 (蜂の巣構b = qa を満たす正整数 q が存在する．
a - b 正整数 a は，正整数 b を割り切れない．つま∗ 香川高等専門学校 詫間キャンパス 通信ネットワーク工学科† 香川高等専門学校 詫間キャンパス 電子システム工学科139

香川高等専門学校研究紀要 2(2011)

3

り，b = qa + r, 0 < r < a を満たす，正整数

基準点 O は六方格子であるグラフェンの格子点にq, r が存在する．

位置して，点 B は点 O から軸方向に延ばした直線が最初に通る格子点として決まる 3) ．

最大公約数の性質
正整数 a, b を考えよう．d0 | a かつ d0 | b を満たす d0 は a, b の公約数である．a = qd0 と表すと，d0 ≤ qd0 = a であるので，a の約数は有限個しか存在しない．したがって，a, b の公約数も有限個しか存在しない．その公約数の中で最大のものを最大公約数という．

d = gcd(a, b), a > b とする．c = a − b を考えると，d は a, b の約数なので，c の約数である．よって，d は b, c の公約数である．d1 = gcd(c, b) とす

図 1 単層ナノチューブ概形 (Fig. 3.11) を参考に作成)

ると，d ≤ d1(1)となる．逆に，d1 は b, c の約数なので，a の約数となる．よって，d1 は a, b の公約数である．d = gcd(a, b)
なので，d1 ≤ d(2)となる．式 (1)，(2) より，d = d1 が得られる．つまり，gcd(a, b) = gcd(c, b) = gcd(a − b, b)(3)である．
式 (3) を繰り返し使うと，

a = qb + r,0≤r<b

図 2 単層ナノチューブ展開図 (Fig. 3.21) を参考に作成, Ch = (4, 2), T = (4, −5))となる q, r が存在し，gcd(a, b)=gcd(a − b, b) = gcd(a − 2b, b)~ で指定できる．OA~ を「カチューブの構造は，OA= ···=イラルベクトル Ch 」と呼ぶ．Ch を六方格子の基gcd(a − qb, b) = gcd(r, b)

本格子ベクトル a1 , a2 を用いて，となる．r = 0 ならば，a = qb なので，gcd(a, b) = b

Ch = na1 + ma2 = (n, m)である．r > 0 ならば，b を a に，r を b に置き直(n, m は整数，0 ≤ |m| < n) と表す．
~ を「並進ベクトル T 」と呼ぶ．T は，OBし，式 (3) を繰り返せば，最大公約数が得られる．
このように最大公約数を求める方法を「ユークリッドの互除法」という 2) ．

4

T = t1 a1 + t2 a2 = (t1 , t2 )単層ナノチューブの概形と問題の定式化と表すことができる．ここで t1 , t2 は互いに素 (最円筒形の層が 1 層のナノチューブを特に単層ナノ大公約数が 1) の整数である．t1 , t2 は，Ch · T = 0チューブと呼ぶ．その円筒部はグラフェンを円筒状より，に巻いた状態にあり，その両端はキャップと呼ばれるフラーレンの半球で閉じている (図 1)．単層ナノt1 =チューブの軸方向に平行な線分 OB と，O, B を含2m + n,dRt2 = −2n + mdRである．ここで，dR は (2m+n) と (2n+m) の最大

み，線分 OB に垂直な (ナノチューブの赤道面に平行な) 面で切り開くと，図 2 が得られる．このとき，140

白石啓一 他 : d=gcd(n, m), n>mのときgcd(3m, n-m)=gcd(3d, n-m)であることの証明

なので，gcd(3m, n − m) = gcd(3d, n − m) で公約数であり，ユークリッド則 (式 (3)) を用いれば，dR=gcd(2m + n, 2n + m)

(4)

=gcd(2m + n, n − m)(5)=gcd(3m, n − m)

(6)=gcd(3d, n − m)(7)である．したがって，{d(3d - (n − m))dR =3d (3d | (n − m))ある．

II. 3d - (n − m)，つまり，3 - (a − b) のとき
式 (9) より，gcd(3m, n − m) =gcd(3bd, (a − b)d)

= dである．また，(8)

gcd(3d, n − m) =である 1) ．

gcd(3d, (a − b)d)

= d

式 (4)∼(6) の式変形は，なので，gcd(3m, n − m) = gcd(3d, n − m) で

2n + m − (2m + n) = n − mある．

2m + n − (n − m) = 3m
より，明らかである．一方，式 (6)∼(7) の式変形，および，式 (8) は，式 (3) のみでは不明瞭である．

I, II より，正整数 n, m について，「d = gcd(n, m),n > m のとき gcd(3m, n − m) = gcd(3d, n − m)」である．

なお，m が負数の場合，最大公約数を求める対象6が負数になることがある．その場合，絶対値を取っ正整数 n, m について，「d = gcd(n, m), n > m のた上で最大公約数を求めれば，十分である．

5

数値実験

とき gcd(3m, n − m) = gcd(3d, n − m)」は，CNT

証明分野において瑣末な問題なので，CNT 分野を学ぶ

正整数 n, m について，「d = gcd(n, m), n > m

者にとって，証明を完全に理解するより，この問題のとき gcd(3m, n − m) = gcd(3d, n − m)」を証明がある程度正しいと分かることが重要であろう．そする．

こで，確認のための数値実験を行った．

式 (3) より，次に示す手続きを踏めば，この問題が正しいことを示すことができる．

d = gcd(n, m) = gcd(n − m, m)である．n = ad, m = bd, gcd(a, b) = 1 を満たす，

2. m = 1, 2, . . . , n − 1 について，3.∼7. を実行する．

正整数 a, b が存在する．gcd(a, b) に対し，式 (3) を使うと，gcd(a, b) = gcd(a − b, b) = 1

1. n = 2, 3, . . . について，2. を実行する．

(9)

3. d = gcd(n, m)
4. d1 = gcd(3m, n − m)がいえる．

I. 3d | (n − m)，つまり，3 | (a − b) のとき
n − m = (a − b)d = 3cd を満たす，正整数 cが存在する．

5. d2 = gcd(3d, n − m)
6. 3d | (n − m) の場合，

式 (9) より，gcd(3c, b) = 1 なので，gcd(b, c) =(a) 3d = d1 = d2 ならば，「OK」と出力する．

gcd(3, b) = 1 である．したがって，gcd(3m, n − m)=(b) そうでなければ，「NG!」と出力し，終了する．

gcd(3bd, 3cd)

= 3d

7. 3d - (n − m) の場合，である．また，(a) d = d1 = d2 ならば，「OK」と出力する．

gcd(3d, n − m) =gcd(3d, 3cd)(b) そうでなければ，「NG!」と出力し，終了する．

= 3d141

香川高等専門学校研究紀要 2(2011)

n, m に関し無限大まで計算し，すべての組み合わ

せで「OK」と表示されれば，この問題が正しいとdef

示したことになるが，そのためには無限の時間が必

cnt()
{

要なので，実験できない (数学的証明は，強力である)．時間の許す限り計算すれば，この問題が，あF = 0;for (N = 2; F == 0; N++)for (M = 1; M < N; M++) {る範囲の n, m について正しいと言える．
数式処理システム Risa/Asir を用いて実験した1 ．
プログラムを図 3 に，実行用シェルスクリプトをD = igcd(N, M);
D1 = igcd(3 * M, N - M);

図 4 に示す．なお，先にも述べたとおり，これは無限に続く処理なので，実験を適切な時間に収め

D2 = igcd(3 * D, N - M);
if (irem((N - M) / D, 3) == 0) {if (3 * D == D1 && D1 == D2)るためにプログラムを停止する必要がある．CPUに Core i7(2.8GHz) を持つパーソナルコンピュータを用いて 29 分 41 秒実験したところ，「n =2, 3, . . . , 21734, m = 1, 2, . . . , n − 1」と「n =MSG = "OK";else {21735, m = 1, 2, . . . , 10936」に関し OK が表示され，この範囲で正しいことが示された．計算ログのMSG = "NG!";F = 1;

一部を図 5 に示す．

7}} else {if (D == D1 && D1 == D2)

おわりに正整数 n, m について，「d = gcd(n, m), n > m の

MSG = "OK";else {MSG = "NG!";

とき gcd(3m, n − m) = gcd(3d, n − m)」を証明し，数値実験を行った．初等数学の問題なので，CNT分野を研究する学生でも証明を理解できると考えら

F = 1;

れる．もし理解できなかったとしても，数値実験を}とおし，題意の理解が進むと考えられる．

}
print(["n=", N, " m=", M," d=gcd(n, m)=", D,今後，本稿を CNT 分野を研究する学生向けの教材として利用し，理解度を確認していきたい．

" gcd(3m, n-m)=", D1," gcd(3d, n-m)=", D2,MSG]);

謝辞
本校 情報工学科 奥山 真吾 准教授から証明に関するアドバイスをいただきました．ここに感謝の意}を表します．

}参考文献end$1) R. Saito, G. Dresselhaus and M. S.
Dresselhaus, Physical Properties of Carbon
Nanotubes, Imperial College Press(1998)

図 3 確認プログラム (ファイル名:cnt.asir)2) 和田 秀男, 計算数学, 朝倉書店 (2000)

#!/bin/sh3) 齋藤 理一郎, 篠原 久典, カーボンナノチュー

LOG=‘date "+%Y%m%d%H%M%S"‘.log
asir 2>&1 > ${LOG} <<EOF
load("./cnt.asir");

ブの基礎と応用, 培風館 (2004)

cnt();
quit;

1 n, m が CPU の整数レジスタに収まる範囲であれば，素の汎用プログラミング言語でも実装できる．ただし，GCD を求める関数を用意する必要がある．著者が Risa/Asir に慣れていた
こと，Risa/Asir が多倍長整数を扱え，GCD を持っていることが，Risa/Asir を利用した理由である．多倍長整数により，時間さえかければ，非常に大きな整数について実験できる．

EOF



図 4 実行用シェルスクリプト142

白石啓一 他 : d=gcd(n, m), n>mのときgcd(3m, n-m)=gcd(3d, n-m)であることの証明

This is Risa/Asir + Interval Arithmetic, Version 20070806 (Plotting GroupDistribution).
Copyright (C) 1994-2000, all rights reserved, FUJITSU LABORATORIES LIMITED.
Copyright 2000-2007, Risa/Asir committers, http://www.openxm.org/.
GC 6.8 Copyright 1988-2005, H-J. Boehm, A. J. Demers, Xerox, SGI, HP.
GP/PARI CALCULATOR Version 2.3.5 (released), Copyright (C) 2000-2005 The PARI Group.
[0] [2] [n=,2, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,3, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,3, m=,2, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,4, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,4, m=,2, d=gcd(n, m)=,2, gcd(3m, n-m)=,2, gcd(3d, n-m)=,2,OK][n=,4, m=,3, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,5, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,5, m=,2, d=gcd(n, m)=,1, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,5, m=,3, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,5, m=,4, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,6, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,6, m=,2, d=gcd(n, m)=,2, gcd(3m, n-m)=,2, gcd(3d, n-m)=,2,OK][n=,6, m=,3, d=gcd(n, m)=,3, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,6, m=,4, d=gcd(n, m)=,2, gcd(3m, n-m)=,2, gcd(3d, n-m)=,2,OK][n=,6, m=,5, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,7, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,7, m=,2, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,7, m=,3, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,7, m=,4, d=gcd(n, m)=,1, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,7, m=,5, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,7, m=,6, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,8, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,8, m=,2, d=gcd(n, m)=,2, gcd(3m, n-m)=,6, gcd(3d, n-m)=,6,OK][n=,8, m=,3, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,8, m=,4, d=gcd(n, m)=,4, gcd(3m, n-m)=,4, gcd(3d, n-m)=,4,OK][n=,8, m=,5, d=gcd(n, m)=,1, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,8, m=,6, d=gcd(n, m)=,2, gcd(3m, n-m)=,2, gcd(3d, n-m)=,2,OK][n=,8, m=,7, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,9, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,9, m=,2, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,9, m=,3, d=gcd(n, m)=,3, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,9, m=,4, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,9, m=,5, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,9, m=,6, d=gcd(n, m)=,3, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK][n=,9, m=,7, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,9, m=,8, d=gcd(n, m)=,1, gcd(3m, n-m)=,1, gcd(3d, n-m)=,1,OK][n=,10, m=,1, d=gcd(n, m)=,1, gcd(3m, n-m)=,3, gcd(3d, n-m)=,3,OK]
図 5 実行ログ (一部)143