유사소수

유사 소수(pseudo primes)는 불완전하나마 소수를 생성해내는 생성함수를 지칭한다. 또는 그러한 생성함수를 통해서 만들어지는 소수를 말한다. 의사소수로도 불린다. 그러나 생성함수 그 자체로는 불완전한 것이 아니다.

종류

• 카탈랑 유사소수(Catalan pseudoprime)

$(-1)^{{n-1} \over {2}}\cdot C_{{n-1} \over {2}}\equiv 2{\pmod {n}}$

음이 아닌 정수 n에 대해서, n 번째 카탈랑 수 $C_{n}$는 다음과 같다.

$C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}={\frac {(2n)!}{n!(n+1)!}}$

카탈랑 수는 자연수열이며, n = 0…37 까지의 값들은 아래와 같다. (OEIS의 수열 A000108)

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110, 812944042149730764, 3116285494907301262, 11959798385860453492, 45950804324621742364, …

• 오일러 유사소수(Euler pseudoprime)

$a,n$ 서로소

$a^{(n-1)/2}\equiv \pm 1{\pmod {n}}$

• 오일러-야코비 유사소수(Euler–Jacobi pseudoprime)

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

$\left({\frac {a}{n}}\right)$은 야코비 기호

• 카마이클 수(Carmichael number)

• 루카스 유사소수(Lucas pseudoprime)

$P$그리고$Q,P>0,D=P^{2}-4Q$,

루카스 수열 $U_{n}(P,Q)\;,\;V_{n}(P,Q)$에 대응하는

$\delta (n)=n-\left({{D} \over {n}}\right)$

$n=$ 자연수 , $\left({{D} \over {n}}\right)$는 야코비 기호

• 페린 유사소수(Perrin pseudoprime)

$P(n)=P(n-2)+P(n-3),n>2$

초기 몇몇의 값은 다음과 같다.

$P(0)=3,P(1)=0,P(2)=2$

• 밀스 소수

• 실베스터 시퀸스

같이 보기

• 소수정리