VMO

Question

A sequence (a_n) is defined by a_1 = 5, a_2 = 13 and a_n+2 = 5a_n+1 - 6a_n, n 2. a) Prove that (a_n, a_n+1) = 1 for all positive integers n. b) Prove that if p is the prime divisor of a_2k then p-1 is divisible by 2^k+1 for all non-negative integers k.

Accepted Answer

a) It is easy to find the general formula of

(a_{n})

, which is

a_{n} = 2^{n} + 3^{n}, \forall n \in Z^{+} .

Suppose that there exists

n \geq 1

that

a_{n}, a_{n + 1}

have common prime divisor

p

. Clearly,

g cd (p, 6) = 1

. We have

{p ∣ 2^{n} + 3^{n}, p ∣ 2^{n + 1} + 3^{n + 1}, so {p ∣3 \cdot 2^{n} + 3^{n + 1}, p ∣2 \cdot 2^{n} + 3^{n + 1},

implies that

p ∣ 2^{n}

, which is a contradiction since

g cd (p, 6) = 1

.

b) Let

p

be the prime divisor of

2^{2^{k}} + 3^{2^{k}}

. Clearly,

2^{2^{k}} \equiv - 3^{2^{k}} (mod p)

so

2^{2^{k + 1}} \equiv 3^{2^{k + 1}} (mod p)

. By Fermat's little theorem,

2^{p - 1} \equiv 3^{p - 1} \equiv 1 (mod p) .

Let

h

be the smallest positive integer that

2^{h} \equiv 3^{h} (mod p)

. It is well-known that for all

h^{'} \geq h

satisfying this condition,

h ∣ h^{'}

. Now, we obtain that

h^{'} = 2^{k + 1}

satisfying that condition then

h ∣ 2^{k + 1}

, thus

h = 2^{x}

with

0 \leq x \leq k + 1

. Suppose that

x \leq k

then

2^{x} \equiv 3^{x} (mod p) so p ∣ 2^{x} - 3^{x} ∣ 2^{2 k} - 3^{2^{k}},

which is a contradiction since

p ∣ 2^{2^{k}} + 3^{2^{k}}

. Therefore, we must get

x = k + 1

, which implies

2^{k + 1} ∣ p - 1

.

□