Prove 5 is not a member of the sequence

[guildmage]

I found this problem in a book for secondary students. It says it's from the Australian Mathematical Olympiad in 1982.

The sequence $$a_1,a_2,...$$ is defined as follows:

$$a_1 = 2$$ and for $$n \geq 2$$, $$a_n$$ is the largest prime divisor of $$a_1a_2...a_{n-1}+1$$.

Prove that 5 is not a member of this sequence.

I don't know if my analysis of the problem is correct, but if 5 were a member of the sequence, then $$a_1a_2...a_{n-1}+1=5q$$ for some $$q\in{\textbf{N}}$$.

For $$q$$ even, then $$a_1a_2...a_{n-1}+1$$ is even, which means $$a_1a_2...a_{n-1}$$ is odd. But $$a_1 = 2$$ so that $$a_1a_2...a_{n-1}$$ is even. A contradiction.

How do I show that for $$q$$ odd? Or do I have to resort to a different approach?

 

[Dragonfall]

Well, if that were the case, then $$a_1...a_n+1=2^a3^b5^c=2*3*a_3...a_n+1$$, so a=b=0. I can't go further. But maybe the chinese remainder theorem can be used, since $$7*a_4...a_n\equiv 2*a_4...a_n\equiv 4 (\mod 5^k)$$ for all k<c+1.

 

[ramsey2879]

I found this problem in a book for secondary students. It says its from the Australian Mathematical Olympiad in 1982.

The sequence $$a_1,a_2,...$$ is defined as follows:

$$a_1 = 2$$ and for $$n \geq 2$$, $$a_n$$ is the largest prime divisor of $$a_1a_2...a_{n-1}+1$$.

Prove that 5 is not a member of this sequence.

I don't know if my analysis of the problem is correct, but if 5 were a member of the sequence, then $$a_1a_2...a_{n-1}+1=5q$$ for some $$q\in{\textbf{N}}$$.

For $$q$$ even, then $$a_1a_2...a_{n-1}+1$$ is even, which means $$a_1a_2...a_{n-1}$$ is odd. But $$a_1 = 2$$ so that $$a_1a_2...a_{n-1}$$ is even. A contradiction.

How do I show that for $$q$$ odd? Or do I have to resort to a different approach?

it can be shown that both 2 and 3 are not divisors since 2 and 3 are members of the sequence and the product + 1 is not divisible by prime factors of the product. If 5 was the largest prime factor then the number is a power of 5 and ends in 25. That would seem to call for a different approach.

 

[Tibarn]

Here's where I started before I got lazy:

The first three terms of the sequence are 2, 3, and 7. It's easy to see that if p is in the sequence, then p does not divide $$a_1a_2...a_{n-1}+1$$; thus, a given prime can appear at most once. Now, if $$a_1a_2...a_{n-1}+1$$ has a prime factor other than 5, this cannot be 2 or 3 since they're in the sequence, so it would have to be a prime larger than 5. Therefore, the only way for the largest prime factor to be 5 is for $$a_1a_2...a_{n-1}+1$$ to be a power of 5.

 

[Vanadium 50]

Therefore, the only way for the largest prime factor to be 5 is for $$a_1a_2...a_{n-1}+1$$ to be a power of 5.

Aren't you done? Then $a_1a_2...a_{n-1}$ is divisible by 4. But there is at most one power of two in that product.

 

[guildmage]

I see. Then I suppose it is not necessary to split the problem into two cases (q even and q odd).