Theorem moddvds 16221

Description: Two ways to say 𝐴≡𝐵 (mod 𝑁), see also definition in [ApostolNT] p. 106. (Contributed by Mario Carneiro, 18-Feb-2014.)

Assertion

Ref	Expression
moddvds	⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) ↔ 𝑁 ∥ (𝐴 − 𝐵)))

Proof of Theorem moddvds

Step	Hyp	Ref	Expression
1		nnrp 12943	. . . . . 6 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℝ+)
2	1	adantr 480	. . . . 5 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → 𝑁 ∈ ℝ+)
3		0mod 13850	. . . . 5 ⊢ (𝑁 ∈ ℝ+ → (0 mod 𝑁) = 0)
4	2, 3	syl 17	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (0 mod 𝑁) = 0)
5	4	eqeq2d 2746	. . 3 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁) ↔ ((𝐴 − 𝐵) mod 𝑁) = 0))
6		zre 12517	. . . . . . 7 ⊢ (𝐴 ∈ ℤ → 𝐴 ∈ ℝ)
7	6	ad2antrl 729	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → 𝐴 ∈ ℝ)
8		zre 12517	. . . . . . 7 ⊢ (𝐵 ∈ ℤ → 𝐵 ∈ ℝ)
9	8	ad2antll 730	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → 𝐵 ∈ ℝ)
10	9	renegcld 11566	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → -𝐵 ∈ ℝ)
11		modadd1 13856	. . . . . . 7 ⊢ (((𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ) ∧ (-𝐵 ∈ ℝ ∧ 𝑁 ∈ ℝ+) ∧ (𝐴 mod 𝑁) = (𝐵 mod 𝑁)) → ((𝐴 + -𝐵) mod 𝑁) = ((𝐵 + -𝐵) mod 𝑁))
12	11	3expia 1122	. . . . . 6 ⊢ (((𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ) ∧ (-𝐵 ∈ ℝ ∧ 𝑁 ∈ ℝ+)) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) → ((𝐴 + -𝐵) mod 𝑁) = ((𝐵 + -𝐵) mod 𝑁)))
13	7, 9, 10, 2, 12	syl22anc 839	. . . . 5 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) → ((𝐴 + -𝐵) mod 𝑁) = ((𝐵 + -𝐵) mod 𝑁)))
14	7	recnd 11162	. . . . . . . 8 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → 𝐴 ∈ ℂ)
15	9	recnd 11162	. . . . . . . 8 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → 𝐵 ∈ ℂ)
16	14, 15	negsubd 11500	. . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (𝐴 + -𝐵) = (𝐴 − 𝐵))
17	16	oveq1d 7371	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐴 + -𝐵) mod 𝑁) = ((𝐴 − 𝐵) mod 𝑁))
18	15	negidd 11484	. . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (𝐵 + -𝐵) = 0)
19	18	oveq1d 7371	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐵 + -𝐵) mod 𝑁) = (0 mod 𝑁))
20	17, 19	eqeq12d 2751	. . . . 5 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (((𝐴 + -𝐵) mod 𝑁) = ((𝐵 + -𝐵) mod 𝑁) ↔ ((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁)))
21	13, 20	sylibd 239	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) → ((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁)))
22	7, 9	resubcld 11567	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (𝐴 − 𝐵) ∈ ℝ)
23		0red 11136	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → 0 ∈ ℝ)
24		modadd1 13856	. . . . . . 7 ⊢ ((((𝐴 − 𝐵) ∈ ℝ ∧ 0 ∈ ℝ) ∧ (𝐵 ∈ ℝ ∧ 𝑁 ∈ ℝ+) ∧ ((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁)) → (((𝐴 − 𝐵) + 𝐵) mod 𝑁) = ((0 + 𝐵) mod 𝑁))
25	24	3expia 1122	. . . . . 6 ⊢ ((((𝐴 − 𝐵) ∈ ℝ ∧ 0 ∈ ℝ) ∧ (𝐵 ∈ ℝ ∧ 𝑁 ∈ ℝ+)) → (((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁) → (((𝐴 − 𝐵) + 𝐵) mod 𝑁) = ((0 + 𝐵) mod 𝑁)))
26	22, 23, 9, 2, 25	syl22anc 839	. . . . 5 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁) → (((𝐴 − 𝐵) + 𝐵) mod 𝑁) = ((0 + 𝐵) mod 𝑁)))
27	14, 15	npcand 11498	. . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐴 − 𝐵) + 𝐵) = 𝐴)
28	27	oveq1d 7371	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (((𝐴 − 𝐵) + 𝐵) mod 𝑁) = (𝐴 mod 𝑁))
29	15	addlidd 11336	. . . . . . 7 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (0 + 𝐵) = 𝐵)
30	29	oveq1d 7371	. . . . . 6 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((0 + 𝐵) mod 𝑁) = (𝐵 mod 𝑁))
31	28, 30	eqeq12d 2751	. . . . 5 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((((𝐴 − 𝐵) + 𝐵) mod 𝑁) = ((0 + 𝐵) mod 𝑁) ↔ (𝐴 mod 𝑁) = (𝐵 mod 𝑁)))
32	26, 31	sylibd 239	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁) → (𝐴 mod 𝑁) = (𝐵 mod 𝑁)))
33	21, 32	impbid 212	. . 3 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) ↔ ((𝐴 − 𝐵) mod 𝑁) = (0 mod 𝑁)))
34		zsubcl 12558	. . . 4 ⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → (𝐴 − 𝐵) ∈ ℤ)
35		dvdsval3 16214	. . . 4 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 − 𝐵) ∈ ℤ) → (𝑁 ∥ (𝐴 − 𝐵) ↔ ((𝐴 − 𝐵) mod 𝑁) = 0))
36	34, 35	sylan2 594	. . 3 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → (𝑁 ∥ (𝐴 − 𝐵) ↔ ((𝐴 − 𝐵) mod 𝑁) = 0))
37	5, 33, 36	3bitr4d 311	. 2 ⊢ ((𝑁 ∈ ℕ ∧ (𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ)) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) ↔ 𝑁 ∥ (𝐴 − 𝐵)))
38	37	3impb 1115	1 ⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝐴 mod 𝑁) = (𝐵 mod 𝑁) ↔ 𝑁 ∥ (𝐴 − 𝐵)))

