Theorem dvdsdc 12028

Description: Divisibility is decidable. (Contributed by Jim Kingdon, 14-Nov-2021.)

Assertion

Ref	Expression
dvdsdc	|- ( ( M e. NN /\ N e. ZZ ) -> DECID M || N )

Proof of Theorem dvdsdc

Step	Hyp	Ref	Expression
1		simpr 110	. . . . 5 |- ( ( M e. NN /\ N e. ZZ ) -> N e. ZZ )
2		simpl 109	. . . . 5 |- ( ( M e. NN /\ N e. ZZ ) -> M e. NN )
3	1, 2	zmodcld 10471	. . . 4 |- ( ( M e. NN /\ N e. ZZ ) -> ( N mod M ) e. NN0 )
4	3	nn0zd 9475	. . 3 |- ( ( M e. NN /\ N e. ZZ ) -> ( N mod M ) e. ZZ )
5		0z 9365	. . 3 |- 0 e. ZZ
6		zdceq 9430	. . 3 |- ( ( ( N mod M ) e. ZZ /\ 0 e. ZZ ) -> DECID ( N mod M ) = 0 )
7	4, 5, 6	sylancl 413	. 2 |- ( ( M e. NN /\ N e. ZZ ) -> DECID ( N mod M ) = 0 )
8		dvdsval3 12021	. . 3 |- ( ( M e. NN /\ N e. ZZ ) -> ( M || N <-> ( N mod M ) = 0 ) )
9	8	dcbid 839	. 2 |- ( ( M e. NN /\ N e. ZZ ) -> (DECID M || N <-> DECID ( N mod M ) = 0 ) )
10	7, 9	mpbird 167	1 |- ( ( M e. NN /\ N e. ZZ ) -> DECID M || N )

Syntax hints:   -> wi 4   /\ wa 104  DECID wdc 835   = wceq 1372   e. wcel 2175   class class class wbr 4043  (class class class)co 5934   0cc0 7907   NNcn 9018   ZZcz 9354   mod cmo 10448   || cdvds 12017

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 615  ax-in2 616  ax-io 710  ax-5 1469  ax-7 1470  ax-gen 1471  ax-ie1 1515  ax-ie2 1516  ax-8 1526  ax-10 1527  ax-11 1528  ax-i12 1529  ax-bndl 1531  ax-4 1532  ax-17 1548  ax-i9 1552  ax-ial 1556  ax-i5r 1557  ax-13 2177  ax-14 2178  ax-ext 2186  ax-sep 4161  ax-pow 4217  ax-pr 4252  ax-un 4478  ax-setind 4583  ax-cnex 7998  ax-resscn 7999  ax-1cn 8000  ax-1re 8001  ax-icn 8002  ax-addcl 8003  ax-addrcl 8004  ax-mulcl 8005  ax-mulrcl 8006  ax-addcom 8007  ax-mulcom 8008  ax-addass 8009  ax-mulass 8010  ax-distr 8011  ax-i2m1 8012  ax-0lt1 8013  ax-1rid 8014  ax-0id 8015  ax-rnegex 8016  ax-precex 8017  ax-cnre 8018  ax-pre-ltirr 8019  ax-pre-ltwlin 8020  ax-pre-lttrn 8021  ax-pre-apti 8022  ax-pre-ltadd 8023  ax-pre-mulgt0 8024  ax-pre-mulext 8025  ax-arch 8026

This theorem depends on definitions:  df-bi 117  df-dc 836  df-3or 981  df-3an 982  df-tru 1375  df-fal 1378  df-nf 1483  df-sb 1785  df-eu 2056  df-mo 2057  df-clab 2191  df-cleq 2197  df-clel 2200  df-nfc 2336  df-ne 2376  df-nel 2471  df-ral 2488  df-rex 2489  df-reu 2490  df-rmo 2491  df-rab 2492  df-v 2773  df-sbc 2998  df-csb 3093  df-dif 3167  df-un 3169  df-in 3171  df-ss 3178  df-pw 3617  df-sn 3638  df-pr 3639  df-op 3641  df-uni 3850  df-int 3885  df-iun 3928  df-br 4044  df-opab 4105  df-mpt 4106  df-id 4338  df-po 4341  df-iso 4342  df-xp 4679  df-rel 4680  df-cnv 4681  df-co 4682  df-dm 4683  df-rn 4684  df-res 4685  df-ima 4686  df-iota 5229  df-fun 5270  df-fn 5271  df-f 5272  df-fv 5276  df-riota 5889  df-ov 5937  df-oprab 5938  df-mpo 5939  df-1st 6216  df-2nd 6217  df-pnf 8091  df-mnf 8092  df-xr 8093  df-ltxr 8094  df-le 8095  df-sub 8227  df-neg 8228  df-reap 8630  df-ap 8637  df-div 8728  df-inn 9019  df-n0 9278  df-z 9355  df-q 9723  df-rp 9758  df-fl 10394  df-mod 10449  df-dvds 12018

This theorem is referenced by:  zdvdsdc  12042  bitsdc  12177  gcdsupex  12197  gcdsupcl  12198  prmind2  12361  prmdc  12371  divgcdodd  12384  euclemma  12387  pw2dvdslemn  12406  hashdvds  12462  fermltl  12475  dvdsfi  12480  hashgcdeq  12481  odzcllem  12484  odzdvds  12487  fldivp1  12590  prmpwdvds  12597  infpnlem2  12602  lgslem4  15398  lgsval  15399  lgsfvalg  15400  lgsfcl2  15401  lgsval2lem  15405  lgsmod  15421  lgsdir2  15428  lgsne0  15433  gausslemma2dlem1a  15453  lgsquadlemofi  15471  lgsquadlem2  15473  m1lgs  15480