# 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!
All times are GMT -8. The time now is 03:13 PM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 16, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8581963777542114, "perplexity_flag": "middle"}