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 [tex]a_1,a_2,...[/tex] is defined as follows:

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

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 [tex]a_1a_2...a_{n-1}+1=5q[/tex] for some [tex]q\in{\textbf{N}}[/tex].

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

How do I show that for [tex]q[/tex] odd? Or do I have to resort to a different approach?

 

[Dragonfall]

Well, if that were the case, then [tex]a_1...a_n+1=2^a3^b5^c=2*3*a_3...a_n+1[/tex], so a=b=0. I can't go further. But maybe the chinese remainder theorem can be used, since [tex]7*a_4...a_n\equiv 2*a_4...a_n\equiv 4 (\mod 5^k)[/tex] 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 [tex]a_1,a_2,...[/tex] is defined as follows:

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

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 [tex]a_1a_2...a_{n-1}+1=5q[/tex] for some [tex]q\in{\textbf{N}}[/tex].

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

How do I show that for [tex]q[/tex] 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 [tex]a_1a_2...a_{n-1}+1[/tex]; thus, a given prime can appear at most once. Now, if [tex]a_1a_2...a_{n-1}+1[/tex] 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 [tex]a_1a_2...a_{n-1}+1[/tex] to be a power of 5.

 

[Vanadium 50]

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

Aren't you done? Then [itex]a_1a_2...a_{n-1}[/itex] 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).