Question

Show that any positive number of the form 4n-1 is divisible by a prime of the same form.

Answer 1

We know that there are primes of the form 2, or of the form

Primes of the form don't exist (except 2 which is a prime of the form and the only one of this sort)

Let be any number and let its prime factorization be where are all primes

If none of these primes are of the form they must either be 2 or of the form

Note that

If one of them is 2 then for

This means can possibility only be

But is modulo 4

So this contradicts our assumption that none of the primes in the prime factorization are of the form

So that every number of the form must have a prime factor of the same form