ユークリッドの互除法
割り算と最大公約数
自然数 $a$，$b$ について，$a$ を $b$ で割ったときの余りを $r$ とすると，$a$ と $b$ の最大公約数は，$b$ と $r$ の最大公約数に等しい。
ユークリッドの互除法
整数 $a$，$b$ の最大公約数を求めるには，次の手順を繰り返せば良い。この方法をユークリッドの互除法，または，単に互除法という。
- $a$ を $b$ で割ったときの余りを $r$ とする。
- $r=0$ ならば，$b$ が $a$ と $b$ の最大公約数である。
$r>0$ ならば，$a$ を $b$ で，$b$ を $r$ でおきかえて，1に戻る。
この手順を繰り返すと，余り $r$ が小さくなり，$r$ が0になって必ず終了する。
1次不定方程式
【定理】
互いに素である整数の性質
2つの整数 $a$，$b$ が互いに素であるとき，整数 $c$ について $ax+by=c$ を満たす整数 $x$，$y$ が存在する。
【定義】
$a$，$b$，$c$ は整数の定数で，$a \neq 0$，$b \neq 0$ とする。$x$，$y$ の1次方程式 $ax+by=c$ を成り立たせる整数 $x$，$y$ の組を，この方程式の整数解という。この方程式の整数解を求めることを，1次不定方程式を解くという。
※2つの整数 $a$，$b$ が互いに素であるとき，方程式 $ax+by=c$ の整数解の1つを $x=p$，$y=q$ とすると，全ての整数解は $x=bk+p$，$y=-ak+q$ ( $k$ は整数) と表される。
分数と小数
【定義】
有限小数：小数第何位かで終わる小数
無限小数：小数部分が無限に続く小数
循環小数：無限小数のうち，ある位以下では数字の同じ並びが繰り返される小数
既約分数：分母と分子が整数で，分母と分子が互いに素である分数
※ $m$ を整数，$n$ を自然数とすると，分数 $\frac{m}{n}$ は整数，有限小数，循環小数のいずれかで表される。
※整数でない既約分数 $\frac{m}{n}$ について次のことが成り立つ。
分母 $n$ の素因数は2，5だけからなる $\Leftrightarrow$ $\frac{m}{n}$ は有限小数で表される
分母 $n$ の素因数に2，5以外のものがある $\Leftrightarrow$ $\frac{m}{n}$ は循環小数で表される
$n$ 進法
【定義】
底：位取りの基礎となる数
$\boldsymbol{n}$ 進法：底を $n$ として数を表す記数法( $n$ は2以上の整数)
$\boldsymbol{n}$ 進数：$n$ 進法で表された数
※$n$ 進数では，その数の右下に${}_{(n)}$ と書く。(10進数は省略する)
※$n$ 進数の各位の数字は0以上 $n-1$ 以下の整数。
$n$ 進法の位
……，$n^3$ の位，$n^2$ の位，$n^1$ の位，$n^0$，$\frac{1}{n^1}$ の位，$\frac{1}{n^2}$ の位，$\frac{1}{n^3}$ の位，……
2進法の四則計算
2進法の四則計算では，次の計算が基本となる。
- 足し算：$0+0=0$，$0+1=1$，$1+0=1$，$1+1=10$
- 引き算：$0-0=0$，$1-0=1$，$1-1=0$，$10-1=1$
- 掛け算：$0 \times 0=0$，$0 \times 1=0$，$1 \times 0=0$，$1 \times 1=1$
2進法の割り算は，10進法の割り算と同様に，掛け算と引き算を組み合わせて行う。