Results 1 to 3 of 3

Thread: Infinitely many composite numbers

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    310

    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
    22
    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 $\displaystyle \gcd(a,b) = 1.$ suppose that the claim is false. so there exists some $\displaystyle \ell \in \mathbb{N}$ such that $\displaystyle x_k$ is prime for all $\displaystyle k \geq \ell.$

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

    choose $\displaystyle m=p$ and if $\displaystyle r > 1,$ choose $\displaystyle m=p-1.$ see that $\displaystyle 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: Nov 25th 2011, 01:52 AM
  2. [SOLVED] Prove there are infinitely many daffodil numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Jun 16th 2011, 06:08 PM
  3. Composite numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 6th 2010, 11:44 PM
  4. Prove that p divides infinitely many numbers...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 28th 2010, 04:55 PM
  5. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 19th 2007, 07:41 AM

Search Tags


/mathhelpforum @mathhelpforum