关于给定整数N的所有除数能否表示为特定系数斐波那契数线性组合的技术问询
大家好,我最近在研究斐波那契数的线性组合和整数除数之间的关联,有个问题想请教各位:
首先我们知道一个结论:每个整数都可以表示为两个斐波那契数的线性组合。比如要把整数$N$写成$N = aF_m + bF_n$的形式,我们可以选一对互质的斐波那契数$F_m, F_n$,再用扩展欧几里得算法求解系数$a,b$。
那我想反过来问:给定一个整数$N$,是否存在一对整数$a,b$,使得$N$的所有除数$d$都能写成$d = aF_m + bF_n$的形式?
另外我还在思考,有没有类似婆罗摩笈多-斐波那契恒等式的形式,能让:
$$N = aF_m + bF_n = (aF_r + bF_s)(aF_t + bF_u)$$
这里的$m,n,r,s,t,u$都是整数。
我自己做了一些小范围的尝试:当固定$a=1, b=-2$时,到整数11为止,它的所有除数都能被表示出来,比如:
- $1 = F_4 - 2F_1$
- $2 = F_6 - 2F_4$
- $3 = F_5 - 2F_1$
- $4 = F_6 - 2F_3$
- $5 = F_8 - 2F_6$
- $6 = F_6 - 2F_2$
- $7 = F_7 - 2F_4$
- $8 = F_9 - 2F_7$
- $9 = F_7 - 2F_3$
- $10 = F_6 - 2F_{-2}$
- $11 = F_7 - 2F_1$
这里我还用到了负下标斐波那契数来扩展表示范围,比如10、14、16、23的例子里都用到了负下标。
不过碰到12的时候,$a=1,b=-2$就不行了,但换成$a=1, b=-3$后,就能表示12的所有除数:1、2、3、4、6、12。另外我发现$a,b$必须是互质的——不然$N$的质因数$p$没法被表示成$aX + bY = p$的形式($X,Y$是斐波那契数)。
目前还有几个数比如20、22,我还没找到合适的$a,b$对来覆盖它们的所有除数,不过这类数的除数表示可能需要不同的$a,b$组合。
我的核心问题就是:对于任意给定的整数$N$,是否总能找到一对整数$a,b$,使得$N$的所有除数都可以表示为$aX + bY$的形式?这里的$X,Y$可以是任意斐波那契数,包括负下标情况。
备注:内容来源于stack exchange,提问作者vvg

