香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学１ 第1-1章 除法定理と整除演算 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 数の集合と四則演算の表記 ■ 整数化記号 ■ 除法定理と整除演算 ■ 様々な剰余と整商 ■ 整除演算の応用とデータ表現 概 要 ■ 数の集合と四則演算の表記 自然数・整数・有理数・実数 加減乗除 和差積商 ■ 整数化記号 切捨 切上 四捨五入 ガウス記号 ■ 除法定理と整除演算 除法等式 剰余条件 整商と剰余 ■ 様々な剰余と整商 正剰余 負剰余 切捨整商 切上整商 最小剰余 ■ 整除演算の応用とデータ表現

第01節 [1] 数の集合の表記 整数 [integer] Ｚ 正負 離散 自然数 [natural number] Ｎ 0および正整数 離散 有理数 [rational number] Ｑ 整数の比 稠密 実数 [real number] Ｒ 数直線上の数 連続 複素数 [complex number] Ｃ 実部と虚部 連続 正の数 Ｘ+ Ｎ+ Ｚ+ Ｑ+ Ｒ+ 0でない数 Ｘ* Ｚ* Ｑ* Ｒ* Ｃ* ・ 情報科学では、自然数 Ｎ に 0 を含める ・ Ｎ+ と Ｚ+ は同じ集合 ・ 整数 Ｚ はドイツ語の数 Zahl から ・ 有理数 Ｑ は英語の商 Quotient から ・ 稠密とは隙間(区間の穴)がないこと、連続とは1点の穴もないこと

第01節 [2] 四則演算の表記 演算 数学 計算機 演算結果 加法 [addition] Ａ＋Ｂ a + b 和 [sum] 演算 数学 計算機 演算結果 加法 [addition] Ａ＋Ｂ a + b 和 [sum] 減法 [subtraction] Ａ－Ｂ a - b 差 [difference] 乗法 [multiplication] Ａ×Ｂ a * b 積 [product] 除法 [division] Ａ÷Ｂ a / b 商 [quotient] 累乗 [power] Ａ↑Ｂ a ^ b 剰余 [reminder] Ａ％Ｂ a % b 実商 実数の除法としての結果の実数 整商 整数の除法としての結果の整数 (実商の切捨) ・ 累乗は、標準的な記法がない ・ 通常の整商は、実商の切捨整数 実商 17÷5＝3.4 整商 17÷5＝3

第02節 [1] 整数化記号 切捨 floor(x) x以下の最大の整数 n ≦ x ＜ n+1 切上 ceil(x) x以上の最小の整数 四捨五入 round(x) xに最も近い整数 n ≦ x+0.5 ＜ n+1 ・ 負数に対する整数化は、間違えやすいので注意する [-3.2] ＝ -3 [-3.6] ＝ -4 ・ 整数化記号は、ガウス記号ともいう ・ プログラム言語では、ライブラリ関数として用意されている ・ C言語には、round(x) がないので、floor(x+0.5) で求める ・ 100の位での切捨(345→300)は、[x/100]*100 とする

第03節 [1] 割り算の意味と計算方法 割り算 17 ÷ 5 ＝ 3 ‥ 2 17 割る 5 は 3 余り 2 割り算 17 ÷ 5 ＝ 3 ‥ 2 17 割る 5 は 3 余り 2 右辺に2つの値が並べられている 本当の意味での等式ではない (簡略表記) 意味 17 に 5 の塊が何個あるか、残りは何個か 計算 17から5をできるだけ引いていく 引けなくなるまで(負にならない間)の回数を数える 17 － 5 ＝ 12 1回 12 － 5 ＝ 7 2回 7 － 5 ＝ 2 3回 2 － 5 ＝ × 3回引けて、残りは2 17 ÷ 5 ＝ 3 ‥ 2 17 ＝ 5 × □ ＋ □ 穴埋め等式 1 12 2 7 3 2 割り算の答え 4 -3

第03節 [2] 除法定理 ● 除法定理 任意の整数 a と正整数 b に対し 除法等式 a ＝ b × q ＋ r 剰余条件 0 ≦ r ＜ b を満たす整数 q, r が 一意に存在する 穴埋め等式 a ＝ b × □ ＋ □ に入る値は 幾つも考えられる 1組に特定するには 何か条件が必要である ・ 除法定理は、整除演算の原理である ・ 証明は、数学的帰納法による ・ 整数に関する多くの性質は、除法定理から導かれる ・ 除法等式は、題意の立式や式変形において、頻出である ・ 剰余条件を変えると、様々な剰余を考えることができる

第03節 [3] 整除演算 ● 整除演算 ● 整除演算のプログラム a ÷ b ＝ q ‥ r 被除数 a 除数 b b＞0 整商 q 剰余 r 0≦r＜b ● 整除演算のプログラム 入力 a, b r = a; // 剰余の初期化 q = 0; // 整商の初期化 // 反復前の前提 q＝0 r≧0 b＞0 while ( r >= b ) { // 引ける間 r = r - b; // 減算 q++; // 計数 // 反復内で不変 a＝q×b＋r } // 反復後に成立 q≧0 0≦r＜b 出力 q, r 剰余は 0,1,‥, b-1 の b 通り ● 整除演算の記号 整商 q ＝ a @ b 剰余 r ＝ a % b

