뤼카 수열

3. 성질

뤼카 수열은 이차 방정식의 해를 이용하여 일반항을 나타낼 수 있고, 생성 함수를 통해 표현할 수도 있다.^[8] 뤼카 수열과 관련된 여러 등식이 존재하며,^[8] 주요 등식은 다음과 같다.

• $V\_n^2-DU\_n^2=4Q^n$
• $U\_n^2-U\_\{n-1\}U\_\{n+1\}=Q^\{n-1\}$
• $DU\_n=V\_\{n+1\}-QV\_\{n-1\}$
• $V\_n=U\_\{n+1\}-QU\_\{n-1\}$
• $2U\_\{m+n\}=U\_mV\_n+U\_nV\_m$
• $2V\_\{m+n\}=V\_mV\_n+DU\_mU\_n$
• $U\_\{2n\}=U\_nV\_n$
• $V\_\{2n\}=V\_n^2-2Q^n$
• $U\_\{m+n\}=U\_mV\_n-Q^nU\_\{m-n\}$
• $V\_\{m+n\}=V\_mV\_n-Q^nV\_\{m-n\}=DU\_mU\_n+Q^nV\_\{m-n\}$
• $2^\{n-1\}U\_n=\{n\; \backslash choose\; 1\}P^\{n-1\}+\{n\; \backslash choose\; 3\}P^\{n-3\}D+\backslash cdots$
• $2^\{n-1\}V\_n=P^n+\{n\; \backslash choose\; 2\}P^\{n-2\}D+\{n\; \backslash choose\; 4\}P^\{n-4\}D^2+\backslash cdots$

• $m|n$이면, $U\_m|U\_n$이다.
• ''P'', ''Q'' 값에 따라 $U\_n$, $V\_n$의 짝홀성이 결정된다.
• 홀소수 ''p''에 대한 합동식이 성립하며, 이는 페르마의 소정리의 일반화이다.

3. 1. 일반항

3. 2. 생성 함수

3. 3. 점화 관계 (영어 문서)

3. 4. 펠 방정식 (영어 문서)

3. 5. 다른 매개변수를 가진 수열과의 관계 (영어 문서)

• $V\_n^2-DU\_n^2=4Q^n$
• $U\_n^2-U\_\{n-1\}U\_\{n+1\}=Q^\{n-1\}$
• $DU\_n=V\_\{n+1\}-QV\_\{n-1\}$
• $V\_n=U\_\{n+1\}-QU\_\{n-1\}$
• $2U\_\{m+n\}=U\_mV\_n+U\_nV\_m$
• $2V\_\{m+n\}=V\_mV\_n+DU\_mU\_n$
• $U\_\{2n\}=U\_nV\_n$
• $V\_\{2n\}=V\_n^2-2Q^n$
• $U\_\{m+n\}=U\_mV\_n-Q^nU\_\{m-n\}$
• $V\_\{m+n\}=V\_mV\_n-Q^nV\_\{m-n\}=DU\_mU\_n+Q^nV\_\{m-n\}$
• $2^\{n-1\}U\_n=\{n\; \backslash choose\; 1\}P^\{n-1\}+\{n\; \backslash choose\; 3\}P^\{n-3\}D+\backslash cdots$
• $2^\{n-1\}V\_n=P^n+\{n\; \backslash choose\; 2\}P^\{n-2\}D+\{n\; \backslash choose\; 4\}P^\{n-4\}D^2+\backslash cdots$

• $m|n$이면, $U\_m|U\_n$이다.
• ''n''이 ''m''의 홀수 배수이면, $V\_m|V\_n$이다.
• ''N''이 2''Q''와 상호 소인 정수이고, $N|U\_r$이 되는 최소의 ''r''이 존재할 때, $N|U\_n$이 되는 ''n'' 전체는 ''r''의 배수 전체와 일치한다.

• ''P'', ''Q''가 짝수이면, $U\_n$, $V\_n$은 $U\_1$을 제외하고 항상 짝수이다.
• ''P''가 짝수이고, ''Q''가 홀수이면, $U\_n$의 짝/홀수는 ''n''의 짝/홀수와 일치하며, $V\_n$은 항상 짝수이다.
• ''P''가 홀수이고, ''Q''가 짝수이면, $U\_n$, $V\_n$은 항상 홀수이다.
• ''P'', ''Q''가 홀수이면, $U\_n$, $V\_n$은 ''n''이 3의 배수일 때 짝수이고, 그렇지 않을 때 홀수이다.

