1. 概要

本記事では，素数の基礎的な性質について解説します．

$2$ 以上の整数 $p$ のうちで，$1,p$ 以外に約数を持たないものを素数ということはよく知られていると思います．非自明な約数がないというのが素数の定義ですが，「$ab$ が $p$ の倍数ならば $a$ または $b$ は $p$ の倍数である」というのが重要な性質です．この性質から，素因数分解の一意性といった重要な性質が導出されます．この性質や素因数分解の一意性は知名度の高いものだと思いますが，証明をしたことがない人も多いと思うので，講座を通して確認してみてください．

また，有理数に対する合同式についても詳しく扱っています．これは整数論の教科書では初学者向けに扱われることがほとんどないテーマですが，競技プログラミングでは特に確率や期待値などの出力で頻繁に用いられます．

2. 前提知識

AtCoder Algorithm Lectures における次の $2$ 講座の内容を前提とします．

3. 素数の定義と逆元の存在

3.1. 素数の定義

【定義 1】
$2$ 以上の整数 $p$ が $1$ と $p$ 以外の（正の）約数を持たないとき，$p$ は素数（prime）であるという．

素数を昇順に列挙すると，

$$2, 3, 5, 7, 11, 13, 17, 19,\ldots$$

となります．$1$ は素数ではありません．$1$ でも素数でもない正の整数を合成数（composite number）といいます．

3.2. 素数判定

次の問題を考えます．

【問題 2】
正整数 $N$ が与えられます．$N$ が素数であるか否かを判定してください．

$N=1$ のときは，素数ではありません．$N>1$ であるとして，$N$ が合成数であるとすると，$N=ab$ かつ $1<a\leq b$ を満たす正整数 $a,b$ が存在します．すると $N=ab\geq a ^ 2$ より $a \leq \sqrt{N}$ が成り立ちます．$2\leq a\leq \sqrt{N}$ となる範囲の $a$ について，$a$ が $N$ の約数になるかどうかを判定することで，【問題 2】は $\mathrm{O}(\sqrt{N})$ 時間で解くことができます．

おおよそ次のような実装となります．

def is_prime(N):
  if N == 1: return False
  a = 2
  while a * a <= N:
    if N % a == 0: return False
    a += 1
  return True

より高速な素数判定アルゴリズムもあるのですが，本記事では扱いません．

3.3. 乗法逆元の存在

【定理 3】

$p$ を素数とする．整数 $a$ が $p$ の倍数でないならば，$p$ を法とする $a$ の乗法逆元が存在する．

Euclid の互除法【定理 9】より，$\gcd(a,p)=1$ を示せばよいです． $p$ の約数は $1, p$ のみなので $a$ が $p$ の倍数でないことから明らかです． $\blacksquare$

【系 4】

$p$ を素数，$a,b$ を整数とする．$ab$ が $p$ の倍数ならば，$a$ または $b$ は $p$ の倍数である．

$a$ が $p$ の倍数でないとして，$b$ が $p$ の倍数であることを示します．仮定より $ab\equiv 0\pmod{p}$ です．$a$ の $p$ を法とする乗法逆元を $a _ {\mathrm{inv}}$ とすると $b\equiv a _ {\mathrm{inv}}\cdot 0\equiv 0\pmod{p}$ が成り立ちます．したがって $b$ は $p$ の倍数です． $\blacksquare$

3.4. 有限体 $\mathbb{F} _ p$

環 $\mathbb{Z}/n\mathbb{Z}$（合同式の基礎参照）は，$n=p$ が素数であるときには $\mathbb{F} _ p$ とも書きます．つまり $\mathbb{F} _ p$ は集合 $\lbrace 0,1,\ldots,p-1\rbrace$ に対して $\operatorname{mod} p$ での加算・減算・乗算によって演算を定めたものです．

【定理 3】より $a\in \mathbb{F} _ p$ に対して $a\neq 0$ ならば，$ax=1$ を満たす $x\in \mathbb{F} _ p$ が存在します．したがって $a,b\in \mathbb{F} _ p$ に対して $a\neq 0$ ならば，$ax=b$ を満たす $x\in \mathbb{F} _ p$ が唯一存在します．この $x$ を $b/a$ とも書き，$a,b$ に対して $x$ をとる操作を除算（division）といいます．

