一道代数题（98年初联12题）

青青子衿

已知$a^2-a-1=0$,求$a^{18}+323a^{-6}$的值
有没有更广义上的背景！

Tesla35

没啥意思。就是硬算吧。

青青子衿

回复 2# Tesla35
1998年全国初中数学联赛试题12题

其妙

回复 3# 青青子衿
根据带余除法来做

青青子衿

和这道题有关联吗？
\(\,x^2-x-1\,\)是\(\,ax^{17}+bx^{16}+1\,\)的因式
forum.php?mod=viewthread&tid=6455

tommywong

$a^2=a+1,a^3=2a+1,a^4=3a+2$
$a^{18}=F_{18}a+F_{17}=2584a+1597$

$b=\frac{1}{a}$
$b^2=-b+1,b^3=2b-1,b^4=-3b+2$
$b^6=(-1)^6 (-F_6 b+ F_5)=-8b+5$

$a^{18}+323b^6=2584(a-b)+1597+1615=5796$

isee

回复 6# tommywong
看到这个第一行的前三式，我终于能理解第二行了，然来就是 Fibonacci  的定义写成了方幂。

kuing

回复 7# isee

这样理解是吗？：设 `a^n=x_na+y_n`，则 `a^{n+1}=x_na^2+y_na=x_n(a+1)+y_na=(x_n+y_n)a+x_n`，所以 `x_{n+1}=x_n+y_n`, `y_{n+1}=x_n`，即 `x_{n+2}=x_{n+1}+x_n`。
也就是有 `x^n\equiv F_nx+F_{n-1}\pmod{x^2-x-1}`，或者 `x^n\equiv (-1)^{n+1}(F_nx-F_{n-1})\pmod{x^2+x-1}`（用于 5# 链接）

kuing

一般结论大概是酱紫吧？：

给定常数 `a`, `b`，则对 $n\inN$ 有
\[x^n\equiv A_nx+B_n\pmod{x^2-ax-b},\]其中：
数列 `\{A_n\}` 满足 `A_0=0`, `A_1=1`, `A_{n+2}=aA_{n+1}+bA_n`；
数列 `\{B_n\}` 满足 `B_0=1`, `B_1=0`, `B_{n+2}=aB_{n+1}+bB_n`。

给定常数 `a`, `b`, `c`，则对 $n\inN$ 有
\[x^n\equiv A_nx^2+B_nx+C_n\pmod{x^3-ax^2-bx-c},\]其中：
数列 `\{A_n\}` 满足 `A_0=0`, `A_1=0`, `A_2=1`, `A_{n+3}=aA_{n+2}+bA_{n+1}+cA_n`；
数列 `\{B_n\}` 满足 `B_0=0`, `B_1=1`, `B_2=0`, `B_{n+3}=aB_{n+2}+bB_{n+1}+cB_n`；
数列 `\{C_n\}` 满足 `C_0=1`, `C_1=0`, `C_2=0`, `C_{n+3}=aC_{n+2}+bC_{n+1}+cC_n`。

如此类推…………