Competition problem — Number theory

Library / /314 of 520

Number theory Difficulty 6.2 National olympiad Prove it

6. Let the prime $p$ be an odd number. Prove:
(i) When $p=4 m+3$ , for any integer $a$ we have $a^{2} \equiv -1(\bmod p)$ ;
(ii) When $p=4 m+1$ , there exists $a$ such that $a^{2} \equiv -1(\bmod p)$ ;
(iii) There are infinitely many primes of the form $4 m+1$ .

Solution

6. (i) By contradiction. Consider $i j \equiv -1 \pmod{p}, 1 \leqslant i, j \leqslant p-1$ . If there exists $i=j=i_{0}$ such that $i_{0}^{2} \equiv -1 \pmod{p}$ , such $i_{0} (1 \leqslant i_{0} \leqslant p-1)$ exists exactly two. This implies $(p-1)! \equiv 1 \pmod{p}$ , which contradicts Theorem 1;
(ii) See Example 2;
(iii) Let $p_{1}, \cdots, p_{r}$ all be primes of the form $4 m+1$ . Consider the prime factors of $\left(2 p_{1} \cdots p_{r}\right)^{2}+1$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.