$\mathbb{F} _ p$ では，加算・減算・乗算・除算が（有理数や実数と同じように）行えることが分かりました．このように除算が行える環（であっていくつかの性質を満たすものは）は，代数学では体（field）と呼ばれます．（詳細は代数構造用語集参照してください．）

$\mathbb{F} _ p$ は体のうちでも要素の個数が有限個であるという特徴を持ち，有限体（finite field）と呼ばれるもののうち最も単純な具体例となります．

4. 素因数分解の一意性

4.1. 素因数分解の一意性の証明

素因数分解の一意性は，「整数論の基本定理」と呼ばれることもある重要な定理です．知名度も非常に高いと思いますが，証明されないまま事実ばかりが知られていることも多いので，ここで証明しておきます．

【定理 5】（素因数分解の一意性）

任意の正整数は素数の積として表すことができる．（ただし $0$ 個の素数の積は $1$ であるとして扱う．）

さらに正整数を素数の積として表す方法は，素数の順序の並べ替えの違いを除いて一意である．つまり $p_1,p_2,\ldots,p_n$ および $q_1,q_2,\ldots,q_m$ が素数であるとき $$p_1p_2\cdots p_n=q_1q_2\cdots q_m$$ ならば，多重集合 $\lbrace p_1,p_2,\ldots,p_n\rbrace$ と $\lbrace q_1,q_2,\ldots,q_m\rbrace$ は等しい．

正整数が素数の積として表せることは簡単です．合成数は自身より小さい $2$ つの正整数の積として表すことができるので，これを反復していけばよいです．

次に $p_1p_2\cdots p_n=q_1q_2\cdots q_m$ が成り立つとします．$n=0$ ならば左辺は $1$ であり，$\lbrace p_1,p_2,\ldots,p_n\rbrace$ と $\lbrace q_1,q_2,\ldots,q_m\rbrace$ はどちらも空集合なのでよいです．$n\geq 1$ であるとします．

このとき左辺は $p_1$ の倍数なので，$q_1q_2\cdots q_m$ も $p_1$ の倍数です．【系 4】を繰り返し使うことで，ある $i$ について $q_i=p_1$ であることが分かります．適当に添字を付け直して $q_1=p_1$ として示せばよく，このとき $p_1=q_1$ かつ $p_2p_3\cdots p_n=q_2q_3\cdots q_m$ となります．

これを反復する（あるいはより形式的には数学的帰納法を使う）ことで，適当に添字を付け直せば $n=m$ かつ $p_1=q_1,p_2=q_2,\ldots$ となることが分かります． $\blacksquare$

4.2. 素因数分解のアルゴリズム

素因数分解を行うアルゴリズムについても考えます．

【問題 6】
正整数 $N$ が与えられます．$N$ を素因数分解してください．

素因数分解を行うには，素因数が存在するならばそのようなものをひとつ見つけ，$N$ を見つけた素因数で割っていけばよいです．$N$ の最小の素因数は，$2$ 以上の約数のうちで最小のものであることに注意すると，約数を探した 3.2 節と同様に，次のように $\sqrt{N}$ 以下の範囲を探索すればよいことが分かります．計算量は $\mathrm{O}(\sqrt{N})$ 時間です．

def prime_factorization(N):
  factors = []
  a = 2
  while a * a <= N:
    if N % a == 0:
      factors.append(a)
      N //= a
    else:
      a += 1
  if N > 1:
    factors.append(N)
  return factors

素因数分解についてもより高速なアルゴリズムが知られていますが，本記事では扱いません．

4.3. p 進付値

【定義 7】

$p$ を素数，$N$ を正整数とする．$p$ が $N$ の素因数分解に $k$ 回現れるとき，$k$ を $N$ の $p$ 進付値 といい，$v_p(N)$ と書く．

言い換えれば，$v_p(N)$ とは，$p^k$ が $N$ の約数であるような非負整数 $k$ のうち最大のものである．

例えば，次が成り立ちます．

$v_2(1)=0$
$v_2(2)=1$
$v_2(3)=0$
$v_2(4)=2$
$v_2(5)=0$
$v_2(6)=1$
$v_2(1000)=3$
$v_2(360)=3$
$v_3(360)=2$
$v_5(360)=1$
$v_7(360)=0$
$v_{11}(360)=0$

