Theorem moddvds 12478

Description: Two ways to say A == B (mod N), see also definition in [ApostolNT] p. 106. (Contributed by Mario Carneiro, 18-Feb-2014.)

Assertion

Ref	Expression
moddvds	|- ( ( N e. NN /\ A e. ZZ /\ B e. ZZ ) -> ( ( A mod N ) = ( B mod N ) <-> N || ( A - B ) ) )

Proof of Theorem moddvds

Step	Hyp	Ref	Expression
1		nnq 9961	. . . . . 6 |- ( N e. NN -> N e. QQ )
2	1	adantr 276	. . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> N e. QQ )
3		nngt0 9258	. . . . . 6 |- ( N e. NN -> 0 < N )
4	3	adantr 276	. . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> 0 < N )
5		q0mod 10713	. . . . 5 |- ( ( N e. QQ /\ 0 < N ) -> ( 0 mod N ) = 0 )
6	2, 4, 5	syl2anc 411	. . . 4 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( 0 mod N ) = 0 )
7	6	eqeq2d 2244	. . 3 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) mod N ) = ( 0 mod N ) <-> ( ( A - B ) mod N ) = 0 ) )
8		zq 9954	. . . . . . . . 9 |- ( A e. ZZ -> A e. QQ )
9	8	ad2antrl 490	. . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. QQ )
10	9	adantr 276	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> A e. QQ )
11		zq 9954	. . . . . . . . 9 |- ( B e. ZZ -> B e. QQ )
12	11	ad2antll 491	. . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. QQ )
13	12	adantr 276	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> B e. QQ )
14		qnegcl 9964	. . . . . . . 8 |- ( B e. QQ -> -u B e. QQ )
15	13, 14	syl 14	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> -u B e. QQ )
16	2	adantr 276	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> N e. QQ )
17	4	adantr 276	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> 0 < N )
18		simpr 110	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> ( A mod N ) = ( B mod N ) )
19	10, 13, 15, 16, 17, 18	modqadd1 10719	. . . . . 6 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( A mod N ) = ( B mod N ) ) -> ( ( A + -u B ) mod N ) = ( ( B + -u B ) mod N ) )
20	19	ex 115	. . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A mod N ) = ( B mod N ) -> ( ( A + -u B ) mod N ) = ( ( B + -u B ) mod N ) ) )
21		simprl 531	. . . . . . . . 9 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. ZZ )
22	21	zcnd 9697	. . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> A e. CC )
23		simprr 533	. . . . . . . . 9 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. ZZ )
24	23	zcnd 9697	. . . . . . . 8 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> B e. CC )
25	22, 24	negsubd 8586	. . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( A + -u B ) = ( A - B ) )
26	25	oveq1d 6064	. . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A + -u B ) mod N ) = ( ( A - B ) mod N ) )
27	24	negidd 8570	. . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( B + -u B ) = 0 )
28	27	oveq1d 6064	. . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( B + -u B ) mod N ) = ( 0 mod N ) )
29	26, 28	eqeq12d 2247	. . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A + -u B ) mod N ) = ( ( B + -u B ) mod N ) <-> ( ( A - B ) mod N ) = ( 0 mod N ) ) )
30	20, 29	sylibd 149	. . . 4 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A mod N ) = ( B mod N ) -> ( ( A - B ) mod N ) = ( 0 mod N ) ) )
31	9	adantr 276	. . . . . . . 8 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> A e. QQ )
32	12	adantr 276	. . . . . . . 8 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> B e. QQ )
33		qsubcl 9966	. . . . . . . 8 |- ( ( A e. QQ /\ B e. QQ ) -> ( A - B ) e. QQ )
34	31, 32, 33	syl2anc 411	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> ( A - B ) e. QQ )
35		0z 9584	. . . . . . . 8 |- 0 e. ZZ
36		zq 9954	. . . . . . . 8 |- ( 0 e. ZZ -> 0 e. QQ )
37	35, 36	mp1i 10	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> 0 e. QQ )
38	2	adantr 276	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> N e. QQ )
39	4	adantr 276	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> 0 < N )
40		simpr 110	. . . . . . 7 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> ( ( A - B ) mod N ) = ( 0 mod N ) )
41	34, 37, 32, 38, 39, 40	modqadd1 10719	. . . . . 6 |- ( ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) /\ ( ( A - B ) mod N ) = ( 0 mod N ) ) -> ( ( ( A - B ) + B ) mod N ) = ( ( 0 + B ) mod N ) )
42	41	ex 115	. . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) mod N ) = ( 0 mod N ) -> ( ( ( A - B ) + B ) mod N ) = ( ( 0 + B ) mod N ) ) )
43	22, 24	npcand 8584	. . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A - B ) + B ) = A )
44	43	oveq1d 6064	. . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) + B ) mod N ) = ( A mod N ) )
45	24	addlidd 8419	. . . . . . 7 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( 0 + B ) = B )
46	45	oveq1d 6064	. . . . . 6 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( 0 + B ) mod N ) = ( B mod N ) )
47	44, 46	eqeq12d 2247	. . . . 5 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( ( A - B ) + B ) mod N ) = ( ( 0 + B ) mod N ) <-> ( A mod N ) = ( B mod N ) ) )
48	42, 47	sylibd 149	. . . 4 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( ( A - B ) mod N ) = ( 0 mod N ) -> ( A mod N ) = ( B mod N ) ) )
49	30, 48	impbid 129	. . 3 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A mod N ) = ( B mod N ) <-> ( ( A - B ) mod N ) = ( 0 mod N ) ) )
50		zsubcl 9614	. . . 4 |- ( ( A e. ZZ /\ B e. ZZ ) -> ( A - B ) e. ZZ )
51		dvdsval3 12470	. . . 4 |- ( ( N e. NN /\ ( A - B ) e. ZZ ) -> ( N || ( A - B ) <-> ( ( A - B ) mod N ) = 0 ) )
52	50, 51	sylan2 286	. . 3 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( N || ( A - B ) <-> ( ( A - B ) mod N ) = 0 ) )
53	7, 49, 52	3bitr4d 220	. 2 |- ( ( N e. NN /\ ( A e. ZZ /\ B e. ZZ ) ) -> ( ( A mod N ) = ( B mod N ) <-> N || ( A - B ) ) )
54	53	3impb 1226	1 |- ( ( N e. NN /\ A e. ZZ /\ B e. ZZ ) -> ( ( A mod N ) = ( B mod N ) <-> N || ( A - B ) ) )