• $U\_p\backslash equiv\backslash left(\backslash frac\{D\}\{p\}\backslash right),\; V\_p\backslash equiv\; P\backslash pmod\{p\}$
• ''p''가 ''P'', ''Q''를 나누어 떨어뜨리면, ''p''는 $U\_1$을 제외한 모든 $U\_n$을 나눈다.
• ''p''가 ''P''를 나누어 떨어뜨리고 ''Q''를 나누어 떨어뜨리지 않으면, ''p''가 $U\_n$을 나누어 떨어뜨리는 것은 ''n''이 짝수인 것과 동치이다.
• ''p''가 ''P''를 나누어 떨어뜨리지 않고 ''Q''를 나누어 떨어뜨리면, ''p''는 절대로 $U\_n$을 나누어 떨어뜨리지 않는다.
• ''p''가 ''PQ''를 나누어 떨어뜨리지 않고, ''D''를 나누어 떨어뜨리면, ''p''가 $U\_n$을 나누어 떨어뜨리는 것은 ''n''이 ''p''의 배수인 것과 동치이다.
• ''p''를 ''PQD''를 나누어 떨어뜨리지 않는 홀소수라고 하고 $l=p-\backslash left(\backslash frac\{D\}\{p\}\backslash right)$라고 하면, ''p''는 $U\_l$을 나눈다.

• $U\_n$과 ''Q''는 서로 소이며, $V\_n$과 ''Q''도 서로 소이다.
• $U\_n$과 $V\_n$은 서로 소이거나, 최대공약수는 2이다.
• $\backslash gcd(U\_m,\; U\_n)=U\_\{\backslash gcd\; (m,\; n)\}.$
• $d=\backslash gcd(m,\; n)$라고 한다. $m/d,\; n/d$가 모두 홀수이면 $\backslash gcd(V\_m,\; V\_n)=V\_d.$이다.

3. 6. 기타 관계 (영어 문서)

3. 7. 정수 나누기 성질 (일본어, 영어 문서)

• $n\; \backslash mid\; m$이고 $n/m$이 홀수이면, $V\_m$은 $V\_n$을 나눈다.
• ''N''을 2''Q''와 서로소인 정수로 할 때, ''N''이 $U\_r$을 나누는 가장 작은 양의 정수 ''r''이 존재하면, ''N''이 $U\_n$을 나누는 ''n''의 집합은 정확히 ''r''의 배수의 집합이다.
• ''P''와 ''Q''가 짝수이면, $U\_n,\; V\_n$은 $U\_1$을 제외하고 항상 짝수이다.
• ''P''가 짝수이고 ''Q''가 홀수이면, $U\_n$의 패리티는 ''n''과 같고 $V\_n$은 항상 짝수이다.
• ''P''가 홀수이고 ''Q''가 짝수이면, $U\_n,\; V\_n$은 $n=1,\; 2,\; \backslash ldots$에 대해 항상 홀수이다.
• ''P''와 ''Q''가 홀수이면, $U\_n,\; V\_n$은 ''n''이 3의 배수일 때에만 짝수이다.
• ''p''가 홀수 소수이면, $U\_p\backslash equiv\backslash left(\backslash tfrac\{D\}\{p\}\backslash right),\; V\_p\backslash equiv\; P\backslash pmod\{p\}$ (르장드르 기호 참조).
• ''p''가 홀수 소수이고 ''P''와 ''Q''를 나누면, ''p''는 모든 $n>1$에 대해 $U\_n$을 나눈다.
• ''p''가 홀수 소수이고 ''P''는 나누지만 ''Q''는 나누지 않으면, ''p''는 ''n''이 짝수일 경우에만 $U\_n$을 나눈다.
• ''p''가 홀수 소수이고 ''P''는 나누지 않지만 ''Q''는 나누면, ''p''는 $n=1,\; 2,\; \backslash ldots$에 대해 $U\_n$을 절대 나누지 않는다.
• ''p''가 홀수 소수이고 ''PQ''는 나누지 않지만 ''D''는 나누면, ''p''는 ''n''이 ''p''의 배수일 경우에만 $U\_n$을 나눈다.
• ''p''가 홀수 소수이고 ''PQD''를 나누지 않으면, ''p''는 $l=p-\backslash left(\backslash tfrac\{D\}\{p\}\backslash right)$인 $U\_l$을 나눈다.

• $U\_n$과 ''Q''는 서로 소이며, $V\_n$과 ''Q''도 서로 소이다.
• $U\_n$과 $V\_n$은 서로 소이거나, 최대공약수는 2이다.
• $\backslash gcd(U\_m,\; U\_n)=U\_\{\backslash gcd\; (m,\; n)\}.$
• $d=\backslash gcd(m,\; n)$이고 $m/d,\; n/d$가 모두 홀수이면 $\backslash gcd(V\_m,\; V\_n)=V\_d.$

4. 예

• ''U_n''(1, -1)는 피보나치 수이고, ''V_n''(1, -1)는 뤼카 수이다.
• ''U_n''(3, 2)는 메르센 수(2 ^''n''-1)이고, ''V_n''(3, 2)는 2 ^''n''+1이며, 페르마 수를 포함한다.
• ''U_n''(2, -1)는 펠 수이고, ''V_n''(2, -1)는 펠-뤼카 수이다.

