Results 1 to 11 of 11

Math Help - Primes in Arithmetic Progression

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Primes in Arithmetic Progression

    Hey guys,
    in our NT course we have the topic arithmetic progressions and we had to prove that there are infinitely many primes in the progressions 4n + 3 and 4n + 1.

    Now the task says to find more arithmetic progressions containing infinitely primes. Our professor said at some point that every arithmetic progression(a. p.) contains infinitely many primes, but is it also possible to find a non-difficult proof that there are infinitely many a. p. with infinitely many primes? I thought about 8n + 1, 8n + 3 ... but the proof for the cases 4n + 1 and 4n + 3 were a bit longer, is there a possibility to generalize them for 2^k*n + 1?

    I would be thankful for any help I can get.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by EinStone View Post
    Our professor said at some point that every arithmetic progression(a. p.) contains infinitely many primes
    Then your professor was wrong. However, I would wager this:

    Any arithmetic progression whose terms are of the form pn + q with p, q coprime contains infinitely many primes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello,
    here's a little proof for you

    Assume your arithmetic progression has form x_n = an + b, a > 0, b > 0.

    \Rightarrow If a and b are not coprime, call d their common divisor greater than one. Then

    x_n = an + b = d \left ( \frac{an}{d} + \frac{b}{d} \right )

    Which is obviously not prime (divisible by d).
    Thus if a and b share a common divisor, the arithmetic progression does not contain any prime.

    \Rightarrow Now, if a and b are coprime. (do not mind what I wrote here before, there is something terribly wrong with it). Dirichlet's Theorem states that there are infinitely many primes of the form an + b with a and b coprime. Thus the arithmetic progression x_n = an + b contains infinitely many primes if and only if a and b are coprime.

    Therefore, there are infinitely many primes in the arithmetic progression x_n = an + b, a > 0, b > 0, if and only if a and b are coprime.

    but is it also possible to find a non-difficult proof that there are infinitely many a. p. with infinitely many primes?
    My previous proof makes this easy : since any arithmetic progression x_n = an + b with gcd(a, b) = 1 contains infinitely many primes, there are infinitely many such progressions because there are infinitely many numbers a, b that are coprime (quick example : every power of two is coprime to an odd number, this can be shown fairly easily).
    Last edited by Bacterius; February 16th 2010 at 07:42 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2009
    Posts
    169
    Quote Originally Posted by icemanfan View Post
    Then your professor was wrong. However, I would wager this:

    Any arithmetic progression whose terms are of the form pn + q with p, q coprime contains infinitely many primes.
    We defined (non-trivial) arithmetic progressions as sequences
    a_n = b*n + c with (c,b) = 1

    Quote Originally Posted by Bacterius View Post

    \Rightarrow Now, if a and b are coprime. (do not mind what I wrote here before, there is something terribly wrong with it). Dirichlet's Theorem states that there are infinitely many primes of the form an + b with a and b coprime. Thus the arithmetic progression x_n = an + b contains infinitely many primes if and only if a and b are coprime.
    The problem is that we are not allowed to use Dirichlets theorem, then the problem would be trivial.

    Any other suggestions to show that there are infinitely many a.p. containing infinitely many primes?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Any other suggestions to show that there are infinitely many a.p. containing infinitely many primes?
    Wanna prove Dirichlet's Theorem ? At least you would deserve to use it

    Seriously, I don't know if there is an easy way to prove that a nontrivial arithmetic sequence contains infinitely many primes I usually stick with theorems and their proofs ... But I'll think about it
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2009
    Posts
    169
    Well I proved it for 4n+1 and 4n+3, and it was kinda difficult, i thought many one can generalize this result to 2^k*n + 1, but I couldn't see how.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by EinStone View Post
    Well I proved it for 4n+1 and 4n+3, and it was kinda difficult, i thought many one can generalize this result to 2^k*n + 1, but I couldn't see how.
    well, actually it's quite easy to prove that for any given integer k \geq 1, the arithmetic progression A=\{2^k n + 1 \}_{n \geq 0} contains infinitely many prime numbers. here is a proof:

    suppose p_1, \cdots , p_r are the only prime elements of A and let m=(2p_1p_2 \cdots p_r)^{2^{k-1}} + 1 (you might ask what if there's no prime in A? well, then we let m=2^{2^{k-1}} + 1).

    let p be a prime divisor of m. clearly p \neq p_i, for all 1 \leq i \leq r. so we only need to prove that p \in A to get a contradiction. so we have (2p_1p_2 \cdots p_r)^{2^{k-1}} \equiv -1 \mod p and

    thus (2p_1p_2 \cdots p_r)^{2^k} \equiv 1 \mod p. therefore the order of  2p_1p_2 \cdots p_r modulo p is 2^k. but, by the Fermat's little theorem, we also have (2p_1p_2 \cdots p_r)^{p-1} \equiv 1 \mod p. hence we

    must have 2^k \mid p-1, which means p \in A. \ \Box
    Last edited by NonCommAlg; February 19th 2010 at 06:44 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Nov 2009
    Posts
    169
    Nice proof, I was looking for something like this.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    much more generally, it's quite elementary and not hard at all to prove that, given any integer k \geq 1, the arithmetic progression \{kn + 1 \}_{n \geq 0} contains infinitely many prime numbers. some basic

    knowledge of cyclotomic polynomials is needed for understanding the proof though. it'd make a nice undergrad level presentation in number theory!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by NonCommAlg View Post
    much more generally, it's quite elementary and not hard at all to prove that, given any integer k \geq 1, the arithmetic progression \{kn + 1 \}_{n \geq 0} contains infinitely many prime numbers. some basic

    knowledge of cyclotomic polynomials is needed for understanding the proof though. it'd make a nice undergrad level presentation in number theory!
    Proof: Consider  \Phi_m(a) for some  a \in \mathbb{N} such that  p\mid \Phi_m(a) and  p \not| m .

    In  \mathbb{F}_p we have  a^m-1=\prod_{d\mid m} \Phi_d(a) = 0 .
    Now suppose  a^d-1=0 for some  d\mid m , then from above we see that  x^m-1 has a double root which is impossible since  (x^m-1,mx^{m-1})=1 (f(x) and f'(x) are relatively prime). This implies  ord_p(a)=m .
    Note  p\not| m , otherwise  mx^{m-1} = 0 \implies (x^m-1,mx^{m-1})\neq 1.
    Therefore  m\mid p-1 \implies p=mk+1 for some  k\in \mathbb{N} .


    Now let  f(x)\in \mathbb{Z}[x] be monic, and suppose  \{f(a) | a\in \mathbb{N} \} has only a finite amount of prime divisors  p_1,p_2, \cdot\cdot\cdot, p_k . Choose  a such that  f(a)=c\neq 0 .

    Define  g(x) = c^{-1} f(a+cy) such that  y=p_1 p_2 \cdot\cdot\cdot p_k x .

     g(x)=c^{-1}\left(f(a)+f'(a)cy+\frac{f''(a)}{2}(cy)^2+\cdot\  cdot\cdot+\frac{f^{(n)}(a)}{n!}(cy)^n\right)
     =1+f'(a)y+\frac{f''(a)}{2}cy^2+\cdot\cdot\cdot+\fr  ac{f^{(n)}(a)}{n!}c^{n-1}y^n \in \mathbb{Z}[x] since  \frac{f^{(n)}(a)}{n!} \in \mathbb{Z} .
    So we have  g(b)\equiv 1 \mod{p_1p_2\cdot\cdot\cdot p_k} for any  b\in \mathbb{Z} .
    Pick  b such that  |g(b)|>1 and let  p be a prime factor of  g(b) .
    This means  p\neq p_i and  p\mid f(a+cp_1p_2\cdot\cdot\cdot p_kb) which is a contradiction to the hypothesis.



    So looking back at what's been done... I've shown for any monic polynomial  f(x)\in\mathbb{Z}[x] , there are an infinite amount of primes dividing  f(x) . Also  p\mid \Phi_m(a) and  p\not| m \implies p\equiv 1 \mod{m} .

    Therefore  \{mk+1|k\in\mathbb{Z}\} contains an infinite amount of primes!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by chiph588@ View Post

    So looking back at what's been done... I've shown for any monic polynomial  f(x)\in\mathbb{Z}[x] , there are an infinite amount of primes dividing  f(x)
    you didn't state this part properly. you proved that for any monic polynomial f(x) \in \mathbb{Z}[x] there are infinitely many primes dividing at least one element of the set \{f(1), f(2), \cdots \}. anyway,

    i would present the proof in this order: first i'd prove the above result. then i'd fix a positive integer m. then, since m has a finite number of prime divisors, we conclude from our first result

    that for any monic polynomial  f(x)\in\mathbb{Z}[x] , there are an infinitely many primes which do not divide m but divide at least one element of the set \{f(1), f(2), \cdots \}. then i would prove that any

    prime numer which does not divide m but divides at least one element of the set \{\Phi_m(1), \Phi_m(2), \cdots \} is equivalent to 1 modulo m. finally i'd put f(x)=\Phi_m(x) to finish the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Arithmetic Progression or Arithmetic Series Problem
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: October 8th 2009, 01:36 AM
  2. Replies: 8
    Last Post: March 23rd 2009, 08:26 AM
  3. Arithmetic Progression
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 14th 2008, 10:11 AM
  4. arithmetic progression
    Posted in the Algebra Forum
    Replies: 4
    Last Post: April 22nd 2007, 11:56 AM
  5. Primes in Arithmetic Progression
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 22nd 2005, 09:19 AM

Search Tags


/mathhelpforum @mathhelpforum