Re: Number with 4k+1 prime.

In article <ffq4hc$n4g$1@xxxxxxxxxxxxxxxx>,
mina_world <mina_world@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.


--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... What's the difference between primes in sequences and above? ... for those primes congruent 1 mod 3. ...
    (sci.math)
  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... What's the difference between primes in sequences and above? ... for those primes congruent 1 mod 3. ...
    (sci.math)
  • Re: About random, primes and statistics
    ... explain a simple area where mathematicians routinely ... modulo 3--perfect regularity: ... researchers as you have primes and you have ... composites and composites ...
    (sci.math)
  • Re: Quadratic residue method for finding primes
    ... Note that we know exactly which primes have 2 as a quadratic residue: ... those which are congruent to 1 or -1 modulo 8. ...
    (sci.crypt)
  • Re: Requesting some help
    ... invertibility modulo e or modulo n. ... to get the RSA-decryptions of smooth primes, ... "Smooth primes" here means small primes below some smoothness bound, ... keep the same number of columns of this; if you can invert ...
    (sci.crypt)