【趣题征解】a,b,x(1)是正整数，x(n+1)＝ax(n)+b,n=1,2,…，证明{x(n)}中必有合数

luyuanhong

[这个贴子最后由luyuanhong在 2011/08/17 10:54am 第 3 次编辑]

【趣题征解】设 a,b,x(1) 是正整数，x(n+1)＝ax(n)+b ,n=1,2,…，证明{x(n)}中必有合数。
例如，设 a＝2 ，b＝1 ，x(1)＝2 ，这时
      x(2)＝ax(1)+b＝2×2+1＝5 ，
      x(3)＝ax(2)+b＝2×5+1＝11 ，
      x(4)＝ax(3)+b＝2×11+1＝23 ，
      x(5)＝ax(4)+b＝2×23+1＝47 ，
      x(6)＝ax(5)+b＝2×47+1＝95 ，95 就是一个合数。

ysr

[这个贴子最后由ysr在 2011/08/20 01:17pm 第 1 次编辑]

wangyangkee 先生,道理不错,但公式与原来的等价吗?好象也对

LLZ2008

ax(1)+b的素因数为p,那么x(p+1)是p的倍数。思路：找出数列的通项公式，再用余数有关知识。

ysr

wangyangkee 先生怎么把帖删了?
试做如下证明:
原公式中x（n+1），和xn是同1数列的两项，所以可认为是递推公式或计算机中的付值语句，则可以推出第n项公式xn=a^n*x1+(n-1)ab+b，由费尔马小定理知，当n，或n-1为素数p时，右边第1项除以与p互质的q余数为ax1，x1，若p除以q余数为1，则第2项余数为ab，若ab+b=q-x1，或q-ax1，则右边余数为0，能被q整除，由于n为连续数，所以是可能的

wangyangkee

ysr

先生第1步是对的,我的公式导错了,下面可以照样做，当ap非互质，费马小定理可以这样：a^p=a(modp),对吗?

wangyangkee

下面引用由ysr在 2011/08/20 09:03pm 发表的内容：
先生第1步是对的,我的公式导错了,下面可以照样做，当ap非互质，费马小定理可以这样：a^p=a(modp),对吗?

------当ap非互质，费马小定理可以这样：a^p=a(modp),对吗?------
当ap非互质，a是p的倍数；a^p=0(modp),

ysr

当ap非互质，a是p的倍数；a^p=0(modp),是对的
那么,N=Q,则上式右边第1项能被Q除余P,第2项被Q除余Q-P,因为A=1MOD(A-1),第2项为整数,商=(A^(N-1)-1）/（A-1）=A^(N-2)+A^(N-3)+……+A+1,总能找到Q去除B乘商余Q-P,Q为素数

luyuanhong

【趣题征解】设 a,b,x(1) 是正整数，x(n+1)＝ax(n)+b ,n=1,2,…，证明 {x(n)} 中必有合数。
例如，设 a＝2 ，b＝1 ，x(1)＝2 ，这时
      x(2)＝ax(1)+b＝2×2+1＝5 ，
      x(3)＝ax(2)+b＝2×5+1＝11 ，
      x(4)＝ax(3)+b＝2×11+1＝23 ，
      x(5)＝ax(4)+b＝2×23+1＝47 ，
      x(6)＝ax(5)+b＝2×47+1＝95 ，95 就是一个合数。

【证】如果 x(2) 是合数，命题显然成立。下面看 x(2) 是素数的情形。
    因为 x(2)=ax(1)+b＞a ，a 不可能是 x(2) 的倍数，a 与素数 x(2) 互素。
    由鸽笼原理可知，在 {x(n)} 中至少有两个数关于 x(2) 同余，即有 m＞n＞0 使得
    x(m)≡x(n)(mod x(2)) ，即有 ax(m-1)+b≡ax(n-1)+b (mod x(2)) ，
    ax(m-1)≡ax(n-1)(mod x(2)) ，因为 a 与 x(2) 互素，所以
    x(m-1)≡x(n-1)(mod x(2)) ，即有 ax(m-2)+b≡ax(n-2)+b (mod x(2)) ，
    ax(m-2)≡ax(n-2)(mod x(2)) ，因为 a 与 x(2) 互素，所以
    x(m-3)≡x(n-3)(mod x(2)) ，
    …… ，这样一直倒推下去，最后可得
    x(m-n+2)≡x(2)(mod x(2)) 。
    可见，x(m-n+2) 是 x(2) 的倍数，又因为数列递增，x(m-n+2)＞x(2) ，所以
x(m-n+2）必定是合数，即 {x(n)} 中必有合数。

ysr

教授的完整正确!8楼的是敷衍了事的,昨天中午想了半天没有作出,wangyangkee先生的第1步对吧?这种法无法证完,谢谢陆教授!