My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
July 4th, 2009, 07:46 AM   #1
Senior Member
 
Joined: Jan 2009
From: Russia

Posts: 113
Thanks: 0

Primes inside the arithmetic progression

Prove that among progression

3, 7, 11, 15, 19, ...

there is infinitely many primes.
lime is offline  
 
July 4th, 2009, 09:23 AM   #2
Senior Member
 
Joined: Jun 2009

Posts: 150
Thanks: 0

Re: Primes inside the arithmetic progression

Call such a number "3 mod 4" ... the rest of the odd numbers are "1 mod 4" ... Note that the product of two "1 mod 4" numbers is again a "1 mod 4" number.
If there were no "3 mod 4" primes, then there could be no "3 mod 4" numbers at all. A contradiction. Therefore, there is at least one "3 mod 4" prime. (By itself, this is not very useful, because we can easily write down such a prime.) Now: soup up that argument: assume there are only finitely many "3 mod 4" primes, then get a contradiction from that.
g_edgar is offline  
July 4th, 2009, 09:29 AM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Primes inside the arithmetic progression

It's not hard to modify Euclid's theorem to work in this case. Suppose that the only primes of this form are 3, 7, ..., k. Take their product and add 4. Can this be divisible by any of the numbers on your list? Can it be the product of primes = 1 mod 4?
CRGreathouse is offline  
July 5th, 2009, 05:40 AM   #4
Senior Member
 
Joined: Jan 2009
From: Russia

Posts: 113
Thanks: 0

Re: Primes inside the arithmetic progression

Quote:
Suppose that the only primes of this form are 3, 7, ..., k. Take their product ...
That's exactly the way I started with.
Quote:
and add 4.
Actually, I will need to add 4 or 2 depending on the product. Won't I?
Quote:
Can this be divisible by any of the numbers on your list?
No way.
Quote:
Can it be the product of primes = 1 mod 4?
Here I'm stuck.
lime is offline  
July 5th, 2009, 08:59 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Primes inside the arithmetic progression

Quote:
Originally Posted by lime
Actually, I will need to add 4 or 2 depending on the product. Won't I?
Good catch.

Quote:
Originally Posted by lime
Quote:
Can it be the product of primes = 1 mod 4?
Here I'm stuck.
Does 1 * 1 = 3 (mod 4)?
CRGreathouse is offline  
July 5th, 2009, 09:52 AM   #6
Senior Member
 
Joined: Jan 2009
From: Russia

Posts: 113
Thanks: 0

Re: Primes inside the arithmetic progression

Can't believe I was so silly. Thanks!
lime is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
arithmetic, inside, primes, progression



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
arithmetic progression will.i.am1 Algebra 14 May 29th, 2013 06:27 AM
arithmetic progression will.i.am1 Algebra 1 May 27th, 2013 02:23 PM
Arithmetic Progression Daksh Algebra 3 November 22nd, 2012 09:08 PM
Arithmetic progression Algebra 2 April 5th, 2012 09:46 PM
Arithmetic Progression Trafford99 Algebra 7 February 28th, 2012 03:07 PM





Copyright © 2019 My Math Forum. All rights reserved.