Carmichael Numbers

[2001.09.24]Carmichael数

■Fermatの小定理
最初にFermatの小定理を述べる。
    pを素数とする。任意の整数aに対して、a^p≡a (mod p)である。
    [特に、pで割り切れない任意の整数aに対して、a^p-1≡1 (mod p)である。]
この定理の逆(を少し修正したもの)
    nをn>1である自然数とする。任意の整数aに対して、aⁿ≡a (mod n)であれば、nは素数である。
は成立しない。
この反例となる合成数nがCarmichael数である。

■擬素数
aⁿ≡a (mod n)を満たす合成数nを底aの擬素数(pseudoprime)と呼ぶ。
例えば、91=7*13は底6の擬素数である。
なぜなら、合成数91=7*13に対して、(3,91)=1であるが、
    3⁶=729=91*8+1≡1 (mod 91)
から、
    3⁹¹=(3⁶)¹⁵*3≡1¹⁵*3≡3 (mod 91)
となる。

また、同様に、合成数341=11*31に対して、
    2¹⁰=1024=3*341+1≡1 (mod 341)
から、
    2³⁴¹=(2¹⁰)³⁴*2≡1³⁴*2≡2 (mod 341)
となるので、341=11*31は底2の擬素数である。

■自然数nがCarmichael数であるとは、nが合成数であり、かつ、1<=a<=nである任意の自然数aに対して、aⁿ≡a (mod n)となることをいう。

nがCarmichael数であれば、任意の自然数aについても、aⁿ≡a (mod n)が成立する。
言い換えると、Carmichael数nは、任意の自然数aに対して、底aの擬素数である。

■561=3*7*17はCarmichael数である。
実際、3,7,17は素数であり、
    (3-1)|(561-1),
    (7-1)|(561-1),
    (17-1)|(561-1)
である。任意の1<=a<=nに対して、Fermatの小定理より、(a,3)=1ならば、
    a^(3-1)≡1 (mod 3)
よって、
    a⁵⁶¹=(a^(3-1))²⁸⁰*a≡(1)²⁸⁰*a≡a (mod 3)
である。また、(a,3)=3ならば、
    a≡0 (mod 3)
よって、
    a⁵⁶¹≡0≡a (mod 3)
である。いずれにしても、a⁵⁶¹≡a (mod 3)
同様に、
    a⁵⁶¹≡a (mod 7)
    a⁵⁶¹≡a (mod 17)
a⁵⁶¹-aは、相異なる3素数3,7,17で割り切れるので、その積である3*7*17=561で割り切れる。よって、
    a⁵⁶¹≡a (mod 561)
aは任意の自然数なので、定義より、561はCarmichael数である。

■自然数nがCarmichael数である必要十分条件は、nが合成数であり、nは2乗因子を持たず、nを割り切る任意の素数pについて、p-1|n-1であることである。

nがCarmichael数と仮定する。定義より、nは合成数である。 pをnを割り切る素数とすると、定義より、pⁿ≡p (mod n)。よって、pⁿ-p=p(p^n-1-1)はnの倍数であるが、n-1>=1より、(p,p^n-1-1)=(p,p-1)=1。よって、pⁿ-pはp²で割り切れないので、nはp²で割り切れることはない。つまり、nは2乗因子を持たない。また、aをpの原始根(primitive root)の１つとする。 aⁿ≡a (mod n)より、aⁿ≡a (mod p)。 (p,a)=1なので、a^n-1≡1 (mod p)。 a (mod p)は位数p-1を持つので、p-1|n-1となる。

逆に、nが合成数で、2乗因子を持たず、nの各素因数pについて、p-1|n-1であると仮定する。 nは2乗因子を持たない(つまり、nの全ての素因子は相異なる)ので、nの各素因数pと任意のaに対して、aⁿ≡a (mod p)を示せば、十分である。 p|nであり、aが整数であると仮定する。 aがpで割り切れない場合、Fermatの小定理より、a^p-1≡1 (mod p)。 p-1|n-1なので、d=(n-1)/(p-1)とすると、dは自然数であり、aⁿ=(a^p-1)^d*a≡1^d*a≡a (mod p)。 aがpで割り切れる(pの倍数である)場合、明らかに、aⁿ≡a (mod p)。よって、全ての整数aについて、aⁿ≡a (mod p)となる。

■Carmichael数nは、奇数である。

Carmichael数nが偶数であると仮定する。 d=n/2とすると、dは自然数であり、(n-1)ⁿ≡((-1)²)^d≡1 (mod n)となる。
一方、Carmichael数の定義より、(n-1)ⁿ≡(n-1)≡(-1) (mod n)。
よって、(-1)≡1 (mod n)、つまり、2≡0 (mod n)となる。
これは、n=1,2の場合のみ成立するが、nは合成数なので、不合理。よって、nは奇数である。

■Carmichael数nは、3個以上の相異なる素因数から成る。

p,qを相異なる素数として、n=pqがCarmichael数であると仮定する。
pqはCarmichael数なので、p-1|pq-1=(p-1)q+(q-1)。
よって、p-1|q-1。
同様に、q-1|p-1。
p-1,q-1は共に自然数で、互いを約数に持つので、p-1=q-1。よって、p=q。
これは、p,qが相異なるという仮定に矛盾する。
よって、Carmichael数は、3個以上の相異なる素因数から成る。

■Carmichael数を探すプログラムを作成して実行すると、10⁷以下のCarmichael数は、以下のようになる。
よって、561は最小のCarmichael数である。