4. 1. 값

^[14]

4. 2. 특수한 경우

• ''U_n''(1, -1)는 피보나치 수, ''V_n''(1, -1)는 뤼카 수이다.
• ''U_n''(2, -1)는 펠 수, ''V_n''(2, -1)는 펠-뤼카 수(펠 수의 짝)이다.
• ''U_n''(1, -2)는 야콥스탈 수, ''V_n''(1, -2)는 야콥스탈-뤼카 수이다.
• ''U_n''(3, 2)는 메르센 수 (2^''n'' − 1), ''V_n''(3, 2)는 2^''n'' + 1 형태의 수이며, 여기에는 페르마 수가 포함된다.
• ''U_n''(6, 1)는 정사각형 삼각수의 제곱근이다.
• ''U_n''(''x'', −1)는 피보나치 다항식, ''V_n''(''x'', −1)는 뤼카 다항식이다.
• ''U_n''(2''x'', 1)는 제2종 체비쇼프 다항식, ''V_n''(2''x'', 1)는 제1종 체비쇼프 다항식에 2를 곱한 것이다.
• ''U_n''(''x''+1, ''x'')는 ''x''진법의 레피닛 수, ''V_n''(''x''+1, ''x'')는 ''xⁿ'' + 1이다.

5. 용어 (일본어 문서)

(''P'', ''Q'')에 따른 뤼카 수열 ''U''_''n'', ''V''_''n''에서, ''V''_''n''을 동반 뤼카 수열이라고도 한다. α/β가 1의 멱근일 때 ''U''_''n'', ''V''_''n''을 '''퇴화'''라고 하고, 그렇지 않을 때 '''비퇴화'''라고 한다.

''D''를 나누지 않는 소수 ''p''가 ''U''_''n''을 나누지만, ''m'' < ''n''인 ''U''_''m''을 나누지 않을 때, ''p''를 ''U''_''n''의 '''원시 약수'''라고 한다.

6. 응용 (영어 문서)

뤼카 수열은 확률적 뤼카 유사 소수 검사에 사용되며, 이는 일반적으로 사용되는 베일리-PSW 소수성 검사의 일부이다.

뤼카 수열은 뤼카-레머-리젤 검사를 포함한 일부 소수판정법과, 브릴하트-레머-셀프리지 1975에서 사용된 N+1 및 하이브리드 N-1/N+1 방법 등에 사용된다.^[4]

LUC는 뤼카 수열을 기반으로 하는 공개 키 암호 시스템으로,^[5] ElGamal (LUCELG), 디피-헬만 키 교환 (LUCDIF), RSA (LUCRSA)의 유사체를 구현한다. LUC에서 메시지의 암호화는 RSA 또는 디피-헬만에서처럼 모듈러 지수 연산을 사용하는 대신, 특정 뤼카 수열의 항으로 계산된다. 그러나 블라이헨바허 등의 논문에서^[6] LUC가 모듈러 지수 연산을 기반으로 하는 암호 시스템에 비해 갖는다고 여겨지던 많은 보안상의 장점이 실제로 존재하지 않거나, 주장만큼 크지 않다는 것을 보여준다.

7. 소프트웨어 (영어 문서)

Sagemath는 뤼카 수열 $U\_n$과 $V\_n$을 각각 `lucas_number1()`과 `lucas_number2()`로 구현한다.^[7]

8. 역사

프랑스 수학자 에두아르 뤼카의 이름을 따 명명되었다.

참조

_[1] 참고문헌 For such relations and divisibility properties
_[2] 학술지 A simple proof of Carmichael's theorem on primitive divisors http://www.fq.math.c[...] 2001
_[3] 학술지 Existence of primitive divisors of Lucas and Lehmer numbers https://hal.inria.fr[...]
_[4] 학술지 New Primality Criteria and Factorizations of 2^m ± 1 1975-04
_[5] 학술지 LUC: A new public key system
_[6] 서적 Advances in Cryptology — CRYPT0' 95
_[7] 웹사이트 Combinatorial Functions - Combinatorics https://doc.sagemath[...] 2023-07-13
_[8] 학술지 On the numerical factors of the arithmetic forms α^''n''±β^''n''
_[9] 기타 Peter Kiss, On Lucas pseudoprimes which are products of ''s'' primes, ''Fibonacci Numbers and Their Applications'', 1986, 131--139.
_[10] 기타 Carmichael, 上記論文, 定理20
_[11] 기타 Carmichael, 上記論文, 定理21
_[12] 학술지 Existence of primitive divisors of Lucas and Lehmer numbers http://www.loria.fr/[...]
_[13] 학술지 Primitive divisors of Lucas and Lehmer sequences http://www.loria.fr/[...]
_[14] 매스월드 Lucas sequence