Primes in Arithmetic Progression

**EinStone** · February 16th 2010, 01:19 PM

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.

**icemanfan** · February 16th 2010, 02:46 PM

Originally Posted by EinStone

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.

**Bacterius** · February 16th 2010, 06:16 PM

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).

**EinStone** · February 17th 2010, 12:07 AM

Originally Posted by icemanfan

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$

Originally Posted by Bacterius

$\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?

**Bacterius** · February 17th 2010, 12:15 AM

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

**EinStone** · February 17th 2010, 12:39 AM

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.

**NonCommAlg** · February 17th 2010, 01:49 AM

Originally Posted by EinStone

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$

**EinStone** · February 17th 2010, 03:52 AM

Nice proof, I was looking for something like this.

**NonCommAlg** · February 17th 2010, 07:14 AM

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!

**chiph588@** · March 20th 2010, 08:07 PM

Originally Posted by NonCommAlg

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!

**NonCommAlg** · March 21st 2010, 10:58 PM

Originally Posted by chiph588@

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.

Thread: Primes in Arithmetic Progression

LinkBack

Thread Tools

Display

Primes in Arithmetic Progression

Similar Math Help Forum Discussions

Arithmetic Progression or Arithmetic Series Problem

Arithmetic Progression & Geometric Progression

Arithmetic Progression

arithmetic progression

Primes in Arithmetic Progression

Search Tags