Modularity and Recursive Sequences

Number Theory Level 3

The sequence $a_n$ is defined by

$\large \begin{cases} a_0=3 \\ a_{n+1}-a_n=n(a_n-1) & \text{for } n \ge 0 \end{cases}$

Find all positive integers $m$ such that $\gcd(m,a_n)=1$ for all $n \geq 0$ . What can the solution set for $m$ be best described as?

23, 529, 12167 Powers of any arbitrary integer Powers of 23 Powers of 2

1 solution

Chew-Seong Cheong
Oct 4, 2016

$\begin{aligned} a_{n+1} - a_n & = n(a_n-1) \\ a_{n+1} & = (n+1)a_n - n \\ a_{n+1} - 1 & = (n+1)a_n - (n + 1) \\ a_{n+1} - 1 & = (n+1)(a_n - 1) & \small \color{#3D99F6}{\text{Let }b_n = a_n - 1} \\ b_{n+1} & = (n+1)b_n \\ b_1 & = 1\cdot b_0 \\ b_2 & = 2 \cdot b_1 = 2 \cdot 1 \cdot b_0 \\ b_3 & = 3! b_0 \\ ... & = \ ... \\ \implies b_n & = n! b_0 \\ a_n - 1 & = n!(a_0-1) \\ \implies a_n & = 2n! + 1 \\ \implies a_n & \equiv 1 \text{ (mod }\boxed{2}) \end{aligned}$

$\implies m$ are the $\boxed{\text{powers of 2}}$ .

Modularity and Recursive Sequences

1 solution

0 pending reports