Sequence and divisibility

  • Thread starter terafull
  • Start date
  • #1
3
0

Main Question or Discussion Point

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

Answers and Replies

  • #2
841
0
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 :)
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:
  • #3
3
0
Yes. I must find some integer n (exactly k), where this modulo statement is true.
Thanks for reply :)
 
  • #4
695
2
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:
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:

Related Threads for: Sequence and divisibility

  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
11
Views
12K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
3K
Top