Results 1 to 3 of 3

Math Help - Infinitely many composite numbers

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    Infinitely many composite numbers

    Let and be positive integers and let the sequence be defined by and for all non-negative integers . Prove that for any choice of and , the sequence contains infinitely many composite numbers.

    How do I do this question? I just started self-learning number theory as recreation so yeah if anyone can show me how to solve it, I would really appreciate it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by usagi_killer View Post
    Let and be positive integers and let the sequence be defined by and for all non-negative integers . Prove that for any choice of and , the sequence contains infinitely many composite numbers.

    How do I do this question? I just started self-learning number theory as recreation so yeah if anyone can show me how to solve it, I would really appreciate it.
    I understand that you are doing mathematics recreationaly and that you just want to see the solution so that you better understand the topic, but that being said I would like to quote the mathematician George Simmons: "Despite our vast advances in mathematics, nothing has replaced the necessity of problem solving."

    So, what have you tried?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    note that the sequence is strictly increasing and also we may assume that \gcd(a,b) = 1. suppose that the claim is false. so there exists some \ell \in \mathbb{N} such that x_k is prime for all k \geq \ell.

    choose k \geq \ell large enough so that x_k=p > 2. see that p \nmid a and x_{k+m}=a^mp + (a^{m-1} + \cdots + a + 1)b, for all integers m \geq 1. let a \equiv r \mod p, where 1 \leq r \leq p-1. now, if r=1,

    choose m=p and if r > 1, choose m=p-1. see that p \mid x_{k+m}, which is a contradiction.


    Note: i left a couple of thing for the OP to discover, so Drexel28 wouldn't get too mad at me!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: November 25th 2011, 02:52 AM
  2. [SOLVED] Prove there are infinitely many daffodil numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: June 16th 2011, 07:08 PM
  3. Composite numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 7th 2010, 12:44 AM
  4. Prove that p divides infinitely many numbers...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 28th 2010, 05:55 PM
  5. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2007, 08:41 AM

Search Tags


/mathhelpforum @mathhelpforum