1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...