第05節 [1] 整商と剰余の性質 除法等式 a ＝ b × (a@b) ＋ (a%b) 整除等式 (a － (a%b)) ÷ b ＝ a@b 和の剰余 (a＋b) % c ＝ ( (a%c)＋(b%c) ) % c 積の剰余 (a×b) % c ＝ ( (a%c)×(b%c) ) % c 二重整商 n @ (p×q) ＝ (n@p) @ q 剰余 10000 % 91 ＝ ？ 10000 ＝ 100×100 を利用 100 % 91 ＝ 9 より 積の剰余から 与式 ＝ (9×9) % 91 ＝ 81 整商 10000 @ 91 ＝ ？ 91 ＝ 7×13 を利用 10000 @ 7 ＝ 1428 より 二重整商から 与式 ＝ 1428 @ 13 ＝ 109

第06節 [1] 正剰余と負剰余 除法等式 a ＝ b × q ＋ r q 仮商 r 残余 剰余条件 整商 剰余条件 整商 正剰余 0≦r＜b 切捨 +17 ÷ 5 ＝ +3 ‥ +2 -17 ÷ 5 ＝ -4 ‥ +3 負剰余 -b＜r≦0 切上 +17 ÷ 5 ＝ +4 ‥ -3 -17 ÷ 5 ＝ -3 ‥ -2 +17 ＝ 5 × □ ＋ □ +3 ← 正 +2 +4 ← 負 -3 -17 ＝ 5 × □ ＋ □ -4 ← 正 +3 -3 ← 負 -2 ・ 除法等式を立て、先に剰余を考える ・ 除数が負数の場合、正負の剰余と切捨・切上の整商との関係が逆になる

第06節 [2] 整商と剰余の関係 除法等式を立てて、 整商と剰余を求める 元数 除数 整商 剰余 除法等式 切捨 切上 正 負 切捨整商 と 正剰余 切上整商 と 負剰余 +13 +6 +2 +3 +1 -5 +13 ＝ (+6)×(+2)＋(+1) +13 ＝ (+6)×(+3)＋(-5) -13 -13 ＝ (+6)×( )＋( ) 切捨整商 と 負剰余 切上整商 と 正剰余 -6 +13 ＝ (-6)×( )＋( ) -13 ＝ (-6)×( )＋( ) 除法等式を立てて、 整商と剰余を求める

第07節 [1] 最小剰余 剰余条件 整商 最小剰余 -b/2 ≦r＜ +b/2 四捨五入 剰余の範囲 除数3 (奇数) 除数4 (偶数) 剰余条件 整商 最小剰余 -b/2 ≦r＜ +b/2 四捨五入 剰余の範囲 除数3 (奇数) 除数4 (偶数) 正剰余 0, +1, +2 0, +1, +2, +3 負剰余 -2, -1, 0 -3, -2, -1, 0 最小剰余 -1, 0, +1 -2, -1, 0, +1 10 5 14 ０ 11 9 -１ +１ 6 -２ +２ 8 7 13 12 8 4 ０ 11 7 -１ +１ 5 9 -２ 6 10

第08節 [1] 整除演算の応用 下2桁が99で、21で割り切れる最小の自然数を求めよ。 自然数をNとし、その上位桁をMとすると、 N ＝ [ 100 ] × M ＋ [ 99 ] と表される。 また、Nを21で割った整商をQとする。除法等式より N ＝ [ 21 ] ×Q と表される。 ここで、Q＝Q0 の各桁を下位から求めていく。 整理して、 [ 100 ] × M ＝ [ 21 ] × Q0 ＋ [ -99 ] ‥ ① を得る。 Q0の下1桁を V1、上位桁をQ1 とし、Q0 ＝ 10×Q1＋ V1 とおく。 ①の右辺は10で割り切れるから V1＝[ 9 ] となる (0～9を当てはめてみる)。 ①に代入して、 100×M ＝ 21×(10×Q1＋9)－99＝210×Q1＋90 となり、 10で割って、 10×M ＝ [ 21 ] × Q1＋ [ 9 ] ‥ ② を得る。 Q1の下1桁を V2、上位桁をQ2 とし、 Q1 ＝ 10×Q2＋ V2 とおく。 ②の右辺は10で割り切れるから V2＝[ 1 ] となる (0～9を当てはめてみる)。 ②に代入して、 10×M = 21×(10×Q2＋1)＋9＝210×Q2＋30 となり、 10で割って、 M ＝ [ 21 ] × Q2 ＋ [ 3 ] ‥ ③ を得る。 Q2＝0 のとき、M＝3 で、③は満たされる。 よって、 N＝ 100 × [ 3 ] ＋ 99 ＝ [ 399 ] を得る。 また、Qの各桁は、上位から 0,1,9 であり、Q＝[ 19 ] となる。 このとき、 399＝21×19 で題意を満たしている。

第08節 [2] トランプカードの識別番号 列数 b で、q 行 r 列の位置の数 a a＝b×q＋r q＝a@b, r＝a%b 3 4 5 6 7 8 9 T J Q K S 1 10 11 12 H 13 14 15 16 17 18 19 20 21 22 23 24 25 D 26 27 28 29 30 31 32 33 34 35 36 37 38 C 39 40 41 42 43 44 45 46 47 48 49 50 51 トランプ52枚は、 0～51の52個の自然数で表現 13による整除演算で1対1 整商が種類、剰余が数位 33 ÷ 13 ＝ 2 ‥ 7 ⇒ D8 H5 ⇒ 1 × 13 ＋ 4 ＝ 17 列数 b で、q 行 r 列の位置の数 a a＝b×q＋r q＝a@b, r＝a%b