素因数分解は，総積の記号 $\prod$ を用いて，$N = \prod_k p_k ^ {v _ {p _ k}(N)}$，あるいは $e_k = v _ {p _ k}(N)$ とおいて，$N = \prod_k p _ k ^ {e _ k}$ などと表すことが多いです．

積をとる素数 $p_1, p_2, \ldots$ としてはすべての素数を対象とした無限積として表記することもありますし，特定の範囲の素数だけを対象とした有限積として表記することもあります．無限積として表記される場合にも，有限個の $e_k$ を除いて $e_k=0$ であり，本質的には有限積と同じ扱いをします．

$a=\prod_k p_k^{e_k}, b=\prod_k p_k^{f_k}$ とすると，$ab=\prod_k p_k^{e_k+f_k}$ です．このように乗算が，素数ごとの指数に対する加算に変換されるのが素因数分解の特徴です．言い換えれば，$v_p(ab)=v_p(a)+v_p(b)$ が成り立ちます．

$p$ 進付値によって，約数倍数の関係は次のように整理できます．

【命題 8】

正整数 $a,b$ に対して，$b$ が $a$ の約数であることと，任意の素数 $p$ に対して $v_p(b)\leq v_p(a)$ が成り立つことは同値である．

$b$ が $a$ の約数であるとは，ある $c$ に対して $bc=a$ が成り立つことです．この条件は，ある $c$ に対してすべての素数 $p$ に対して $v_p(b)+v_p(c)=v_p(a)$ が成り立つことと言い換えられます．

$v_p(b)\leq v_p(a)$ が必要であることは明らかです．また有限個の $p$ を除いて $v_p(b)=v_p(a)=0$ であることから，この必要条件が成り立つとき，$v_p(c)=v_p(a)-v_p(b)$ となるように $c$ を定めることができます． $\blacksquare$

すると例えば，次のようなことが分かります．

$v_p\left(\gcd(a,b)\right)=\min\left(v_p(a),v_p(b)\right)$
$v_p\left(\mathrm{lcm}(a,b)\right)=\max\left(v_p(a),v_p(b)\right)$

5. 有理数に対する合同式

3 節では $a,b\in \mathbb{F} _ p$ が $a\neq 0$ を満たすとき，除算 $b/a\in \mathbb{F} _ p$ が定義できました．このことに対応するように，$a$ が $p$ の倍数ではないとき有理数 $b/a$ は $p$ を法とする合同式で扱うことができて，「$b/a$ を $p$ で割った余りのようなもの」が定義できることが分かります．

以下本節では，特に断らない限り「有理数 $a=\dfrac{a_1}{a_2}$」のように書いた場合，$a_1$ は整数，$a_2$ は正整数であり $\gcd(a_1,a_2)=1$ が成り立つ（つまり $\dfrac{a_1}{a_2}$ は $a$ の既約分数表示である）ことを仮定します．また本節においては $a_1$ を $a$ の分子，$a_2$ を $a$ の分母ということにします．

【定義 9】（有理数に対する合同式）

$p$ を素数とする．有理数 $a=\dfrac{a_1}{a_2}, b=\dfrac{b_1}{b_2}$ について $a_2,b_2$ は $p$ の倍数ではないとする．

$a_1b_2-a_2b_1$ が $p$ の倍数であるとき，$a$ と $b$ は $p$ を法として合同（congruent）であるといい，$a\equiv b\pmod{p}$ と書く．

「有理数に対する合同式」という見出しを付けましたが，合同式を定義したのは分母が $p$ の倍数ではないような有理数に限られることに注意してください．（整数論の用語では，「有理数のうちで $p$ 進整数であるもの」ということになります．）

また $a,b$ が整数であるときその既約分数表示は $\dfrac{a}{1}, \dfrac{b}{1}$ なので，【定義 9】の意味で $a\equiv b\pmod{p}$ となることは従来の意味で $a\equiv b\pmod{p}$ が成り立つことと同値になります．この意味で，【定義 9】は従来の合同式の一般化になっています．

有理数に対する合同式に関する基礎事項を証明します．その際にいちいち分子・分母を持ち出して議論せずに済むように，次の補題を用意しておきます．

【補題 10】

$p$ を素数とする．$a, b$ を分母が $p$ の倍数ではないような有理数とする．$a\equiv b\pmod{p}$ が成り立つことは，以下の条件をすべて満たす整数 $s$ が存在することと同値である．

