Theorem mod42tp1mod8 48513

Description: If a number is 3 modulo 4, twice the number plus 1 is 7 modulo 8. (Contributed by AV, 19-Aug-2021.)

Assertion

Ref	Expression
mod42tp1mod8	⊢ ((𝑁 ∈ ℤ ∧ (𝑁 mod 4) = 3) → (((2 · 𝑁) + 1) mod 8) = 7)

Proof of Theorem mod42tp1mod8

Dummy variable 𝑧 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		4nn 12352	. . . . 5 ⊢ 4 ∈ ℕ
2	1	a1i 11	. . . 4 ⊢ (𝑁 ∈ ℤ → 4 ∈ ℕ)
3		3nn0 12550	. . . . . 6 ⊢ 3 ∈ ℕ0
4	3	a1i 11	. . . . 5 ⊢ (𝑁 ∈ ℤ → 3 ∈ ℕ0)
5		3lt4 12445	. . . . 5 ⊢ 3 < 4
6	4, 5	jctir 530	. . . 4 ⊢ (𝑁 ∈ ℤ → (3 ∈ ℕ0 ∧ 3 < 4))
7		modremain 16504	. . . 4 ⊢ ((𝑁 ∈ ℤ ∧ 4 ∈ ℕ ∧ (3 ∈ ℕ0 ∧ 3 < 4)) → ((𝑁 mod 4) = 3 ↔ ∃𝑧 ∈ ℤ ((𝑧 · 4) + 3) = 𝑁))
8	2, 6, 7	mpd3an23 1492	. . 3 ⊢ (𝑁 ∈ ℤ → ((𝑁 mod 4) = 3 ↔ ∃𝑧 ∈ ℤ ((𝑧 · 4) + 3) = 𝑁))
9		2cnd 12347	. . . . . . . . . . 11 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → 2 ∈ ℂ)
10		simpr 490	. . . . . . . . . . . . 13 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → 𝑧 ∈ ℤ)
11		4z 12656	. . . . . . . . . . . . . 14 ⊢ 4 ∈ ℤ
12	11	a1i 11	. . . . . . . . . . . . 13 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → 4 ∈ ℤ)
13	10, 12	zmulcld 12735	. . . . . . . . . . . 12 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (𝑧 · 4) ∈ ℤ)
14	13	zcnd 12730	. . . . . . . . . . 11 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (𝑧 · 4) ∈ ℂ)
15		3cn 12350	. . . . . . . . . . . 12 ⊢ 3 ∈ ℂ
16	15	a1i 11	. . . . . . . . . . 11 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → 3 ∈ ℂ)
17	9, 14, 16	adddid 11261	. . . . . . . . . 10 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (2 · ((𝑧 · 4) + 3)) = ((2 · (𝑧 · 4)) + (2 · 3)))
18	10	zcnd 12730	. . . . . . . . . . . . 13 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → 𝑧 ∈ ℂ)
19		4cn 12354	. . . . . . . . . . . . . 14 ⊢ 4 ∈ ℂ
20	19	a1i 11	. . . . . . . . . . . . 13 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → 4 ∈ ℂ)
21	9, 18, 20	mul12d 11447	. . . . . . . . . . . 12 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (2 · (𝑧 · 4)) = (𝑧 · (2 · 4)))
22		2t4e8 12438	. . . . . . . . . . . . 13 ⊢ (2 · 4) = 8
23	22	oveq2i 7428	. . . . . . . . . . . 12 ⊢ (𝑧 · (2 · 4)) = (𝑧 · 8)
24	21, 23	eqtrdi 2813	. . . . . . . . . . 11 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (2 · (𝑧 · 4)) = (𝑧 · 8))
25		2t3e6 12435	. . . . . . . . . . . 12 ⊢ (2 · 3) = 6
26	25	a1i 11	. . . . . . . . . . 11 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (2 · 3) = 6)
27	24, 26	oveq12d 7435	. . . . . . . . . 10 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → ((2 · (𝑧 · 4)) + (2 · 3)) = ((𝑧 · 8) + 6))
28	17, 27	eqtrd 2797	. . . . . . . . 9 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (2 · ((𝑧 · 4) + 3)) = ((𝑧 · 8) + 6))
29	28	oveq1d 7432	. . . . . . . 8 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → ((2 · ((𝑧 · 4) + 3)) + 1) = (((𝑧 · 8) + 6) + 1))
30		id 23	. . . . . . . . . . . . 13 ⊢ (𝑧 ∈ ℤ → 𝑧 ∈ ℤ)
31		8nn 12364	. . . . . . . . . . . . . . 15 ⊢ 8 ∈ ℕ
32	31	nnzi 12646	. . . . . . . . . . . . . 14 ⊢ 8 ∈ ℤ
33	32	a1i 11	. . . . . . . . . . . . 13 ⊢ (𝑧 ∈ ℤ → 8 ∈ ℤ)
34	30, 33	zmulcld 12735	. . . . . . . . . . . 12 ⊢ (𝑧 ∈ ℤ → (𝑧 · 8) ∈ ℤ)
35	34	zcnd 12730	. . . . . . . . . . 11 ⊢ (𝑧 ∈ ℤ → (𝑧 · 8) ∈ ℂ)
36		6cn 12360	. . . . . . . . . . . 12 ⊢ 6 ∈ ℂ
37	36	a1i 11	. . . . . . . . . . 11 ⊢ (𝑧 ∈ ℤ → 6 ∈ ℂ)
38		1cnd 11230	. . . . . . . . . . 11 ⊢ (𝑧 ∈ ℤ → 1 ∈ ℂ)
39	35, 37, 38	addassd 11259	. . . . . . . . . 10 ⊢ (𝑧 ∈ ℤ → (((𝑧 · 8) + 6) + 1) = ((𝑧 · 8) + (6 + 1)))
40		6p1e7 12416	. . . . . . . . . . . 12 ⊢ (6 + 1) = 7
41	40	a1i 11	. . . . . . . . . . 11 ⊢ (𝑧 ∈ ℤ → (6 + 1) = 7)
42	41	oveq2d 7433	. . . . . . . . . 10 ⊢ (𝑧 ∈ ℤ → ((𝑧 · 8) + (6 + 1)) = ((𝑧 · 8) + 7))
43	39, 42	eqtrd 2797	. . . . . . . . 9 ⊢ (𝑧 ∈ ℤ → (((𝑧 · 8) + 6) + 1) = ((𝑧 · 8) + 7))
44	43	adantl 487	. . . . . . . 8 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (((𝑧 · 8) + 6) + 1) = ((𝑧 · 8) + 7))
45	29, 44	eqtrd 2797	. . . . . . 7 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → ((2 · ((𝑧 · 4) + 3)) + 1) = ((𝑧 · 8) + 7))
46	45	oveq1d 7432	. . . . . 6 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (((2 · ((𝑧 · 4) + 3)) + 1) mod 8) = (((𝑧 · 8) + 7) mod 8))
47		nnrp 13058	. . . . . . . . 9 ⊢ (8 ∈ ℕ → 8 ∈ ℝ+)
48	31, 47	mp1i 14	. . . . . . . 8 ⊢ (𝑧 ∈ ℤ → 8 ∈ ℝ+)
49		0xr 11284	. . . . . . . . . 10 ⊢ 0 ∈ ℝ*
50	49	a1i 11	. . . . . . . . 9 ⊢ (𝑧 ∈ ℤ → 0 ∈ ℝ*)
51		8re 12365	. . . . . . . . . . 11 ⊢ 8 ∈ ℝ
52	51	rexri 11295	. . . . . . . . . 10 ⊢ 8 ∈ ℝ*
53	52	a1i 11	. . . . . . . . 9 ⊢ (𝑧 ∈ ℤ → 8 ∈ ℝ*)
54		7re 12362	. . . . . . . . . . 11 ⊢ 7 ∈ ℝ
55	54	rexri 11295	. . . . . . . . . 10 ⊢ 7 ∈ ℝ*
56	55	a1i 11	. . . . . . . . 9 ⊢ (𝑧 ∈ ℤ → 7 ∈ ℝ*)
57		0re 11238	. . . . . . . . . . 11 ⊢ 0 ∈ ℝ
58		7pos 12383	. . . . . . . . . . 11 ⊢ 0 < 7
59	57, 54, 58	ltleii 11361	. . . . . . . . . 10 ⊢ 0 ≤ 7
60	59	a1i 11	. . . . . . . . 9 ⊢ (𝑧 ∈ ℤ → 0 ≤ 7)
61		7lt8 12463	. . . . . . . . . 10 ⊢ 7 < 8
62	61	a1i 11	. . . . . . . . 9 ⊢ (𝑧 ∈ ℤ → 7 < 8)
63	50, 53, 56, 60, 62	elicod 13452	. . . . . . . 8 ⊢ (𝑧 ∈ ℤ → 7 ∈ (0[,)8))
64		muladdmodid 13978	. . . . . . . 8 ⊢ ((𝑧 ∈ ℤ ∧ 8 ∈ ℝ+ ∧ 7 ∈ (0[,)8)) → (((𝑧 · 8) + 7) mod 8) = 7)
65	48, 63, 64	mpd3an23 1492	. . . . . . 7 ⊢ (𝑧 ∈ ℤ → (((𝑧 · 8) + 7) mod 8) = 7)
66	65	adantl 487	. . . . . 6 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (((𝑧 · 8) + 7) mod 8) = 7)
67	46, 66	eqtrd 2797	. . . . 5 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (((2 · ((𝑧 · 4) + 3)) + 1) mod 8) = 7)
68		oveq2 7425	. . . . . . . 8 ⊢ (((𝑧 · 4) + 3) = 𝑁 → (2 · ((𝑧 · 4) + 3)) = (2 · 𝑁))
69	68	oveq1d 7432	. . . . . . 7 ⊢ (((𝑧 · 4) + 3) = 𝑁 → ((2 · ((𝑧 · 4) + 3)) + 1) = ((2 · 𝑁) + 1))
70	69	oveq1d 7432	. . . . . 6 ⊢ (((𝑧 · 4) + 3) = 𝑁 → (((2 · ((𝑧 · 4) + 3)) + 1) mod 8) = (((2 · 𝑁) + 1) mod 8))
71	70	eqeq1d 2764	. . . . 5 ⊢ (((𝑧 · 4) + 3) = 𝑁 → ((((2 · ((𝑧 · 4) + 3)) + 1) mod 8) = 7 ↔ (((2 · 𝑁) + 1) mod 8) = 7))
72	67, 71	syl5ibcom 248	. . . 4 ⊢ ((𝑁 ∈ ℤ ∧ 𝑧 ∈ ℤ) → (((𝑧 · 4) + 3) = 𝑁 → (((2 · 𝑁) + 1) mod 8) = 7))
73	72	rexlimdva 3165	. . 3 ⊢ (𝑁 ∈ ℤ → (∃𝑧 ∈ ℤ ((𝑧 · 4) + 3) = 𝑁 → (((2 · 𝑁) + 1) mod 8) = 7))
74	8, 73	sylbid 243	. 2 ⊢ (𝑁 ∈ ℤ → ((𝑁 mod 4) = 3 → (((2 · 𝑁) + 1) mod 8) = 7))
75	74	imp 412	1 ⊢ ((𝑁 ∈ ℤ ∧ (𝑁 mod 4) = 3) → (((2 · 𝑁) + 1) mod 8) = 7)