Syntax hints:   → wi 4   ↔ wb 206   ∧ wa 395   ∧ w3a 1087   = wceq 1542   ∈ wcel 2114   class class class wbr 5074  (class class class)co 7356  ℝcr 11026  0cc0 11027   + caddc 11030   − cmin 11366  -cneg 11367  ℕcn 12163  ℤcz 12513  ℝ⁺crp 12931   mod cmo 13817   ∥ cdvds 16210

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1969  ax-7 2010  ax-8 2116  ax-9 2124  ax-10 2147  ax-11 2163  ax-12 2184  ax-ext 2707  ax-sep 5220  ax-nul 5230  ax-pow 5296  ax-pr 5364  ax-un 7678  ax-cnex 11083  ax-resscn 11084  ax-1cn 11085  ax-icn 11086  ax-addcl 11087  ax-addrcl 11088  ax-mulcl 11089  ax-mulrcl 11090  ax-mulcom 11091  ax-addass 11092  ax-mulass 11093  ax-distr 11094  ax-i2m1 11095  ax-1ne0 11096  ax-1rid 11097  ax-rnegex 11098  ax-rrecex 11099  ax-cnre 11100  ax-pre-lttri 11101  ax-pre-lttrn 11102  ax-pre-ltadd 11103  ax-pre-mulgt0 11104  ax-pre-sup 11105

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1545  df-fal 1555  df-ex 1782  df-nf 1786  df-sb 2069  df-mo 2538  df-eu 2568  df-clab 2714  df-cleq 2727  df-clel 2810  df-nfc 2884  df-ne 2931  df-nel 3035  df-ral 3050  df-rex 3060  df-rmo 3340  df-reu 3341  df-rab 3388  df-v 3429  df-sbc 3726  df-csb 3834  df-dif 3888  df-un 3890  df-in 3892  df-ss 3902  df-pss 3905  df-nul 4264  df-if 4457  df-pw 4533  df-sn 4558  df-pr 4560  df-op 4564  df-uni 4841  df-iun 4925  df-br 5075  df-opab 5137  df-mpt 5156  df-tr 5182  df-id 5515  df-eprel 5520  df-po 5528  df-so 5529  df-fr 5573  df-we 5575  df-xp 5626  df-rel 5627  df-cnv 5628  df-co 5629  df-dm 5630  df-rn 5631  df-res 5632  df-ima 5633  df-pred 6254  df-ord 6315  df-on 6316  df-lim 6317  df-suc 6318  df-iota 6443  df-fun 6489  df-fn 6490  df-f 6491  df-f1 6492  df-fo 6493  df-f1o 6494  df-fv 6495  df-riota 7313  df-ov 7359  df-oprab 7360  df-mpo 7361  df-om 7807  df-2nd 7932  df-frecs 8220  df-wrecs 8251  df-recs 8300  df-rdg 8338  df-er 8632  df-en 8883  df-dom 8884  df-sdom 8885  df-sup 9344  df-inf 9345  df-pnf 11170  df-mnf 11171  df-xr 11172  df-ltxr 11173  df-le 11174  df-sub 11368  df-neg 11369  df-div 11797  df-nn 12164  df-n0 12427  df-z 12514  df-uz 12778  df-rp 12932  df-fl 13740  df-mod 13818  df-dvds 16211

This theorem is referenced by:  modm1div  16222  addmulmodb  16223  summodnegmod  16244  modmulconst  16246  addmodlteqALT  16283  dvdsmod  16287  sadadd3  16419  sadaddlem  16424  congr  16622  cncongr1  16625  cncongr2  16626  crth  16737  eulerthlem2  16741  prmdiv  16744  prmdiveq  16745  odzcllem  16752  odzdvds  16755  odzphi  16756  pockthlem  16865  4sqlem11  16915  4sqlem12  16916  mndodcong  19506  dfod2  19528  sylow3lem6  19596  znf1o  21520  wilthlem1  27019  wilthlem2  27020  wilthlem3  27021  wilthimp  27023  ppiub  27155  lgslem1  27248  lgsmod  27274  lgsdirprm  27282  lgsqrlem1  27297  lgsqrlem2  27298  lgsqr  27302  lgsqrmod  27303  lgsqrmodndvds  27304  lgsdchrval  27305  lgseisenlem2  27327  lgseisenlem3  27328  lgseisenlem4  27329  m1lgs  27339  submodaddmod  47783  difltmodne  47784  sfprmdvdsmersenne  48054  dfwppr  48202  fpprwpprb  48204