Results 1 to 14 of 14

Math Help - [SOLVED] Recursive sequence and primes

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    7

    [SOLVED] Recursive sequence and primes

    I don't speak English well, but I have a serious problem.

    Let k > 1. The sequence is defined by recursive equation a_0 = 1,<br />
a_{n+1} = 10^{k}a_n+1 for n>=0.

    We must prove that this sequence contains only finitely many primes.

    Thank you for our answers.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by bogdany View Post
    I don't speak English well, but I have a serious problem.

    Let k > 1. The sequence is defined by recursive equation a_0 = 1,<br />
a_{n+1} = 10^{k}a_n+1 for n>=0.

    We must prove that this sequence contains only finitely many primes.

    Thank you for our answers.
    I wonder if you might get more responses if this were posted in the Number Theory subforum.

    There is, however, a very easy answer. What's an easy test for divisibility by 3 based on a number's decimal digits?

    EDIT: Sorry, I completely forgot what the question asked momentarily, and the above gives a reason for there being infinitely many composites. I'll have to revisit the question. (And I may not be able to find an answer.)

    (By the way, does anyone know how to get strikethrough text formatting? I tried searching but couldn't find a way. So I made my wrong answer gray instead.)

    Edit 2: If the right answer involves divisibility tests for small primes then this link ("Divisibility by prime numbers under 50" by Stu Savory) might be helpful (or might not).
    Last edited by undefined; May 8th 2010 at 09:16 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2010
    Posts
    7
    Every third element of this sequence is divisible by 3, but it's still not enough.

    Thanks for this useful link, but I think that it isn't helpful in this problem.

    For examle the smallest (except 1) divisor of 10001 is 73
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Hello.

    Maybe it helps to write the sequence in closed form:

    a_n=\frac{1-10^{k(1+n)}}{1-10^k}=1+10^k+10^{2k}+\ldots+10^{nk}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by roninpro View Post
    Hello.

    Maybe it helps to write the sequence in closed form:

    a_n=\frac{1-10^{k(1+n)}}{1-10^k}=1+10^k+10^{2k}+\ldots+10^{nk}
    Working off what roninpro wrote, for every odd k and odd n pair a_n is divisible by 11.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2009
    Posts
    95
    For sufficiently large n, every odd n, a_n is divisbile by 10^k+1.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    May 2010
    Posts
    7
    Quote Originally Posted by gmatt View Post
    For sufficiently large n, every odd n, a_n is divisbile by 10^k+1.
    I think we can prove this using induction. Or have you other idea?

    But we still have a problem with even n, where a_n isn't divisbile by 3.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    The problem is that some of the terms are composite but have extremely weird prime factors. Does anybody know if this goes away when n gets large?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by bogdany View Post
    I don't speak English well, but I have a serious problem.

    Let k > 1. The sequence is defined by recursive equation a_0 = 1,<br />
a_{n+1} = 10^{k}a_n+1 for n>=0.

    We must prove that this sequence contains only finitely many primes.

    Thank you for our answers.
    Aren't these primes all in the form 4k+3? Doesn't that help us tremendously? (I really don't know, but I know you can do a lot more with that than with 1,11,111,\cdots)
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    May 2010
    Posts
    7
    Maybe I don't understand you, but f.e. 101 is prime, but it isn't in the form 4k+3.

    And I also think that k\neq1 is better for us.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by bogdany View Post
    I think we can prove this using induction. Or have you other idea?

    But we still have a problem with even n, where a_n isn't divisbile by 3.
    Actually the proof is very simple.

    <br />
a_n = \frac{10^{k(1+n)} - 1}{10^k-1}<br />


    use the fact that

    \gcd (10^k-1,10^k+1)=1

    and

    10^k \equiv -1 \bmod(10^k+1).

    You use the first fact to show that an inverse exists for 10^k-1 \bmod{10^k+1} and the second fact to show that the numerator is 0.

    Actually this sort of reasoning outlines a possible line of attack for the n even case.

    We want to find b such that

    <br />
a_n = \frac{10^{k(1+n)} - 1}{10^k-1}<br />
\equiv 0 \bmod{b}<br />

    thus if we can find a b that satisfies

    10^{k(1+n)}-1 \equiv 0 \bmod{b}

    and

    \gcd(10^k-1,b) = 1

    then we are done.

    Following this logic, it would probably be best to find b such that \gcd(10^k-1,b) = 1
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Jan 2009
    Posts
    715
    I think the key is  k \neq 1


    From  \frac{ a^{kp} -1 }{a^k  - 1}~ , a=10  ,  p is prime . we get

     \frac{(1 + a + a^2 + a^3 + ... + a^{p-1} ) (1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} ) }{ 1 + a + a^2 + a^3 + ... + a^{k-1}}

    If  p > k , then we have the inequality

     1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p}  >1 + a + a^2 + a^3 + ... + a^{p-1}   > 1 + a + a^2 + a^3 + ... + a^{k-1}

    For  \frac{ a^{kp} -1 }{a^k  - 1} to be prime , we must have

     1 + a + a^2 + a^3 + ... + a^{p-1}  = A ,

     1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p}   = BC

    and  1 + a + a^2 + a^3 + ... + a^{k-1}  = AB which gives  1 + a + a^2 + a^3 + ... + a^{k-1} > 1 + a + a^2 + a^3 + ... + a^{p-1} , a contradiction .

    Since  k is finite , it is impossible to find a prime in  \frac{ a^{kp} -1 }{a^k  - 1} for  p > k .

    ps: Oh , I have just realized that p is prime is unnecessary .
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    May 2010
    Posts
    7

    Unhappy

    Quote Originally Posted by simplependulum View Post
    For  \frac{ a^{kp} -1 }{a^k  - 1} to be prime , we must have

     1 + a + a^2 + a^3 + ... + a^{p-1}  = A ,

     1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p}   = BC

    and  1 + a + a^2 + a^3 + ... + a^{k-1}  = AB which gives  1 + a + a^2 + a^3 + ... + a^{k-1} > 1 + a + a^2 + a^3 + ... + a^{p-1} , a contradiction .
    I don't know why this should be (this A, B and C).
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Quote Originally Posted by bogdany View Post
    I don't know why this should be (this A, B and C).

    Forget about it

    We know
    <br />
