# Metamath Proof Explorer

## Theorem 31prm

Description: 31 is a prime number. In contrast to 37prm , the proof of this theorem is not based on the "blanket" prmlem2 , but on isprm7 . Although the checks for non-divisibility by the primes 7 to 23 are not needed, the proof is much longer (regarding size) than the proof of 37prm (1810 characters compared with 1213 for 37prm ). The number of essential steps, however, is much smaller (138 compared with 213 for 37prm ). (Contributed by AV, 17-Aug-2021) (Proof modification is discouraged.)

Ref Expression
Assertion 31prm ${⊢}31\in ℙ$

### Proof

Step Hyp Ref Expression
1 2z ${⊢}2\in ℤ$
2 3nn0 ${⊢}3\in {ℕ}_{0}$
3 1nn0 ${⊢}1\in {ℕ}_{0}$
4 2 3 deccl ${⊢}31\in {ℕ}_{0}$
5 4 nn0zi ${⊢}31\in ℤ$
6 3nn ${⊢}3\in ℕ$
7 2nn0 ${⊢}2\in {ℕ}_{0}$
8 2re ${⊢}2\in ℝ$
9 9re ${⊢}9\in ℝ$
10 2lt9 ${⊢}2<9$
11 8 9 10 ltleii ${⊢}2\le 9$
12 6 3 7 11 declei ${⊢}2\le 31$
13 eluz2 ${⊢}31\in {ℤ}_{\ge 2}↔\left(2\in ℤ\wedge 31\in ℤ\wedge 2\le 31\right)$
14 1 5 12 13 mpbir3an ${⊢}31\in {ℤ}_{\ge 2}$
15 elun ${⊢}{n}\in \left(\left(\left\{2,3\right\}\cap ℙ\right)\cup \left(\left\{4,5\right\}\cap ℙ\right)\right)↔\left({n}\in \left(\left\{2,3\right\}\cap ℙ\right)\vee {n}\in \left(\left\{4,5\right\}\cap ℙ\right)\right)$
16 elin ${⊢}{n}\in \left(\left\{2,3\right\}\cap ℙ\right)↔\left({n}\in \left\{2,3\right\}\wedge {n}\in ℙ\right)$
17 vex ${⊢}{n}\in \mathrm{V}$
18 17 elpr ${⊢}{n}\in \left\{2,3\right\}↔\left({n}=2\vee {n}=3\right)$
19 0nn0 ${⊢}0\in {ℕ}_{0}$
20 2cn ${⊢}2\in ℂ$
21 20 mul02i ${⊢}0\cdot 2=0$
22 1e0p1 ${⊢}1=0+1$
23 2 19 21 22 dec2dvds ${⊢}¬2\parallel 31$
24 breq1 ${⊢}{n}=2\to \left({n}\parallel 31↔2\parallel 31\right)$
25 23 24 mtbiri ${⊢}{n}=2\to ¬{n}\parallel 31$
26 3ndvds4 ${⊢}¬3\parallel 4$
27 2 3 3dvdsdec ${⊢}3\parallel 31↔3\parallel \left(3+1\right)$
28 3p1e4 ${⊢}3+1=4$
29 28 breq2i ${⊢}3\parallel \left(3+1\right)↔3\parallel 4$
30 27 29 bitri ${⊢}3\parallel 31↔3\parallel 4$
31 26 30 mtbir ${⊢}¬3\parallel 31$
32 breq1 ${⊢}{n}=3\to \left({n}\parallel 31↔3\parallel 31\right)$
33 31 32 mtbiri ${⊢}{n}=3\to ¬{n}\parallel 31$
34 25 33 jaoi ${⊢}\left({n}=2\vee {n}=3\right)\to ¬{n}\parallel 31$
35 18 34 sylbi ${⊢}{n}\in \left\{2,3\right\}\to ¬{n}\parallel 31$
36 35 adantr ${⊢}\left({n}\in \left\{2,3\right\}\wedge {n}\in ℙ\right)\to ¬{n}\parallel 31$
37 16 36 sylbi ${⊢}{n}\in \left(\left\{2,3\right\}\cap ℙ\right)\to ¬{n}\parallel 31$
38 elin ${⊢}{n}\in \left(\left\{4,5\right\}\cap ℙ\right)↔\left({n}\in \left\{4,5\right\}\wedge {n}\in ℙ\right)$
39 17 elpr ${⊢}{n}\in \left\{4,5\right\}↔\left({n}=4\vee {n}=5\right)$
40 eleq1 ${⊢}{n}=4\to \left({n}\in ℙ↔4\in ℙ\right)$
41 4nprm ${⊢}¬4\in ℙ$
42 41 pm2.21i ${⊢}4\in ℙ\to ¬{n}\parallel 31$
43 40 42 syl6bi ${⊢}{n}=4\to \left({n}\in ℙ\to ¬{n}\parallel 31\right)$
44 1nn ${⊢}1\in ℕ$
45 1lt5 ${⊢}1<5$
46 2 44 45 dec5dvds ${⊢}¬5\parallel 31$
47 breq1 ${⊢}{n}=5\to \left({n}\parallel 31↔5\parallel 31\right)$
48 46 47 mtbiri ${⊢}{n}=5\to ¬{n}\parallel 31$
49 48 a1d ${⊢}{n}=5\to \left({n}\in ℙ\to ¬{n}\parallel 31\right)$
50 43 49 jaoi ${⊢}\left({n}=4\vee {n}=5\right)\to \left({n}\in ℙ\to ¬{n}\parallel 31\right)$
51 39 50 sylbi ${⊢}{n}\in \left\{4,5\right\}\to \left({n}\in ℙ\to ¬{n}\parallel 31\right)$
52 51 imp ${⊢}\left({n}\in \left\{4,5\right\}\wedge {n}\in ℙ\right)\to ¬{n}\parallel 31$
53 38 52 sylbi ${⊢}{n}\in \left(\left\{4,5\right\}\cap ℙ\right)\to ¬{n}\parallel 31$
54 37 53 jaoi ${⊢}\left({n}\in \left(\left\{2,3\right\}\cap ℙ\right)\vee {n}\in \left(\left\{4,5\right\}\cap ℙ\right)\right)\to ¬{n}\parallel 31$
55 15 54 sylbi ${⊢}{n}\in \left(\left(\left\{2,3\right\}\cap ℙ\right)\cup \left(\left\{4,5\right\}\cap ℙ\right)\right)\to ¬{n}\parallel 31$
56 indir ${⊢}\left(\left\{2,3\right\}\cup \left\{4,5\right\}\right)\cap ℙ=\left(\left\{2,3\right\}\cap ℙ\right)\cup \left(\left\{4,5\right\}\cap ℙ\right)$
57 55 56 eleq2s ${⊢}{n}\in \left(\left(\left\{2,3\right\}\cup \left\{4,5\right\}\right)\cap ℙ\right)\to ¬{n}\parallel 31$
58 5nn0 ${⊢}5\in {ℕ}_{0}$
59 5re ${⊢}5\in ℝ$
60 5lt9 ${⊢}5<9$
61 59 9 60 ltleii ${⊢}5\le 9$
62 2lt3 ${⊢}2<3$
63 7 2 58 3 61 62 decleh ${⊢}25\le 31$
64 6nn ${⊢}6\in ℕ$
65 1lt6 ${⊢}1<6$
66 2 3 64 65 declt ${⊢}31<36$
67 4 nn0rei ${⊢}31\in ℝ$
68 0re ${⊢}0\in ℝ$
69 9pos ${⊢}0<9$
70 68 9 69 ltleii ${⊢}0\le 9$
71 6 3 19 70 declei ${⊢}0\le 31$
72 67 71 pm3.2i ${⊢}\left(31\in ℝ\wedge 0\le 31\right)$
73 flsqrt5 ${⊢}\left(31\in ℝ\wedge 0\le 31\right)\to \left(\left(25\le 31\wedge 31<36\right)↔⌊\sqrt{31}⌋=5\right)$
74 73 bicomd ${⊢}\left(31\in ℝ\wedge 0\le 31\right)\to \left(⌊\sqrt{31}⌋=5↔\left(25\le 31\wedge 31<36\right)\right)$
75 72 74 ax-mp ${⊢}⌊\sqrt{31}⌋=5↔\left(25\le 31\wedge 31<36\right)$
76 63 66 75 mpbir2an ${⊢}⌊\sqrt{31}⌋=5$
77 76 oveq2i ${⊢}\left(2\dots ⌊\sqrt{31}⌋\right)=\left(2\dots 5\right)$
78 5nn ${⊢}5\in ℕ$
79 78 nnzi ${⊢}5\in ℤ$
80 3z ${⊢}3\in ℤ$
81 1 79 80 3pm3.2i ${⊢}\left(2\in ℤ\wedge 5\in ℤ\wedge 3\in ℤ\right)$
82 3re ${⊢}3\in ℝ$
83 8 82 62 ltleii ${⊢}2\le 3$
84 3lt5 ${⊢}3<5$
85 82 59 84 ltleii ${⊢}3\le 5$
86 83 85 pm3.2i ${⊢}\left(2\le 3\wedge 3\le 5\right)$
87 elfz2 ${⊢}3\in \left(2\dots 5\right)↔\left(\left(2\in ℤ\wedge 5\in ℤ\wedge 3\in ℤ\right)\wedge \left(2\le 3\wedge 3\le 5\right)\right)$
88 81 86 87 mpbir2an ${⊢}3\in \left(2\dots 5\right)$
89 fzsplit ${⊢}3\in \left(2\dots 5\right)\to \left(2\dots 5\right)=\left(2\dots 3\right)\cup \left(3+1\dots 5\right)$
90 88 89 ax-mp ${⊢}\left(2\dots 5\right)=\left(2\dots 3\right)\cup \left(3+1\dots 5\right)$
91 df-3 ${⊢}3=2+1$
92 91 oveq2i ${⊢}\left(2\dots 3\right)=\left(2\dots 2+1\right)$
93 fzpr ${⊢}2\in ℤ\to \left(2\dots 2+1\right)=\left\{2,2+1\right\}$
94 1 93 ax-mp ${⊢}\left(2\dots 2+1\right)=\left\{2,2+1\right\}$
95 2p1e3 ${⊢}2+1=3$
96 95 preq2i ${⊢}\left\{2,2+1\right\}=\left\{2,3\right\}$
97 92 94 96 3eqtri ${⊢}\left(2\dots 3\right)=\left\{2,3\right\}$
98 28 oveq1i ${⊢}\left(3+1\dots 5\right)=\left(4\dots 5\right)$
99 df-5 ${⊢}5=4+1$
100 99 oveq2i ${⊢}\left(4\dots 5\right)=\left(4\dots 4+1\right)$
101 4z ${⊢}4\in ℤ$
102 fzpr ${⊢}4\in ℤ\to \left(4\dots 4+1\right)=\left\{4,4+1\right\}$
103 101 102 ax-mp ${⊢}\left(4\dots 4+1\right)=\left\{4,4+1\right\}$
104 4p1e5 ${⊢}4+1=5$
105 104 preq2i ${⊢}\left\{4,4+1\right\}=\left\{4,5\right\}$
106 103 105 eqtri ${⊢}\left(4\dots 4+1\right)=\left\{4,5\right\}$
107 98 100 106 3eqtri ${⊢}\left(3+1\dots 5\right)=\left\{4,5\right\}$
108 97 107 uneq12i ${⊢}\left(2\dots 3\right)\cup \left(3+1\dots 5\right)=\left\{2,3\right\}\cup \left\{4,5\right\}$
109 77 90 108 3eqtri ${⊢}\left(2\dots ⌊\sqrt{31}⌋\right)=\left\{2,3\right\}\cup \left\{4,5\right\}$
110 109 ineq1i ${⊢}\left(2\dots ⌊\sqrt{31}⌋\right)\cap ℙ=\left(\left\{2,3\right\}\cup \left\{4,5\right\}\right)\cap ℙ$
111 57 110 eleq2s ${⊢}{n}\in \left(\left(2\dots ⌊\sqrt{31}⌋\right)\cap ℙ\right)\to ¬{n}\parallel 31$
112 111 rgen ${⊢}\forall {n}\in \left(\left(2\dots ⌊\sqrt{31}⌋\right)\cap ℙ\right)\phantom{\rule{.4em}{0ex}}¬{n}\parallel 31$
113 isprm7 ${⊢}31\in ℙ↔\left(31\in {ℤ}_{\ge 2}\wedge \forall {n}\in \left(\left(2\dots ⌊\sqrt{31}⌋\right)\cap ℙ\right)\phantom{\rule{.4em}{0ex}}¬{n}\parallel 31\right)$
114 14 112 113 mpbir2an ${⊢}31\in ℙ$