$s$ は $p$ の倍数ではない．
$sa,sb$ は整数であり，$sa\equiv sb\pmod{p}$ が成り立つ．

$a=\dfrac{a_1}{a_2}, b=\dfrac{b_1}{b_2}$ とします．まず $a\equiv b\pmod{p}$ ならば $s=a_2b_2$ が条件を満たすことが確認できます．逆に条件を満たす $s$ が存在するならば，$(a_2b_2)sa\equiv (a_2b_2)sb\pmod{p}$ も成り立ちます．よって $s(a_1b_2-a_2b_1)$ は $p$ の倍数です．$s$ が $p$ の倍数でないことから $a_1b_2-a_2b_1$ は $p$ の倍数，つまり $a\equiv b\pmod{p}$ となります． $\blacksquare$

【補題 11】

$p$ を素数とする．$a, b, c$ を分母が $p$ の倍数ではないような有理数とする．このとき $a\equiv b\pmod{p}$ かつ $b\equiv c\pmod{p}$ ならば，$a\equiv c\pmod{p}$ が成り立つ．

【補題 10】より，$p$ の倍数ではない整数 $s,t$ であって，$sa,sb,tb,tc$ が整数かつ $sa\equiv sb\pmod{p}$, $tb\equiv tc\pmod{p}$ を満たすものがとれます．

このとき $st$ は $p$ の倍数ではなく，$sta,stb,stc$ は整数です．また

$$ sta\equiv t\cdot sa\equiv t\cdot sb\equiv s\cdot tb\equiv s\cdot tc\equiv stc\pmod{p} $$

となるので再び【補題 10】より $a\equiv c\pmod{p}$ が成り立ちます． $\blacksquare$

【定理 12】
分母が $p$ の倍数ではないような有理数 $a_1,b_1,a_2,b_2$ について $a_1\equiv a_2\pmod{p}$，$b_1\equiv b_2\pmod{p}$ であるとき，次が成り立つ． $$ \begin{aligned} a_1+b_1&\equiv a_2+b_2\pmod{p}\\\ a_1-b_1&\equiv a_2-b_2\pmod{p}\\\ a_1b_1&\equiv a_2b_2\pmod{p} \end{aligned} $$

【補題 10】より，$p$ の倍数ではない整数 $s,t$ であって

$sa_1,sa_2$ は整数で $sa_1\equiv sa_2\pmod{p}$
$tb_1,tb_2$ は整数で $tb_1\equiv tb_2\pmod{p}$

を満たすものがとれます．$st$ は $p$ の倍数ではなく，$st(a_1\pm b_1)$, $st(a_2\pm b_2)$, $sta_1b_1$, $sta_2b_2$ はすべて整数です．さらに

$$ \begin{aligned} st(a_1\pm b_1) &\equiv t\cdot sa_1\pm s\cdot tb_1\equiv t\cdot sa_2\pm s\cdot tb_2 \\ &\equiv st(a_2\pm b_2)\pmod{p}, \\ st(a_1b_1) &\equiv sa_1\cdot tb_1\equiv sa_2\cdot tb_2 \equiv st(a_2b_2)\pmod{p} \end{aligned} $$

が成り立つので，再び【補題 10】より $a_1\pm b_1\equiv a_2\pm b_2\pmod{p}$，$a_1b_1\equiv a_2b_2\pmod{p}$ であることが分かります． $\blacksquare$

$p$ を法とする合同式について，整数は $0,1,\ldots,p-1$ のどれかと合同で $p$ 種類に分類されました．有理数でも同様のことが成り立ちます．

【定理 13】

分母が $p$ の倍数ではない有理数 $a=\dfrac{a_1}{a_2}$ に対して，$a_2$ の $p$ を法とする乗法逆元を $a _ {2 , \mathrm{inv}}$ とする．このとき $a\equiv a_1\cdot a _ {2 , \mathrm{inv}}\pmod{p}$ が成り立つ．

特に分母が $p$ の倍数ではない有理数はすべて $0,1,\ldots,p-1$ のいずれかに合同である．

定義から，$a_1 \equiv a_1 \cdot a _ {2, \mathrm{inv}} \cdot a_2 \pmod{p}$ を示せばよく，これは $a _ {2,\mathrm{inv}}\cdot a_2\equiv 1\pmod{p}$ より明らかです． $\blacksquare$