\frac{(1 + a + a^2 + a^3 + ... + a^{p-1} ) (1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} ) }{ 1 + a + a^2 + a^3 + ... + a^{k-1}}<br />
    is an integer .

    Therefore, the denominator is divisible by the numerator .

    I let  1 + a + a^2 + a^3 + ... + a^{p-1} = AB

    and 1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} = CD

    as the product of two integers that one is cancelled by the numerator and one remains .

    Let 1 + a + a^2 + a^3 + ... + a^{k-1} = AC  or  AD , BC ,BD whatever you like .

    After the division ,we obtain the quotient  BD , if it is a prime , then either  B or  D is one , let  B=1 so we have 1 + a + a^2 + a^3 + ... + a^{k-1}  =  AC \geq A = AB = 1 + a + a^2 + a^3 + ... + a^{p-1}   , a contradiction because we always have <br />
1 + a^p + a^{2p} + a^{3p} + ... + a^{(k-1)p} >1 + a + a^2 + a^3 + ... + a^{p-1} > 1 + a + a^2 + a^3 + ... + a^{k-1}<br />
for  p>k so  B \neq 1 . Similar work on letting  D = 1 , we will have another contradiction so the quotient is not a prime for all  n > k .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursive sequence of primes
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 9th 2011, 07:44 AM
  2. Replies: 2
    Last Post: March 1st 2010, 12:57 PM
  3. recursive sequence
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 29th 2009, 06:15 AM
  4. Replies: 2
    Last Post: February 5th 2009, 09:07 PM
  5. [SOLVED] Recursive sequence induction proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 22nd 2008, 12:04 AM

Search Tags


/mathhelpforum @mathhelpforum