Infinitely many composite numbers

Printable View

January 2nd 2010, 06:58 AM
usagi_killer

Infinitely many composite numbers

Let http://alt1.artofproblemsolving.com/...ea377667b8.gif and http://alt2.artofproblemsolving.com/...bd49418f98.gif be positive integers and let the sequence http://alt2.artofproblemsolving.com/...fd0f8f56b2.gif be defined by http://alt1.artofproblemsolving.com/...6ebcf18b17.gif and http://alt1.artofproblemsolving.com/...774c64065a.gif for all non-negative integers http://alt2.artofproblemsolving.com/...00c274bdaa.gif. Prove that for any choice of http://alt1.artofproblemsolving.com/...ea377667b8.gif and http://alt2.artofproblemsolving.com/...bd49418f98.gif, the sequence http://alt1.artofproblemsolving.com/...26110acee0.gif 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.
January 2nd 2010, 08:11 AM
Drexel28

Quote:

Originally Posted by usagi_killer

Let http://alt1.artofproblemsolving.com/...ea377667b8.gif and http://alt2.artofproblemsolving.com/...bd49418f98.gif be positive integers and let the sequence http://alt2.artofproblemsolving.com/...fd0f8f56b2.gif be defined by http://alt1.artofproblemsolving.com/...6ebcf18b17.gif and http://alt1.artofproblemsolving.com/...774c64065a.gif for all non-negative integers http://alt2.artofproblemsolving.com/...00c274bdaa.gif. Prove that for any choice of http://alt1.artofproblemsolving.com/...ea377667b8.gif and http://alt2.artofproblemsolving.com/...bd49418f98.gif, the sequence http://alt1.artofproblemsolving.com/...26110acee0.gif 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?
January 2nd 2010, 09:30 AM
NonCommAlg

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!