【定理 12】および【定理 13】より，分母が $p$ の倍数ではない有理数について，合同式はおおよそ整数の場合と同じように取り扱えることが分かります．特に加算・減算・乗算を反復する計算では，

最初に与えられた値をそれと合同な数に置き換えてもよい．この際，特に $0, 1, \ldots, p-1$ のいずれかに置き換えることができる．
加算・減算・乗算などを行うたびに，その計算結果をそれと合同な数に置き換えてもよい．

ということが分かります．

6. Fermat の小定理

【定理 14】（Fermat の小定理）

$p$ を素数とし，$a$ を整数とする．$a$ が $p$ の倍数でないならば，$a ^ {p-1}\equiv 1\pmod{p}$ が成り立つ．また任意の $a$ に対して $a ^ p\equiv a\pmod{p}$ が成り立つ．

$a$ が乗法逆元を持つことから，$1, 2, \ldots, (p-1)$ をそれぞれ $a$ 倍した数

$$a, 2a, \ldots, (p-1)a$$

は，$p$ を法として $1, 2, \ldots, (p-1)$ の並べ替えとなります．

注意

「$p$ を法として並べ替えとなる」ということを定義すると次のようになります：

$a_1,a_2,\ldots,a_n$ と $b_1,b_2,\ldots,b_n$ が $p$ を法として並べ替えであるとは，$b_1,b_2,\ldots,b_n$ を適当に並べ替えることで任意の $i$ について $a_i\equiv b_i\pmod{p}$ であるようにできることをいう．

また $\mathbb{F} _ p$ では，単に「$a, 2a, \ldots, (p-1)a$ は，$1, 2, \ldots, (p-1)$ の並べ替えとなる」といってしまってよく記述が簡潔になるので，$\mathbb{F} _ p$ に抵抗がない方はそのように考えるとよいでしょう．

したがって，$a, 2a, \ldots, (p-1)a$ の総積は $1, 2, \ldots, (p-1)$ の総積に一致します．ここから

$$(p-1)!a ^ {p-1}\equiv (p-1)!\pmod{p}$$

が成り立ちます．$(p-1)!$ は $p$ の倍数ではないので $p$ を法として乗法逆元を持ちます．よって $a ^ {p-1}\equiv 1\pmod{p}$ が成り立ちます．

任意の $a$ について $a ^ p\equiv a\pmod{p}$ が成り立つのは上のことから明らかです． $\blacksquare$

【系 15】
$p$ を素数とし，$a$ を $p$ の倍数ではない整数とする．このとき $a ^ {p-2}$ は $p$ を法とする $a$ の乗法逆元である．

Fermat の小定理から明らかです． $\blacksquare$

7. 関連問題

1，2 はそれぞれ素数判定・素因数分解をする問題です．

3，4，5，6，7 は素因数分解の一意性を用いる問題です．一部の問題では解法によっては二項係数の知識が必要になります．

8. まとめ

本記事では，素数の基礎的な性質について解説しました．特に素因数分解の一意性や，$p$ を法とする合同式において $p$ の倍数でない数は乗法逆元を持つこと（$\mathbb{F}_p$ が体になること）は重要です．

アルゴリズムとしては，素数判定・素因数分解を $\mathrm{O}(\sqrt{N})$ 時間で行うアルゴリズムを解説しました．これらはそれぞれより高速なアルゴリズムも知られており，今後の AtCoder Algorithm Lectures でも解説します．

また，素数の性質については引き続き次の講座でも解説します．

また，$\mathbb{F}_p$ の理論は有限体の一般論へと一般化されます．有限体についても AtCoder Algorithm Lectures で解説する予定です．

9. 参考文献

Wikipedia．素数．https://ja.wikipedia.org/wiki/素数．（閲覧日: 2026-03-31）．
Wikipedia．フェルマーの小定理．https://ja.wikipedia.org/wiki/フェルマーの小定理．（閲覧日: 2026-03-31）．
けんちょん．AtCoder 版！マスター・オブ・整数 (素因数分解編)．https://qiita.com/drken/items/a14e9af0ca2d857dad23．（閲覧日: 2026-03-31）．

トップページ：AtCoder Algorithm Lectures