カーマイケル数

ウィキペディア

カーマイケル数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/24 15:47 UTC 版)

カーマイケル数（カーマイケルすう、Carmichael number）とは、自身と互いに素である任意の底でフェルマーテストを通過する合成数である。アメリカの数学者ロバート・ダニエル・カーマイケル（Robert Daniel Carmichael）にちなんでこう呼ばれる。また、絶対擬素数 (absolute pseudoprimes) とも呼ばれる。

概要

確率的素数判定法の一つであるフェルマーテストにおいて、素数ではないにもかかわらず確率的素数であると判定される数を擬素数と呼ぶ。擬素数であるかどうかはフェルマーテストの底ごとに定まり、ある底で擬素数であっても他の底で擬素数であるとは限らない。そのため、複数の底でフェルマーテストを行うことで、素数であることの信頼性を高めることができる。しかしながら、それ自身と互いに素である全ての底においてフェルマーテストを通過してしまう擬素数が存在し、それらはカーマイケル数と呼ばれる。すなわち、合成数 n がカーマイケル数であるとは、自身と互いに素である任意の自然数 a に対し、

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$