\( \DeclareMathOperator{\abs}{abs} \newcommand{\ensuremath}[1]{\mbox{$#1$}} \)

整数の性質(Number Thorem)

1 約数と倍数

 1.1 約数と倍数

整数 integral number,integer アンタッチャブル:完全という意味あり、整数と積分は完全なのだ。
正の整数 positive ラテン語「(協定で)決まった」の意から
自然数 数の世界はここからスタート
負の整数 negative 「否定する」まさに否定された数
 たまに,負の数と負の数を掛けるとどうして正になるのか,と質問する生徒がいる。
 証明を聞きたいんじゃなくて,自分なりに納得したいんだよなきっと。
割り切れる divisible (divide ラテン語「分離する」の意から)
約数 divisor,factor(ラテン語「作る[なす]人」の意から)
倍数 multiple( multi-「多くの…」)

新教育課程の整数論は,私の「再読 高木貞治」の「初頭整数論講義」(*)の簡易版という感じだ。
Maxima でおっていこうか。

すべての約数を見るのは divisors()
すべての約数の和は divsum()
だから 約数の個数は cardinate(divisors())

倍数の見分け方がある
もちろん,7はない。知りたい人は*をどうぞ。

素数 prime ラテン語「第一の」の意から
合成数 composition 古期フランス語「共に置く」の意から_
因数 factor
素因数
素因数分解 factorization

素因数分解は factor()
素数とその指数を見る ifactors()

(%i1) divisors(28);
\[(\%o1) {1,2,4,7,14,28}\]
(%i2) cardinality(divisors(28));
\[(\%o2) 6\]
(%i3) divsum(28);
\[(\%o3) 56\]
(%i4) factor(28);
\[(\%o4) {{2}^{2}}7\]
(%i5) ifactors(28);
\[(\%o5) [[2,2],[7,1]]\]

この応用として2元2次不定方程式がある。
$$問1 ab+3a+2b=1 をみたす整数の組 (a,b) を求めよ。$$
2元2次方程式を解くプログラムを一応作ったがこれじゃあなあ,まあ,もっと研究しよう。

(%i6) for a:-50 thru 50 do
for b:-50 thru 50 do
if a*b+3*a+2*b=1 then print("(",a,",",b,")")$
\[( -9 , -4 ) ( -3 , -10 ) ( -1 , 4 ) ( 5 , -2 ) \]

 1.2 最大公約数と最小公倍数

最大公約数 great common divisor(measure)
最小公倍数 least common multiple
互いに素 co-prime
2数の関係 ab=gl があり,これを使った問題がある。

最大公約数は gcd(a,b),最小公倍数は lcm(a,b)

(%i8) gcd(12,45);lcm(12,45);
\[(\%o7) 3\] \[(\%o8) 180\]

問2 最大公約数が15,最小公倍数が180である2つの自然数の組をすべて求めよ。
いろいろ考えるより調べてしまえというマクロ

(%i9) glc(g,l):=block(
   for i:g thru l do
   for j:i thru l do
   if gcd(i,j)=g and lcm(i,j)=l then print("(",i,",",j,")")
)$
(%i10) glc(15,180)$
\[( 15 , 180 ) ( 45 , 60 ) \]

 1.3 整数の割り算と商および余り

商 quotient
余り remainder

割り算の商は floor(a/b)床関数 あるいは quotient(a,b)
 a/bが負に注意
余りは mod(a,b)
両方一気に出すのは divide(a,b)ただし,下のように注意が必要

(%i11) floor(-29/7);
\[(\%o11) -5\]
(%i12) quotient(-29,7);
\[(\%o12) -4\]
(%i13) mod(-29,7);
\[(\%o13) 6\]
(%i14) divide(-29,7);
\[(\%o14) [-4,-1]\]
(%i15) divide(29,7);
\[(\%o15) [4,1]\]

剰余類 residue class
 整数を余りで分類する方法
合同の記号は教科書では発展にある。

すべての自然数の平方は4で割った余りが0か1を実験

(%i16) l:[0,1,2,3]$
(%i17) mod(l^2,4);
\[(\%o17) [0,1,0,1]\]

n(n+1)(2n+1) は6の倍数であることの実験

(%i18) l:[0,1,2,3,4,5]$
(%i19) mod(l*(l+1)*(2*l+1),6);
\[(\%o19) [0,0,0,0,0,0]\]

2 ユークリッドの互除法

 2.1 ユークリッドの互除法

ユークリッドの互除法で最大公約数を求める。
ユークリッドの互除法は昔の書き方があるが,教科書はそれを採用していない。
この方法の書き方を提言する。
図1がいいと思うが,図2が昔の書き方

図 1:
Diagram

図 2:
Diagram

 2.2 1次不定方程式

そして2元1次方程式(ディオファンタス方程式)
特殊解を見つけて一般解にするというもの,特殊解が見つけずらいものは互除法を使うという流れだ。
図形的な意味もある,詳しくは*。
ディオファンタス方程式を解くには,ユークリッドの互除法を使う方法と,合同式を使う方法と,連分数を使う方法がある。詳しくは*。
上は合同法を使った解法,下は連分数を使った解法,連分法のほうがいいのかな。

(%i20) dio(a,b):=block(
x:inv_mod(a,b),
y:(1-a*x)/b,
return([x,y])
)$
(%i21) dio(163,78);
\[(\%o21) [67,-140]\]
(%i22) diof(a,b):=block(
r:radcan(cfdisrep(delete(last(cf(a/b)),cf(a/b)))),
return([-denom(r),num(r)])
)$
(%i23) diof(163,78);
\[(\%o23) [-11,23]\]

3 整数の性質の活用

 3.1 n進法

p進法 notation

これも,部分分数分解などの応用があり,詳しくは*
Maximaには ibase(input base) とobase(output base)なる変数がある。
もちろんデフォルトは10。
ただし整数のみ,しかも環境変数みたいなもので直さないといけない。

(%i24) ibase:2$
(%i25) 10101;
\[(\%o25) 21\]
(%i26) ibase:1010$
(%i27) obase:2$
(%i11100) 67;
\[(\%o11100) 1000011\]
(%i11101) obase:10$

以下ぎこちないが,p進法に直す,p進表示を十進法に直すマクロ。

(%i30) nota(a,p):=block(
l:[ ],
for i:1 while i<100 do
(
l:append([mod(a,p)],l),
a:floor(a/p),
if a=0 then return(l)
)
)$
(%i31) nota(23,3);
\[(\%o31) [2,1,2]\]
(%i32) nota10(l,p):=block(
s:0,
(
for i:0 thru length(l)-1 do
s:s+l[length(l)-i]*p^i
),
return(s)
)$
(%i33) nota10([2,1,2],3);
\[(\%o33) 23\]

小数入りのマクロ
 2進数で1.111だったら,nota11([1,2,1,1,1],2)と入力。
10進小数をp進法に直すのは,すぐ無限になりそうなのでやめとこ。

(%i34) nota11(l,p):=block(
s:0,
(
for i:1 thru length(l) do
if l[i]=p then k:i
),
(
for i:1 thru k-1 do
s:s+l[i]*p^(k-i-1)
),
(
for i:k+1 thru length(l) do
s:s+l[i]*p^(-i+k)
),
return(float(s))
)$
(%i35) nota11([1,2,1,1,1],2);
\[(\%o35) 1.875\]

 3.2 分数と小数

循環小数 recurring decimal
 循環といえばFermatの小定理,オイラーの定理までやりたいところだが。
 連分数まで入試問題には出ていたりする。
*を参照していただければ。
循環小数を分数に直すマクロです。
例えば 0.1272727...ならば

(%i36) recurde(a,b):=block(
r:-floor((log(b))/(log(10))+1),
return(a*b/(1-10^r)/10^(-r-1))
)$
(%i37) 1/10+recurde(1/100,27);
\[(\%o37) \frac{7}{55}\]
Created with wxMaxima. inserted by FC2 system