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 and .
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 , ... but the proof for the cases and were a bit longer, is there a possibility to generalize them for ?
I would be thankful for any help I can get.
Hello,
here's a little proof for you
Assume your arithmetic progression has form , , .
If and are not coprime, call their common divisor greater than one. Then
Which is obviously not prime (divisible by ).
Thus if and share a common divisor, the arithmetic progression does not contain any prime.
Now, if and 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 with and coprime. Thus the arithmetic progression contains infinitely many primes if and only if and are coprime.
Therefore, there are infinitely many primes in the arithmetic progression , , , if and only if and are coprime.
My previous proof makes this easy : since any arithmetic progression with contains infinitely many primes, there are infinitely many such progressions because there are infinitely many numbers , that are coprime (quick example : every power of two is coprime to an odd number, this can be shown fairly easily).but is it also possible to find a non-difficult proof that there are infinitely many a. p. with infinitely many primes?
We defined (non-trivial) arithmetic progressions as sequences
with
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?
Wanna prove Dirichlet's Theorem ? At least you would deserve to use itAny other suggestions to show that there are infinitely many a.p. containing infinitely many primes?
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
well, actually it's quite easy to prove that for any given integer , the arithmetic progression contains infinitely many prime numbers. here is a proof:
suppose are the only prime elements of and let (you might ask what if there's no prime in ? well, then we let ).
let be a prime divisor of clearly for all so we only need to prove that to get a contradiction. so we have and
thus therefore the order of modulo is but, by the Fermat's little theorem, we also have hence we
must have which means
much more generally, it's quite elementary and not hard at all to prove that, given any integer the arithmetic progression 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 for some such that and .
In we have .
Now suppose for some , then from above we see that has a double root which is impossible since (f(x) and f'(x) are relatively prime). This implies .
Note , otherwise .
Therefore for some .
Now let be monic, and suppose has only a finite amount of prime divisors . Choose such that .
Define such that .
since .
So we have for any .
Pick such that and let be a prime factor of .
This means and which is a contradiction to the hypothesis.
So looking back at what's been done... I've shown for any monic polynomial , there are an infinite amount of primes dividing . Also and .
Therefore contains an infinite amount of primes!
you didn't state this part properly. you proved that for any monic polynomial there are infinitely many primes dividing at least one element of the set anyway,
i would present the proof in this order: first i'd prove the above result. then i'd fix a positive integer then, since has a finite number of prime divisors, we conclude from our first result
that for any monic polynomial , there are an infinitely many primes which do not divide but divide at least one element of the set then i would prove that any
prime numer which does not divide but divides at least one element of the set is equivalent to modulo finally i'd put to finish the proof.