Re: Number with 4k+1 prime.

On 10 25 , 10 57 , magi...@xxxxxxxxxxxxxxxxx (Arturo Magidin) wrote:
In article <ffq4hc$n4...@xxxxxxxxxxxxxxxx>,

mina_world <mina_wo...@xxxxxxxxxxx> wrote:
Hello sir~

Prove that there are infinitely many primes of the form 4k+1.

-----------------------------------------------------
1)
Suppose that there are finite primes of the form 4k+1.
Namely, q_1, q_2, ...., q_r

As in the proof that there are infinitely many primes, there is no
need to do this by contradiction. Simply show that given any finite
list of primes congruent to 1 modulo 4, there is a prime not on the
list that is also congruent to 1 modulo 4. That is what you do below
anyway.

Let N = [{2.(q_1).(q_2)....(q_r)}^2] + 1

so, N is odd.
so, p | N for some odd prime p.
so, [{2.(q_1).(q_2)....(q_r)}^2] + 1 = 0 (mod p)
so, [{2.(q_1).(q_2)....(q_r)}^2] = -1 (mod p)

Namely, -1 is a quadratic residue modulo p since (-1, p) = 1.

so, 1 = (-1 / p) = (-1)^{(p-1)/2}
so, (p-1)/2 = 2k
so, p = 4k + 1.

so, p in {q_1, q_2 ,..... ,q_r}
Since p | N, p | 1. contradiction.

Since p = 1 (mod q_i) for each i, p is not equal to q_i for any i...





2)
Lemma)
Suppose that p | (a^2) + 1 for some odd prime p and some integer a.
Then (a^2) + 1 = 0 (mod p)
so, a^2 = -1 (mod p)
so, a^4 = 1 (mod p)

so, the order of a is 1 or 2 or 4 modulo p.
1 and 2 are impossible.
so, the order of a is 4 modulo p.
so, 4 | (p-1) ---(***)
so, p = 4k + 1
-----------------------------------------------------
Suppose that there are finite primes of the form 4k+1.
Namely, q_1, q_2, ...., q_r

Let N = [{2.(q_1).(q_2)....(q_r)}^2] + 1

so, N is odd.
so, p | N for some odd prime p.
By lemma, p | N for p = 4k+1 form.
so, p | 1. contradiction.

As above. You can do this directly instead of by contradiction.

--------------------------------------------------------------

I can understand (1).
But I can't understand (***) of (2).

Consider the mutliplicative group of nonzero integers modulo p. It has
p-1 elements. Since a is of order 4 modulo p, that means that the
order of a in (Z_p)^* is 4. By Lagrange's Theorem, 4 must divide the
number of elements in (Z_p)^*, which is p-1. Thus, 4|p-1, which is
(***).

Because, I did not suppose the condition (a, p) = 1.

Of course you did. If p|a^2+1, then you must have (a,p)=1; otherwise,
p|1.

Even if I supposed the condition (a,p) =1,
I can't use this problem.
Because, I can't guarantee (2.(q_1).(q_2)....(q_r) , p) = 1.

Yes, you can. Since p| (2.(q_1)...(q_r))^2 + 1, you must have that p
is relatively prime to 2.(q_1)...(q_r). Otherwise, the prime p would
divide 1.

Oh, You're right.
Thank you very much for good advice. and hagman, too.

.