YOI 603：561 は、互いに素などの底で試しても、フェルマーの判定を通る

論文603 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/603 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。Zenodo でも公開しています（DOI：10.5281/zenodo.23014433）。

本文のサイトの記事は、これから順に公開します。

@misc{yamagishi2026yoi603,
  author = {Yamagishi, Yuuki},
  title = {561 Passes Fermat's Test for Every Base Coprime to It},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/603},
  doi = {10.5281/zenodo.23014433},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969434・969435・969440・969461 に記録されました（2026年10月01日 18:16（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

$n$ が素数なら、$n$ と互いに素などの $a$ についても $a^{n-1}$ を $n$ で割った余りは $1$ になる（フェルマーの小定理）。そこで、余りが $1$ になるかを見て素数らしさを判定する方法がある（フェルマーの判定）。この判定がどの合成数に、どれだけ騙されるかを数える。新しい定理も法則も主張しない。

第一に、$561$ は互いに素な底すべてで判定を通る。$561=3\times11\times17$ と互いに素な底は $320$ 個で、その $320$ 個すべてで余りが $1$ になる。$1$ から $560$ の底のうち割合は $\mathbf{0.571429}$ で、見破れるのは $3$・$11$・$17$ のどれかを共有する $240$ 個（$\mathbf{0.428571}$）だけである（第2節）。

第二に、こうした数は珍しいが、無くならない。互いに素な底すべてで判定を通る合成数（カーマイケル数）は、$10^3$ までに $1$ 個、$10^4$ までに $7$ 個、$10^5$ までに $16$ 個、$10^6$ までに $43$ 個ある。全部の底で確かめた数と、素因数だけで決める判定（コルセルトの判定）は、$10^5$ まで一つ残らず一致した（第2節）。

第三に、問いを足すと、騙す底が減る。$561$ で、$a^{280}$ がヤコビ記号に一致するかも問う（オイラーの判定）と騙す底は $80$ 個（$\mathbf{0.142857}$）、$2$ 乗の列を全部問う（ミラー＝ラビンの判定）と $10$ 個（$\mathbf{0.017857}$）になる（第3節）。

第四に、これが本稿の芯である。最後の問いが見ているのは、$2$ 乗して $1$ になる数が $\pm1$ の二つしかないかどうかである。素数 $557$ を法とすると $2$ 乗して $1$ になる数は $1$ と $556$ の $2$ 個だが、$561$ を法とすると $8$ 個ある。底 $2$ で $2^{35},2^{70},2^{140},2^{280}$ を $561$ で割ると $263,166,67,1$ で、$1$ の直前の $67$ が $\pm1$ でない $1$ の平方根として $561$ を見破る（第3節）。

第五に、分離子は、何を問うかである。フェルマーは最後の一つ $a^{n-1}$ だけを問い、オイラーはその半分の冪とヤコビ記号を、ミラー＝ラビンは $2$ 乗の列の途中を全部問う。騙す底は $320$、$80$、$10$ と減り、ミラー＝ラビンでは $10^4$ までのどの奇数の合成数でも、騙す底の割合は上限の $1/4$ を超えなかった（ちょうど $1/4$ になるのは $9$）（第3節）。

キーワード：カーマイケル数、フェルマーの素数判定、ミラー＝ラビン判定、擬素数、素数判定

Abstract

If $n$ is prime, $a^{n-1}$ leaves remainder $1$ on division by $n$ for every $a$ coprime to $n$ (Fermat’s little theorem).So one may judge whether a number looks prime by checking whether that remainder is $1$ (Fermat’s test).Here it is counted which composite numbers fool this test, and by how many bases.No new theorem or law is claimed.

First, $561$ passes the test for every coprime base、there are $320$ bases coprime to $561=3\times11\times17$, and for all $320$ the remainder is $1$. Among the bases $1$ to $560$ that is a share of $\mathbf{0.571429}$; only the $240$ bases ($\mathbf{0.428571}$) sharing one of $3$, $11$, $17$ expose it (Section 2).

Second, such numbers are rare but do not run out、composite numbers passing the test for every coprime base (Carmichael numbers) number $1$ up to $10^3$, $7$ up to $10^4$, $16$ up to $10^5$ and $43$ up to $10^6$. The numbers found by trying every base and those given by a criterion using only the prime factors (Korselt’s criterion) agreed without exception up to $10^5$ (Section 2).

Third, adding questions reduces the fooling bases、for $561$, asking also whether $a^{280}$ equals the Jacobi symbol (Euler’s test) leaves $80$ fooling bases ($\mathbf{0.142857}$), and asking about the whole chain of squares (the Miller--Rabin test) leaves $10$ ($\mathbf{0.017857}$) (Section 3).

Fourth, and this is the core.What the last question looks at is whether the only numbers whose square is $1$ are $\pm1$、modulo the prime $557$, the numbers whose square leaves $1$ are just $1$ and $556$; modulo $561$ there are $8$. With base $2$, $2^{35},2^{70},2^{140},2^{280}$ leave $263,166,67,1$ on division by $561$, and $67$, just before the $1$, is a square root of $1$ other than $\pm1$ and exposes $561$ (Section 3).

Fifth, the separator is what is asked、Fermat asks only about the last term $a^{n-1}$; Euler asks about half that power and the Jacobi symbol; Miller--Rabin asks about every step of the chain of squares. The fooling bases fall from $320$ to $80$ to $10$, and for Miller--Rabin no odd composite up to $10^4$ had a fooling share above the bound $1/4$ (exactly $1/4$ for $9$) (Section 3).

Keywords: Carmichael numbers, Fermat primality test, Miller-Rabin test, pseudoprime, primality testing

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/603/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/603 はいつも最新の版を指します）。Zenodo の記録とは、Zenodo に上げる前の改訂のぶんだけ違うことがあります。

YOI の一覧へ