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

Sequence and divisibility

  1. Oct 7, 2007 #1
    We have recurrent sequence of integer number [tex]a_{1},a_{2},...[/tex]
    [tex]a1=1, a2=2[/tex]
    [tex]a_{n}=3a_{n-1}+5a_{n-2}[/tex] for [tex]n=3,4,5,...[/tex]
    Is integer number [tex]k>=2[/tex], that [tex](a_{k+1}*a_{k+2}) mod a_{k} = 0[/tex] ?

    Please for quick help :)
     
  2. jcsd
  3. Oct 7, 2007 #2
    You need to clarify your post A(2) = 2. A(3)*A(4) = 11*43 is not divisible by A(2). Do you mean to ask whether for some integer n that [tex]a_{n}|a_{n+1}*a_{n+2}[/tex]?
     
    Last edited: Oct 7, 2007
  4. Oct 8, 2007 #3
    Yes. I must find some integer n (exactly k), where this modulo statement is true.
    Thanks for reply :)
     
  5. Oct 8, 2007 #4
    I was doing some number crunching to reduce the possibilities for k, but I'm still far from an answer.
    So far, I get the following:

    If b, a, 3a+5b, 14a+15b, ... are contiguous elements of the sequence, then we see that, if [tex]a_n[/tex]=b is even, then [tex]a_{n+3}[/tex]=14a+15b is also even. And since there happens to be an even element among the first 3 (namely, [tex]a_2[/tex]=2, then one every 3 elements from that point on ([tex]a_5, a_8, a_{11}[/tex]...) will be even too.
    In short, since [tex]a_2[/tex]=2,
    • [tex]n \equiv 2 \ (mod\ 3) \ \ \Rightarrow \ \ 2|a_n[/tex]
    Which means that the desired k cannot be congruent to 2 (mod 3), because [tex]a_k[/tex] would have a factor 2 that [tex](a_{k+1} * a_{k+2})[/tex] doesn't have.

    On similar arguments, based on this table:
    Code (Text):

    a_{n+ 0}                           b
    a_{n+ 1}            a                     (prime factors of a's coeff.)
    a_{n+ 2}           3a +           5b      3
    a_{n+ 3}          14a +          15b      2 7
    a_{n+ 4}          57a +          70b      3 19
    a_{n+ 5}         241a +         285b      241
      ...
    a_{n+11}     1306469a +     1558065b      23 43 1321
    a_{n+12}     5477472a +     6532345b      2 2 2 2 2 3 3 7 11 13 19
      ...
    a_{n+18} 29748832848a + 35477934605b      2 2 2 2 3 3 3 7 17 109 5309
     
    and given that [tex]a_3=11, a_4=43, a_5=23\ .\ 8, a_6=13\ .\ 59 \ \mbox{and}\ a_8=17\ .\ 794[/tex], we also have
    • [tex]n \equiv 3 \ (mod\ 12) \ \ \Rightarrow \ \ 11|a_n[/tex]
    • [tex]n \equiv 4 \ (mod\ 11) \ \ \Rightarrow \ \ 43|a_n[/tex]
    • [tex]n \equiv 5 \ (mod\ 11) \ \ \Rightarrow \ \ 23|a_n[/tex]
    • [tex]n \equiv 6 \ (mod\ 12) \ \ \Rightarrow \ \ 13|a_n[/tex]
    • [tex]n \equiv 8 \ (mod\ 18) \ \ \Rightarrow \ \ 17|a_n[/tex]
    and all these conditions (including the one above about even numbers) must be avoided by your k candidate. However, there are still plenty of valid candidates remaining.
     
    Last edited: Oct 8, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Sequence and divisibility
  1. Divisibility question (Replies: 12)

  2. Divisibility Question (Replies: 6)

  3. Division ring (Replies: 0)

Loading...