Explore this weird gcd problem

Number Theory Level 4

A sequence $\{x_n\}_{n=0}^{\infty}$ is defined by $x_{1}=2$ and $x_{n+1}=2x_{n}^{2}-1$ for all $n \in \mathbb N^+$ .

Determine the greatest common divisor of $1729!$ and $x_{1729!}$ .

Note: You could easily get the answer if $x_1=1$ , but unfortunately here is given $x_{1}=2$ . So think twice before you choose the answer.

37 1729 3 1

1 solution

Patrick Corn
May 14, 2018

Suppose $x_a \equiv x_b$ mod $p$ for some $p,$ with $a<b.$ Then the sequence repeats after $b$ : $x_{b+1} \equiv x_{a+1}, x_{b+2} \equiv x_{a+2},$ etc.

Now suppose $x_1,x_2,\ldots, x_p$ are all nonzero mod $p.$ By the pigeonhole principle , there are two distinct $a,b$ such that $x_a \equiv x_b$ mod $p,$ $1 \le a<b \le p.$ But then the values of the sequence repeat, so the sequence is never divisible by $p.$

Note also that if $x_k \equiv 0$ mod $p,$ then $x_{k+1} \equiv -1,$ $x_{k+2} \equiv 1,$ and $x_m \equiv 1$ for all $m \ge k+3.$

The upshot is that, for any positive integer $p \ge 2,$ there is at most one value of the sequence that is divisible by $p,$ and that value must occur in the first $p$ terms if it occurs at all. That is, $x_n$ is only divisible by integers that are $\ge n.$

(Remark 1: This gives a proof of the infinitude of primes, now that I think about it!

Remark 2: With a little thought, you can show that the inequality is actually strict.)

Anyway, to solve the problem, note that if $n=1729!,$ $x_n$ is only divisible by primes $\ge 1729!,$ but no such primes divide $1729!,$ so $x_{1729!}$ and $1729!$ have no common prime factors, and hence their gcd is $\fbox{1}.$

(Remark 3: I used that $1729!$ wasn't prime, but if you believe Remark 2, that's not necessary; in fact $\text{gcd}(n,x_n) = 1$ for all $n.$ )

Nice solution! In Remark 1,assume $p_{1}<p_{2}<\cdots <p_{s}$ are all the primes,then $x_{(p_{1}p_{2}...p_{s})}$ must have a new prime factor by our conclusion,which is a contradiction. In Remark 2,we assume $p|x_{p}$ for prime p.Then $x_{a}$ $\equiv$ $x_{b}$ (nonzero) $mod p$ cannot hold for any $1\le a<b\le p-1$ (Otherwise $x_{p+b-a}\equiv x_{p} \equiv 0 (mod p)$ ,which is a contrdiction).So there exists $(i_{1},i_{2},...,i_{p-1})$ as a permutation of $(1,2,...,p-1)$ such that $x_{i_{j}}\equiv j (mod p)$ .But $x_{k}\equiv 1 (mod p)$ ( $1\le k \le p-1$ ) gives $x_{k+1}\equiv 1 (mod p)$ ,which means $k=p-1$ ,and so $x_{p}\equiv 1(mod p)$ ,contradiction.Thereby the inequality is actually strict.

Haosen Chen - 3 years ago

Explore this weird gcd problem

1 solution

0 pending reports