斐波那契数列第2015个数除以105所得的余数为多少？求过程

斐波那契数列第2015个数除以105所得的余数为多少？求过程

不清楚你学过哪些知识，因而用我认为最简单的方法。如果看不懂，请追问并告知你学习过哪些相关知识，我换方法。



首先，先明确你说的斐波拉契数列是0，1，1，2，……开始的。
一般情况下，国内说的斐波拉契数列是1，1，2，3，……开始的，但刚查了一下oeis，它认为斐波拉契数列是从0开始的，因而我也按0开始。见下面的图片：



先铺垫一个性质：
——————————————————————
和的余数与余数的和关于除数同余。
——————————————————————
挺绕口的，实际上很简单。
例如：
a÷p=？……m
b÷p=？……n
那么
(a+b)÷p=？……(m+n)或者(a+b)÷p=？……(m+n-p)


好了，正式开始做题。
首先，105=3×5×7
下面分别判断第2015个数÷3、5、7的余数。



0、1、1、2、3、5、……
因而，每个数÷3的余数为
0、1、1、2、0、2、2、1、0、1、……
容易发现，0、1开始重复了，而每个余数与前两个数相关，于是，它按照0、1、1、2、0、2、2、1周期排列，每个周期是8。
（此处证明要用到通项公式，不难但输入麻烦，如非要证明，请追问）
而2015÷8=？……7
设第2015个数为a2015
于是
a2015≡2（mod 3）


同理，
0、1、1、2、3、5、……
因而，每个数÷5的余数为
0、1、1、2、3、0、3、3、1、4、0、4、4、3、2、0、2、2、4、1、0、1……
容易发现，0、1开始重复了，而每个余数与前两个数相关，于是，它按照0、1、1、2、3、0、3、3、1、4、0、4、4、3、2、0、2、2、4、1周期排列，每个周期是20。
而2015÷20=？……15

于是

a2015≡2（mod 5）


0、1、1、2、3、5、……
因而，每个数÷7的余数为
0、1、1、2、3、5、1、6、0、6、6、5、4、2、6、1、0、1……
容易发现，0、1开始重复了，而每个余数与前两个数相关，于是，它按照0、1、1、2、3、5、1、6、0、6、6、5、4、2、6、1周期排列，每个周期是16。
而2015÷20=？……15

于是

a2015≡6（mod 5）


因为3、5、7两两互质，
也就是说，求解下面的同余方程组即可求到a2015÷105的余数：
a2015≡2（mod 3）
a2015≡2（mod 5）
a2015≡6（mod 7）


这个同余方程组不难，甚至不用中国剩余定理，用简单的小学知识即可。
因为
x≡2（mod 3）
x≡2（mod 5）
那么x-2既是3的倍数，又是5的倍数，那么a2015-2就是15的公倍数。
因而x=15p+2
于是，x=2、17、32、47、62、77、92、……（同余理论可知，后面我们用mod 7去求特解，而7是素数，因而只写7个，一定有且只有1个特解）
而x≡6（mod 7）
因而x=62即为一个特解。


因而，x≡62（mod 105）
因而a2015≡62（mod 105）


也就是说，斐波拉契数列（0、1、1、2、...）的第2015个数÷105的余数为62。


【经济数学团队为你解答！】