Intereting Posts

Prove $\lim\limits_{n \to \infty} \sqrt{X_n} = \sqrt{\lim\limits_{n \to \infty} X_n}$, where $\{X_n\}_{n=1}^\infty$ converges
From natural log to log base 10
Example of a model in set theory where the axiom of extensionality does not hold?
Is inverse matrix convex?
Why weak law of large number still alive?
How $a+bi$ becomes $\left(\matrix{a & -b\\b & a}\right)$?
$\mathbb{Z} \times \mathbb{Z}$ is cyclic.
Uniform $L^p$ bound on finite measure implies uniform integrability
Why can't this number be written as a sum of three squares of rationals?
Normal Subgroups that Intersect Trivially
Alternative solution to $\cos\frac{2\pi}{17}$
Given several integrals calculate $\int\limits_5^6 f(x) dx$
Is the closure of $ X \cap Y$ equal to $\bar{X} \cap \bar{Y}$?
Necessary and sufficient condition that a localization of an integral domain is integrally closed
Show that this set is linearly independent

Question: Are there infinitely many primes of the form 4n+3 and 4n-1?

My attempt: Suppose the contrary that there exists finitely many primes of the form 4n+3, say k+1 of them: 3,$p_1,p_2,….,p_k$

Consider $N$ = 4$p_1p_2p_3…p_k$+3 $N$ cannot be a prime of this form. So suppose that $N$=$q_1…q_r$ where $q_i∈P$

- integer $m$ has primitive root if and only if the only solutions of the congruence $x^{2} \equiv 1 \pmod m$ are $x \equiv \pm 1\pmod m$.
- Confused by proof of the irrationality of root 2: if $p^2$ is divisible by $2$, then so is $p$.
- Modular Inverses
- Can two perfect squares average to a third perfect square?
- How to solve $(2x^2-1)^2=2y^2 - 1$ in positive integers?
- Integral solutions to $1\times2+2\times3+\cdots+m\times(m+1)=n\times(n+1)$.

Claim: At least one of the $q_i$’s is of the form 4n+3:

Proof for my claim: $N$ is odd => $q_1,…,q_r$ are odd => $q_i$ ≡ 1 (mod 4) or $q_i# ≡ 3 (mod 4)

If all $q_1,…q_r$ are of the form 4n+1, then (4n+1)(4m+1)=16nm+4n+4m+1 = 4() +1

Therefore, $N=q_1…q_r$ = 4m+1. But $N=4p_1..p_k$+3 i.e. $N$≡3 (mod 4), N is congruent to 1 mod 4 which is a contradiction.

Therefore, at least one of $q_i$ ≡ 3 (mod 4). Suppose $q_j$ ≡ 3 (mod 4)

=> $q_j=p_i$ for some 1$\leq$i $\leq$ k or $q_j$ =3

If $q_j=p_i≠3$ then $q_j$ | $N$ = 4$p_1…p_k$ + 3 => $q_j$=3 Contradiction!

If $q_j$=3 (≠$p_i$ , 1$\leq$i $\leq$ k) then $q_j$ | $N$ = 4$p_1…p_k$ + 3 => $q_j=p_t$ for some 1$\leq$i $\leq$ k Contradiction!

In fact, there must be also infinitely many primes of the form 4n+1 (according to my search), but the above method does not work for its proof. I could not understand why it does not work. Could you please show me?

Regards

- For $n \in \mathbb{N}$ $\lfloor{\sqrt{n} + \sqrt{n+1}\rfloor} = \lfloor{\sqrt{4n+2}\rfloor}$
- Determination of the last two digits of $777^{777}$
- Density of products of a certain set of primes
- Determine whether a number is prime
- When is $5n^2+14n+1$ a perfect square?
- How to prove there are no solutions to $a^2 - 223 b^2 = -3$.
- Prove that $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$
- Inductive proof of the identity $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$
- $A \in M_3(\mathbb Z)$ be such that $\det(A)=1$ ; then what is the maximum possible number of entries of $A$ that are even ?
- What's the formula for the fixed point of a power tower of $2$s modulo $n$?