Syntax hints:   -> wi 4   /\ wa 104   <-> wb 105   /\ w3a 1005   = wceq 1398   e. wcel 2203   class class class wbr 4108  (class class class)co 6049   0cc0 8123   + caddc 8126   < clt 8304   - cmin 8440   -ucneg 8441   NNcn 9233   ZZcz 9573   QQcq 9947   mod cmo 10680   || cdvds 12466

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-ia1 106  ax-ia2 107  ax-ia3 108  ax-in1 619  ax-in2 620  ax-io 717  ax-5 1496  ax-7 1497  ax-gen 1498  ax-ie1 1542  ax-ie2 1543  ax-8 1553  ax-10 1554  ax-11 1555  ax-i12 1556  ax-bndl 1558  ax-4 1559  ax-17 1575  ax-i9 1579  ax-ial 1583  ax-i5r 1584  ax-13 2205  ax-14 2206  ax-ext 2214  ax-sep 4227  ax-pow 4286  ax-pr 4321  ax-un 4553  ax-setind 4658  ax-cnex 8214  ax-resscn 8215  ax-1cn 8216  ax-1re 8217  ax-icn 8218  ax-addcl 8219  ax-addrcl 8220  ax-mulcl 8221  ax-mulrcl 8222  ax-addcom 8223  ax-mulcom 8224  ax-addass 8225  ax-mulass 8226  ax-distr 8227  ax-i2m1 8228  ax-0lt1 8229  ax-1rid 8230  ax-0id 8231  ax-rnegex 8232  ax-precex 8233  ax-cnre 8234  ax-pre-ltirr 8235  ax-pre-ltwlin 8236  ax-pre-lttrn 8237  ax-pre-apti 8238  ax-pre-ltadd 8239  ax-pre-mulgt0 8240  ax-pre-mulext 8241  ax-arch 8242

This theorem depends on definitions:  df-bi 117  df-3or 1006  df-3an 1007  df-tru 1401  df-fal 1404  df-nf 1510  df-sb 1812  df-eu 2083  df-mo 2084  df-clab 2219  df-cleq 2225  df-clel 2228  df-nfc 2373  df-ne 2413  df-nel 2508  df-ral 2525  df-rex 2526  df-reu 2527  df-rmo 2528  df-rab 2529  df-v 2814  df-sbc 3042  df-csb 3138  df-dif 3212  df-un 3214  df-in 3216  df-ss 3223  df-pw 3670  df-sn 3694  df-pr 3695  df-op 3697  df-uni 3914  df-int 3949  df-iun 3992  df-br 4109  df-opab 4171  df-mpt 4172  df-id 4413  df-po 4416  df-iso 4417  df-xp 4754  df-rel 4755  df-cnv 4756  df-co 4757  df-dm 4758  df-rn 4759  df-res 4760  df-ima 4761  df-iota 5311  df-fun 5353  df-fn 5354  df-f 5355  df-fv 5359  df-riota 6002  df-ov 6052  df-oprab 6053  df-mpo 6054  df-1st 6333  df-2nd 6334  df-pnf 8306  df-mnf 8307  df-xr 8308  df-ltxr 8309  df-le 8310  df-sub 8442  df-neg 8443  df-reap 8845  df-ap 8852  df-div 8943  df-inn 9234  df-n0 9493  df-z 9574  df-q 9948  df-rp 9983  df-fl 10626  df-mod 10681  df-dvds 12467

This theorem is referenced by:  modm1div  12479  summodnegmod  12501  modmulconst  12502  addmodlteqALT  12538  dvdsmod  12541  congr  12790  cncongr1  12793  cncongr2  12794  crth  12914  eulerthlemh  12921  eulerthlemth  12922  prmdiv  12925  prmdiveq  12926  odzcllem  12933  odzdvds  12936  odzphi  12937  pockthlem  13047  4sqlem11  13092  4sqlem12  13093  znf1o  14786  wilthlem1  15835  lgslem1  15860  lgsmod  15886  lgsdirprm  15894  lgseisenlem2  15931  lgseisenlem3  15932  lgseisenlem4  15933  m1lgs  15945