This proof depends on syntax axioms:   → wi 4   ↔ wb 209   ∧ wa 401   = wceq 1570   ∈ wcel 2145  ∃wrex 3088   class class class wbr 5107  (class class class)co 7417  ℂcc 11126  0cc0 11128  1c1 11129   + caddc 11131   · cmul 11133  ℝ^*cxr 11270   < clt 11271   ≤ cle 11272  ℕcn 12261  2c2 12323  3c3 12324  4c4 12325  6c6 12327  7c7 12328  8c8 12329  ℕ₀cn0 12532  ℤcz 12619  ℝ⁺crp 13046  [,)cico 13404   mod cmo 13934

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1943  ax-6 2000  ax-7 2041  ax-8 2147  ax-9 2155  ax-10 2178  ax-11 2194  ax-12 2215  ax-ext 2734  ax-sep 5255  ax-nul 5267  ax-pow 5334  ax-pr 5402  ax-un 7740  ax-cnex 11184  ax-resscn 11185  ax-1cn 11186  ax-icn 11187  ax-addcl 11188  ax-addrcl 11189  ax-mulcl 11190  ax-mulrcl 11191  ax-mulcom 11192  ax-addass 11193  ax-mulass 11194  ax-distr 11195  ax-i2m1 11196  ax-1ne0 11197  ax-1rid 11198  ax-rnegex 11199  ax-rrecex 11200  ax-cnre 11201  ax-pre-lttri 11202  ax-pre-lttrn 11203  ax-pre-ltadd 11204  ax-pre-mulgt0 11205  ax-pre-sup 11206

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2100  df-mo 2566  df-eu 2596  df-clab 2741  df-cleq 2754  df-clel 2837  df-nfc 2911  df-ne 2958  df-nel 3064  df-ral 3079  df-rex 3089  df-rmo 3367  df-reu 3368  df-rab 3415  df-v 3455  df-sbc 3743  df-csb 3851  df-dif 3905  df-un 3907  df-in 3909  df-ss 3919  df-pss 3922  df-nul 4283  df-if 4486  df-pw 4562  df-sn 4588  df-pr 4590  df-op 4594  df-uni 4871  df-iun 4956  df-br 5108  df-opab 5172  df-mpt 5191  df-tr 5217  df-id 5554  df-eprel 5559  df-po 5567  df-so 5568  df-fr 5612  df-we 5614  df-xp 5665  df-rel 5666  df-cnv 5667  df-co 5668  df-dm 5669  df-rn 5670  df-res 5671  df-ima 5672  df-pred 6303  df-ord 6364  df-on 6365  df-lim 6366  df-suc 6367  df-iota 6493  df-fun 6539  df-fn 6540  df-f 6541  df-f1 6542  df-fo 6543  df-f1o 6544  df-fv 6545  df-riota 7374  df-ov 7420  df-oprab 7421  df-mpo 7422  df-om 7867  df-1st 7990  df-2nd 7991  df-frecs 8284  df-wrecs 8315  df-recs 8364  df-rdg 8403  df-er 8700  df-en 8957  df-dom 8958  df-sdom 8959  df-sup 9416  df-inf 9417  df-pnf 11273  df-mnf 11274  df-xr 11275  df-ltxr 11276  df-le 11277  df-sub 11471  df-neg 11472  df-div 11900  df-nn 12262  df-2 12331  df-3 12332  df-4 12333  df-5 12334  df-6 12335  df-7 12336  df-8 12337  df-n0 12533  df-z 12620  df-uz 12892  df-rp 13047  df-ico 13408  df-fz 13566  df-fl 13857  df-mod 13935  df-seq 14070  df-exp 14130  df-cj 15190  df-re 15191  df-im 15192  df-sqrt 15326  df-abs 15327  df-dvds 16349

This theorem is used by:  sgprmdvdsmersenne  48515