Suppose $n>1$ is an integer. We define $N=(n!)^2 +1$. Suppose $p$

is the smallest prime divisor of $N$. Since $N$ is odd, $p$ cannot

be equal to $2$. It is clear that $p$ is bigger than $n$

(otherwise $p \mid 1$). If we show that $p$ is of the form

$4k+1$ then we can repeat the procedure replacing $n$ with $p$

and we produce an infinite sequence of primes of the form $4k+1$.

We know that $p$ has the form $4k+1$ or $4k+3$. Since $p\mid N$

we have $$ (n!)^2 \equiv -1 \ \ (p) \ . $$ Therefore $$

(n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \ \ (p) \ . $$

Using Fermat’s little Theorem we get $$ (-1)^{ \frac{p-1}{2} } \equiv 1 \ \ (p) \ . $$

If $p$ was of the form $4k+3$ then $\frac{p-1}{2} =2k+1$ is odd

and therefore we obtain $-1 \equiv 1 \ \ (p)$ or $p \mid 2$ which

is a contradiction since $p$ is odd.

There’s indeed another elementary approach:

For every even $n$, all prime divisors of $n^2+1$ are $ \equiv 1 \mod 4$. This is because any $p\mid n^2+1$ fulfills $n^2 \equiv -1 \mod p$ and therefore $\left( \frac{-1}{p}\right) =1$, which is, since $p$ must be odd, equivalent to $p \equiv 1 \mod 4$.

Assume that there are only $k$ primes $p_1,…,p_k$ of the form $4m+1$. Then you can derive a contradiction from considering the prime factors of $(2p_1…p_k)^2+1$.

(There’s also an elementary approach to show that there are infinitely many primes congruent to $1$ modulo $n$ for every $n$, but that one gets rather tedious. (See: Wikipedia as a reference.))

Suppose that there are only fitely many primes of the form $4k+1$, say $p_{1}, …, p_{n}$, and consider $N =(p_{1} …p_{n})^{2}+ 1$. $N>p_{i}$, for $1 ≤i≤n$, hence $N$ cannot be prime. Any number of the form $a^{2}+1 $ has, except possibly for the factor $2$, only prime factors of the form $4m+1$.Since division into $N$ by each prime factor of the form $4k+1$ leaves a remainder $1$, $N$ cannot be composite, a contradiction. Hence, the number of primes of the form $4k +1$ must be infinite.

Actually there is an even more elegant proof that shows that this holds true for **all** primes>2:

∀ primes,p ∈P & p>2,∃ k∈Q| k=(p-1)/4 or k= (p+1)/4

Proof:

By definition every 4th integer, k ≥ 4, must have 2^2 (2 squared) as a factor. This means that every other even integer > 2 must have 2^2 as a factor.

For all primes p>2, the prime itself is odd and therefore p-1 and p+1 are both even.

Since p-1 and p+1 represent consecutive even integers, one and only one of them must have 2^2 as factors and thus (p±1)/4 is an integer. ∎

This applies to all primes greater than 2.

- Verify this identity: $\sin x/(1 – \cos x) = \csc x + \cot x$
- Probability that sum of rolling a 6-sided die 10 times is divisible by 10?
- Exercise from Stein with partial differential operator
- Is the unit sphere in $(C, \| \cdot\|_1)$ compact?
- Pigeonhole Principle to Prove a Hamiltonian Graph
- If $n\ge2$, Prove $\binom{2n}{3}$ is even.
- Different methods of evaluating $\int\sqrt{a^2-x^2}dx$:
- Functional completeness of $\{\text{or},\text{ xor}, \text{ xnor}\}$
- Proving by strong induction that $\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)…(n+d-1) $
- Understanding the definition of completeness of formal theorys(and Godel's famous theorem)
- How to prove $\inf(S)=-\sup(-S)$?
- What can be computed by axiomatic summation?
- Decomposition by subtraction
- Intuition behind curl identity
- Weak closure of $\{\sqrt n e_n|n\in \mathbb N\}$ and metrizability of weak topology