[数论] 请教一个整除的题

设$A_1=0, A_2=1$，当$n>2$时，定义$A_n$为把$A_{n-1}, A_{n-2}$的十进制展开式按从左到右的次序连接起来得到的数，例如$A_3=A_2A_1=10, A_4=A_3A_2=101, A_5=A_4A_3=10110$，求所有的自然数$n$使$A_n$能被$11$整除

本主题由 kuing 于 2013-1-19 15:33 分类

kuing

管理员

UID: 1
帖子: 3992

2^#

发表于 2012-12-4 20:55

十进制还是二进制？

基本信息：kuing，GG，19880618~?，地道广州人，高中毕业，无业游民，不等式爱好者，论坛混混；
现状：冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做！（粤语）

abababa

高级会员

UID: 380
帖子: 157

3^#

发表于 2012-12-4 21:16

2# kuing
是10进制，可能因为前两个正好是1，0看起来像二进制。这个题一位网友说已经解出来了，但是他说他解得太复杂了，他得的结果是n=6k+1满足。

abababa

高级会员

UID: 380
帖子: 157

4^#

发表于 2013-1-25 19:23

顶一下

realnumber

论坛元老

UID: 16
帖子: 590

5^#

发表于 2013-1-25 21:29

本帖最后由 realnumber 于 2013-1-25 22:11 编辑

被11整除的数字(10进制),"偶数位和"与"奇数位和"相等,$10^n\equiv1 \mod11$,$n$为偶数;$10^n\equiv-1 \mod11$,$n$为奇数.
如此以下只关心$A_n$的是几位数,取$\mod11$情况下.
$A_3,A_4,A_5,A_6,A_7,...$依次是2,3,5,8,13,21,...位数,即偶,奇,奇,偶,奇,奇,....位数,---3为周期
(偶)$A_3\equiv-1$,(奇)$A_4\equiv2$,(奇)$A_5=A_4A_3\equiv2-1\equiv1$,
(偶)$A_6=A_5A_4\equiv10+2\equiv-1$,(奇)$A_7=A_6A_5=10+1\equiv2$,(奇)$A_8=A_7A_6\equiv1$,
$A_9=-1$,$A_{10}=2$开始出现周期了,...所以$n=6n+1$.
---我不知道怎么表达更清楚点.这个需要写吗?
$A_n=A_{n-1}A_{n-2}\equiv10A_{n-1}+A_{n-2} \mod11$($A_{n-2}$为奇位数);
$A_n=A_{n-1}A_{n-2}\equiv A_{n-1}+A_{n-2} \mod11$($A_{n-2}$为偶位数).

abababa

高级会员

UID: 380
帖子: 157

6^#

发表于 2013-1-26 08:59

5# realnumber
和那位网友说的差不多，都是先得到这个数的位数是Fibonacci数列，再得到$A_n \equiv (-1)^{d_{n-2}}A_{n-1} + A_{n-2} \pmod{11}$，$d$是位数
把n模3分类，然后用数学归纳法分别证这三类模2的余数是0，1，1
这就用了三次数学归纳法，但还不是最麻烦的，最麻烦的是他下面的证明，把n模6分类了，分别求了$A_n$模11的余数，用了6次数学归纳法，他说自己证明麻烦了，也没想出简单的方法。
楼上得出的周期最后也要用什么方法证明一下吧？不能就这么说是周期就证明了。