(561 = (3 11 17)) 
(1105 = (5 13 17)) 
(1729 = (7 13 19)) 
(2465 = (5 17 29)) 
(2821 = (7 13 31)) 
(6601 = (7 23 41)) 
(8911 = (7 19 67)) 
(10585 = (5 29 73)) 
(15841 = (7 31 73)) 
(29341 = (13 37 61)) 
(41041 = (7 11 13 41)) 
(46657 = (13 37 97)) 
(52633 = (7 73 103)) 
(62745 = (3 5 47 89)) 
(63973 = (7 13 19 37)) 
(75361 = (11 13 17 31)) 
(101101 = (7 11 13 101)) 
(115921 = (13 37 241)) 
(126217 = (7 13 19 73)) 
(162401 = (17 41 233)) 
(172081 = (7 13 31 61)) 
(188461 = (7 13 19 109)) 
(252601 = (41 61 101)) 
(278545 = (5 17 29 113)) 
(294409 = (37 73 109)) 
(314821 = (13 61 397)) 
(334153 = (19 43 409)) 
(340561 = (13 17 23 67)) 
(399001 = (31 61 211)) 
(410041 = (41 73 137)) 
(449065 = (5 19 29 163)) 
(488881 = (37 73 181)) 
(512461 = (31 61 271)) 
(530881 = (13 97 421)) 
(552721 = (13 17 41 61)) 
(656601 = (3 11 101 197)) 
(658801 = (11 13 17 271)) 
(670033 = (7 13 37 199)) 
(748657 = (7 13 19 433)) 
(825265 = (5 7 17 19 73)) 
(838201 = (7 13 61 151)) 
(852841 = (11 31 41 61)) 
(997633 = (7 13 19 577)) 
(1024651 = (19 199 271)) 
(1033669 = (7 13 37 307)) 
(1050985 = (5 13 19 23 37)) 
(1082809 = (7 13 73 163)) 
(1152271 = (43 127 211)) 
(1193221 = (31 61 631)) 
(1461241 = (37 73 541)) 
(1569457 = (17 19 43 113)) 
(1615681 = (23 199 353)) 
(1773289 = (7 19 67 199)) 
(1857241 = (31 181 331)) 
(1909001 = (41 101 461)) 
(2100901 = (11 31 61 101)) 
(2113921 = (19 31 37 97)) 
(2433601 = (17 37 53 73)) 
(2455921 = (13 19 61 163)) 
(2508013 = (53 79 599)) 
(2531845 = (5 19 29 919)) 
(2628073 = (7 37 73 139)) 
(2704801 = (11 29 61 139)) 
(3057601 = (43 211 337)) 
(3146221 = (13 31 37 211)) 
(3224065 = (5 13 193 257)) 
(3581761 = (29 113 1093)) 
(3664585 = (5 29 127 199)) 
(3828001 = (101 151 251)) 
(4335241 = (53 157 521)) 
(4463641 = (7 13 181 271)) 
(4767841 = (13 19 97 199)) 
(4903921 = (11 31 73 197)) 
(4909177 = (7 13 73 739)) 
(5031181 = (19 23 29 397)) 
(5049001 = (31 271 601)) 
(5148001 = (41 241 521)) 
(5310721 = (13 37 61 181)) 
(5444489 = (29 197 953)) 
(5481451 = (31 151 1171)) 
(5632705 = (5 13 193 449)) 
(5968873 = (43 127 1093)) 
(6049681 = (11 31 113 157)) 
(6054985 = (5 53 73 313)) 
(6189121 = (61 241 421)) 
(6313681 = (11 17 19 1777)) 
(6733693 = (109 163 379)) 
(6840001 = (7 17 229 251)) 
(6868261 = (43 211 757)) 
(7207201 = (17 353 1201)) 
(7519441 = (41 241 761)) 
(7995169 = (7 13 103 853)) 
(8134561 = (37 109 2017)) 
(8341201 = (11 31 61 401)) 
(8355841 = (13 41 61 257)) 
(8719309 = (19 37 79 157)) 
(8719921 = (7 23 41 1321)) 
(8830801 = (7 19 67 991)) 
(8927101 = (31 37 43 181)) 
(9439201 = (61 271 571)) 
(9494101 = (23 61 67 101)) 
(9582145 = (5 23 97 859)) 
(9585541 = (7 31 163 271)) 
(9613297 = (19 29 73 239)) 
(9890881 = (7 11 13 41 241))

[2001.09.30追記]
■同様のアルゴリズムのCプログラムによって、10⁹以下のCarmichael数を求めると、646個[2001.10.17訂正]見つかり、このようになる。

[2001.10.08追記]
■さらに、10⁹以上10¹⁰以下のCarmichael数を探すと、このように(未完)なる。

[参考文献]

[1]Joseph. H. Silverman, "A Friendly Introduction to Number Theory Second Edition", Prentice Hall Inc., 2001, ISBN0-13-030954-0, p225-235.
[2]Richard Crandall, Carl Pomerance, "Prime Numbers A Computational Perspective", Springer-Verlag New York, Inc., 2001, ISBN0-387-94777-9, p121-123.
[3]Paulo Ribenboim, "The Littile Book of Big Primes", Springer-Verlag New York, Inc., 1991, ISBN0-387-97508-X, p83-86.
[4]G.H.Hardy, E.M.Wright, "An Introduction to the Theory of Numbers 5th edition", Oxford University Press, 1979, ISBN0-19-853171-0, p71-72.

Last Update: 2006.12.30

H.Nakao