Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove 5 is not a member of the sequence

  1. Jun 11, 2009 #1
    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?
    Last edited: Jun 11, 2009
  2. jcsd
  3. Jun 11, 2009 #2
    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.
    Last edited: Jun 11, 2009
  4. Jun 11, 2009 #3
    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.
  5. Jun 11, 2009 #4
    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.
  6. Jun 12, 2009 #5

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2017 Award

    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.
  7. Jun 12, 2009 #6
    I see. Then I suppose it is not necessary to split the problem in to two cases (q even and q odd).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook