Struggling to understand proofs involving modules.

Question

Currently, I am faced with solving the following proof(s).

Lemma 1: If n ≡ 3 mod 4 then n has a prime divisor p for which p ≡ 3 mod 4.

Lemma 2: If p ≡ 3 mod 4 then p cannot divide n and n + 2 for any n.

Lemma 3: If p_1...p_k are all primes congruent to 3 mod 4 then N = p_1^2 * p_2^2....p_k^2 is congruent to 1 mod 4.

Theorem: There are infinitely many primes congruent to 3 mod 4.

I am not looking for direct answers, this is something I wish to be able to understand better and solve on my own.

Although I am struggling to understand what it means for n ≡ 3 mod 4. On top of that concept, I also don't quite understand the following statement: n ≡ 3 mod 4 means 4 | n - 3, so there exists a k such that n - 3 = 4k.

The big concepts I think I'm failing to understand properly are congruence and congruence classes. So anything having to do with the following notation: "≡".

The help is much appreciated!

Answer 1

The notation $a \equiv b \pmod n$ means "$a$ and $b$ have a relationship with each other". And the relationship the have in common is: If you consider integers by whether they are or are not divisible by $n$ and if they are not divisible by $n$ the by what "offset" their remainders are, then $a$ and $b$ are both such "divisible by $n$" characteristic.

In other words $a \equiv b \pmod n$ means each of the following

i) $a$ and $b$ have the same remainder when divided by $n$. That is $a = r + n*k$ for some integer $k$ and $0 \le r < n$ and $b = r + n*j$ for some integer $j$ and the exact same $r$.

ii) $a = b + m*n$ for some integer $m$. This is the exact same statement as i) because if $a = r + n*k$ and $b = r + n*j$ then $a = b + n*(k-j)=b + n*m$ for $m = k-j$.

iii) $n$ divides $a-b$ evenly. This is the exact same statement as i) and ii) because if $a = r + n*k$ and $b = r + n*j$ and $a = b + n*m$ then $a-b = n*(k -j)=n*m$ and $n$ divides into $a-b$ evenly.

So

$n \equiv 3\pmod 4$ means by definition that there is an integer $k$ so that $n = 3+ 4k$. If $k = ..... -2, -1, 0, 1,2,3,4, .....$ then $n = ..... -5, -1, 3, 7, 11, 15, 19, .....$. And that means $n-3 = ..... -8, -4, 0, 4, 8, 12, 16, ....$ and that $4|n-3$ because $4$ does divide $...... -8, -4, 0, 4, 8, 12, 16,, ...$ and $\frac {n-3}4$ is the integer $...... -2, -1, 0, ,1, 2, 3, 4,.....$

So $n \equiv 3 \pmod 4$ means

i). That when $n$ is divide by $4$ the remainder will be $3$.

ii). That $n = 3 + 4k$ for some integer $k$.

iii). Then $\frac {n-3}4= k$ for some integer $k$.

iv) That $n \in \{....., -8, -5, -1, 3, 7, 1, 15, 19, ....\}$.

Those four statements are exactly the same.

So...

So lemma 1:

If $n \equiv 3 \pmod 4$ then it has a prime divisor of the form $p \equiv 3 \pmod 4$.

That means if $n$ is number of the form $n = 3 + 4k$ (for example: $55 \equiv 3 \pmod 4$ because $55 = 3 + 13*4$) then it will also have a prime factor of the form $p = 3+4j$. And, indeed, the prime factors of $55$ are $5$ and $11$ and $11 \equiv 3 \pmod 4$ because $11 = 3 + 4*2$.

Okay, to prove it:

One: $n$ must have prime divisors.

Two: If $p$ is a prime divisor then $p$ when divided by $4$ must have a remainder. It could be that the remainder would be $0, 1,2$ or $3$. In other words exactly one of the following is true: $p \equiv 0\pmod 4$ or $p \equiv 1 \pmod 4$ or $p \equiv 2 \pmod 3$ or $p \equiv 3 \pmod 4$. (This is true for any integer.)

Three: if $p\equiv 0 \pmod 4$ then $p = 0 + 4k$ for some integer $k$ so $p = 4k$. This is impossible because $p$ is prime.

if $p\equiv 2 \pmod 4$ then $p = 2 + 4k$ for some integer $k$. So $p$ is even. But $p$ is prime and $2$ is the only even prime so $p = 2$. But $n\equiv 3 \mod 4$ so $n = 3 + 4m$ for some $m$ so $n$ is odd. So $p \ne 2$. So this is impossible.

So there are only two possible options. $p \equiv 1 \pmod 4$ or $p \equiv 3 \pmod 4$.

Four If $n$ has NO prime factors so that $p \equiv 3 \pmod 4$ then that would mean that ALL of the prime factors of $n$ would all be so that $p\equiv 1 \pmod 4$.

Prove that that is impossible.

Hint: If $a \equiv 1 \pmod 4$ and $b \equiv 1 \pmod 4$ then $a = 1 + 4k$ and $b = 1 + 4j$ for some $j$ and $k$. So $ab = (1+4k)(1 + 4j) = 1 + 4k + 4j + 16jk$. So $ab \equiv 1 \pmod 4$.

Answer 2

Welcome to MSE Aleksei. Nice question!

Okay first, what does $n\equiv 3\mod 4$ mean?

You might remember from your early education be taught division using remainders.

For instance: "$7 \text{ divided by } 2 \text{ is } 3 \text{ remainder } 1$". This is because $7=(1\times 4) +3$

Mod notation works very similarly to this, we say that $n\equiv 3\mod 4$ if: $$n \text{ divided by } 4 \text{ is something remainder } 3$$

If we call the 'something' $k$, then we have $n=4k+3$ (use my number example if you don't see how).

You can rearrange that statement to see the other equalities.

$4 | (n-3)$ means $4 \text{ divides } (n-3)$, so for example $4|8$ is true because $4$ is a factor of $8$.

The use of the $\equiv$ symbol as opposed to the $=$ I don't understand personally, but it's the common notation.

Now for the Lemmas:

The first one states that every $n$ that meets $n=4k+3$ (for integer $k$) has a prime factor $p=4q+3$ (for integer $q$). If $n$ is prime, this is trivial, as $n=p$

To prove this Lemma, note that any odd number is of either the form $4k+1$ or $4k+3$ (for integer $k$) and that a non-prime odd number has two odd factors. You should be able to take it from there.

---

The second one states that $\frac{n(n+2)}{4k+3}$ cannot be an integer. My hint to you is that since $n(n+2)$ is even, and $4k+3$ is odd, the result of this division must be even.

---

The third one states that for: $$p_r=4k_r+3$$ $$p_1^2\cdot p_2^2\cdot...\cdot p_n^2=4t+1$$ Notice: $$(4k_r+3)(4k_r+3)=16k_r^2+24k_r+9=4(4k_r^2+6k_r+2)+1$$ which is of the form $4a_r+1$. So the expression becomes:

$$(4a_1+1)(4a_2+1)(...)(4a_n+1)$$

---

For the theorem, just assume there is a maximum prime $P$, and then show a bigger one can be made using it.

Hint: $(4a+3)(4b+3)(4c+3)=4d+3$ $(\text{for }a,b,c,d \in \Bbb Z)$