香川大学工学部 富永浩之 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とし、その上位桁をN'とすると、 N ＝ [ ] × N' ＋ [ ] と表される。 また、Nを21で割った整商をQとする。除法等式より N ＝ [ ] ×Q と表される。 ここで、Q＝Q0' の各桁を下位から求めていく。 整理して、 [ ] × N' ＝ [ ] × Q0' ＋ [ ] ‥ ① を得る。 Q0'の下1桁を Q1 とすると、①から明らかに Q1＝9 となる。 上位桁 Q1' とすると、 Q0' ＝ [ ] ×Q1'＋ [ ] となる。 ①に代入して、 100×N'＝21×(10×Q1'＋9)－99＝210×Q1'＋90 となり、 10×N' ＝ [ ] × Q1'＋ [ ] ‥ ② を得る。 Q1'の下1桁を Q2 とすると、②から明らかに Q2＝1 となる。 上位桁 Q2' とすると、 Q1' ＝ [ ] ×Q2'＋ [ ] となる。 ②に代入して、 10×N'＝21×(10×Q2'＋1)＋9＝210×Q2'＋30 となり、 N'＝ [ ] × Q2' ＋ [ ] ‥ ③ を得る。 Q2'＝0 のとき、N'＝3 で、③は満たされる。 よって、 N＝ 100 × [ ] ＋ 99 ＝ [ ] を得る。 また、Qの各桁は、上位から 0,1,9 であり、Q＝19 となる。 このとき、 399＝21×19 で題意を満たしている。

列数 b で、q 行 r 列の位置の数 a a＝b×q＋r q＝a@b, r＝a%b 第08節 [2] トランプカードの識別番号 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 33 ÷ 13 ＝ 2 ‥ 7 ⇒ D8 H5 ⇒ 1 × 13 ＋ 4 ＝ 17 列数 b で、q 行 r 列の位置の数 a a＝b×q＋r q＝a@b, r＝a%b