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).