数学と人間の活動の公式・用語まとめ

整数の除法

\(a=bq+r\quad(0\leq r<b)\)

いつ使う？

整数 \(a\) を正の整数 \(b\) で割った商 \(q\) と余り \(r\) を表します。

短い例

\(23=5\cdot4+3\)

注意

余りは0以上で、割る数より小さくなります。

ユークリッドの互除法

\(\gcd(a,b)=\gcd(b,r)\quad(a=bq+r)\)

いつ使う？

大きな2整数の最大公約数を、余りを繰り返し使って求めます。

短い例

\(48=18\cdot2+12,\ 18=12\cdot1+6\) より \(\gcd(48,18)=6\)

注意

余りが0になったときの、最後の0でない余りが最大公約数です。

最大公約数と最小公倍数

\(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab\quad(a,b>0)\)

いつ使う？

最大公約数または最小公倍数の一方から、もう一方を求めます。

短い例

\(\gcd(12,18)=6\) なので \(\operatorname{lcm}(12,18)=36\)

注意

2つの正の整数に対して使う公式です。

n進法の位取り

\((a_ka_{k-1}\cdots a_0)_n=a_kn^k+a_{k-1}n^{k-1}+\cdots+a_0\)

いつ使う？

\(n\) 進法で表された数を10進法へ直します。

短い例

\((1011)_2=1\cdot2^3+1\cdot2+1=11\)

注意

使える数字は \(0\) から \(n-1\) までです。

合同式

\(a\equiv b\pmod m\iff m\mid(a-b)\)

いつ使う？

2つの整数を \(m\) で割った余りが等しいことを表し、曜日や周期の計算に使います。

短い例

\(17\equiv2\pmod5\)

注意

合同式では、両辺の加法・減法・乗法ができます。除法は常にできるとは限りません。

一次不定方程式

\(ax+by=c\) が整数解をもつ条件は \(\gcd(a,b)\mid c\)

いつ使う？

個数や金額など、整数に限られる条件を満たす組を求めます。

短い例

\(6x+9y=12\) は \(\gcd(6,9)=3\) が12を割り切るので整数解をもつ

注意

整数解を求めた後、問題に応じて正の整数などの条件を確認します。

ハノイの塔の最小手数

\(n\) 枚の円盤を移す最小手数は \(2^n-1\)

いつ使う？

同じ操作を小さい場合へ分ける、再帰的な考え方の例として使います。

短い例

円盤が4枚なら最小手数は \(2^4-1=15\)

注意

上の \(n-1\) 枚を移す操作を2回、最大の円盤を移す操作を1回行います。