MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  quoremz Structured version   Visualization version   GIF version

Theorem quoremz 13816
Description: Quotient and remainder of an integer divided by a positive integer. TODO - is this really needed for anything? Should we use mod to simplify it? Remark (AV): This is a special case of divalg 16342. (Contributed by NM, 14-Aug-2008.)
Hypotheses
Ref Expression
quorem.1 𝑄 = (⌊‘(𝐴 / 𝐵))
quorem.2 𝑅 = (𝐴 − (𝐵 · 𝑄))
Assertion
Ref Expression
quoremz ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝑄 ∈ ℤ ∧ 𝑅 ∈ ℕ0) ∧ (𝑅 < 𝐵𝐴 = ((𝐵 · 𝑄) + 𝑅))))

Proof of Theorem quoremz
StepHypRef Expression
1 quorem.1 . . 3 𝑄 = (⌊‘(𝐴 / 𝐵))
2 zre 12558 . . . . . 6 (𝐴 ∈ ℤ → 𝐴 ∈ ℝ)
32adantr 480 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐴 ∈ ℝ)
4 nnre 12215 . . . . . 6 (𝐵 ∈ ℕ → 𝐵 ∈ ℝ)
54adantl 481 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐵 ∈ ℝ)
6 nnne0 12242 . . . . . 6 (𝐵 ∈ ℕ → 𝐵 ≠ 0)
76adantl 481 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐵 ≠ 0)
83, 5, 7redivcld 12038 . . . 4 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐴 / 𝐵) ∈ ℝ)
98flcld 13759 . . 3 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (⌊‘(𝐴 / 𝐵)) ∈ ℤ)
101, 9eqeltrid 2829 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝑄 ∈ ℤ)
11 quorem.2 . . 3 𝑅 = (𝐴 − (𝐵 · 𝑄))
1210zcnd 12663 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝑄 ∈ ℂ)
13 nncn 12216 . . . . . . . 8 (𝐵 ∈ ℕ → 𝐵 ∈ ℂ)
1413adantl 481 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐵 ∈ ℂ)
1512, 14, 7divcan3d 11991 . . . . . 6 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐵 · 𝑄) / 𝐵) = 𝑄)
16 flle 13760 . . . . . . . 8 ((𝐴 / 𝐵) ∈ ℝ → (⌊‘(𝐴 / 𝐵)) ≤ (𝐴 / 𝐵))
178, 16syl 17 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (⌊‘(𝐴 / 𝐵)) ≤ (𝐴 / 𝐵))
181, 17eqbrtrid 5173 . . . . . 6 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝑄 ≤ (𝐴 / 𝐵))
1915, 18eqbrtrd 5160 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐵 · 𝑄) / 𝐵) ≤ (𝐴 / 𝐵))
20 nnz 12575 . . . . . . . . 9 (𝐵 ∈ ℕ → 𝐵 ∈ ℤ)
2120adantl 481 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐵 ∈ ℤ)
2221, 10zmulcld 12668 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐵 · 𝑄) ∈ ℤ)
2322zred 12662 . . . . . 6 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐵 · 𝑄) ∈ ℝ)
24 nngt0 12239 . . . . . . 7 (𝐵 ∈ ℕ → 0 < 𝐵)
2524adantl 481 . . . . . 6 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 0 < 𝐵)
26 lediv1 12075 . . . . . 6 (((𝐵 · 𝑄) ∈ ℝ ∧ 𝐴 ∈ ℝ ∧ (𝐵 ∈ ℝ ∧ 0 < 𝐵)) → ((𝐵 · 𝑄) ≤ 𝐴 ↔ ((𝐵 · 𝑄) / 𝐵) ≤ (𝐴 / 𝐵)))
2723, 3, 5, 25, 26syl112anc 1371 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐵 · 𝑄) ≤ 𝐴 ↔ ((𝐵 · 𝑄) / 𝐵) ≤ (𝐴 / 𝐵)))
2819, 27mpbird 257 . . . 4 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐵 · 𝑄) ≤ 𝐴)
29 simpl 482 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐴 ∈ ℤ)
30 znn0sub 12605 . . . . 5 (((𝐵 · 𝑄) ∈ ℤ ∧ 𝐴 ∈ ℤ) → ((𝐵 · 𝑄) ≤ 𝐴 ↔ (𝐴 − (𝐵 · 𝑄)) ∈ ℕ0))
3122, 29, 30syl2anc 583 . . . 4 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐵 · 𝑄) ≤ 𝐴 ↔ (𝐴 − (𝐵 · 𝑄)) ∈ ℕ0))
3228, 31mpbid 231 . . 3 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐴 − (𝐵 · 𝑄)) ∈ ℕ0)
3311, 32eqeltrid 2829 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝑅 ∈ ℕ0)
341oveq2i 7412 . . . . . 6 ((𝐴 / 𝐵) − 𝑄) = ((𝐴 / 𝐵) − (⌊‘(𝐴 / 𝐵)))
35 fraclt1 13763 . . . . . . 7 ((𝐴 / 𝐵) ∈ ℝ → ((𝐴 / 𝐵) − (⌊‘(𝐴 / 𝐵))) < 1)
368, 35syl 17 . . . . . 6 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐴 / 𝐵) − (⌊‘(𝐴 / 𝐵))) < 1)
3734, 36eqbrtrid 5173 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐴 / 𝐵) − 𝑄) < 1)
3811oveq1i 7411 . . . . . 6 (𝑅 / 𝐵) = ((𝐴 − (𝐵 · 𝑄)) / 𝐵)
39 zcn 12559 . . . . . . . . 9 (𝐴 ∈ ℤ → 𝐴 ∈ ℂ)
4039adantr 480 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐴 ∈ ℂ)
4122zcnd 12663 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐵 · 𝑄) ∈ ℂ)
4213, 6jca 511 . . . . . . . . 9 (𝐵 ∈ ℕ → (𝐵 ∈ ℂ ∧ 𝐵 ≠ 0))
4342adantl 481 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐵 ∈ ℂ ∧ 𝐵 ≠ 0))
44 divsubdir 11904 . . . . . . . 8 ((𝐴 ∈ ℂ ∧ (𝐵 · 𝑄) ∈ ℂ ∧ (𝐵 ∈ ℂ ∧ 𝐵 ≠ 0)) → ((𝐴 − (𝐵 · 𝑄)) / 𝐵) = ((𝐴 / 𝐵) − ((𝐵 · 𝑄) / 𝐵)))
4540, 41, 43, 44syl3anc 1368 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐴 − (𝐵 · 𝑄)) / 𝐵) = ((𝐴 / 𝐵) − ((𝐵 · 𝑄) / 𝐵)))
4615oveq2d 7417 . . . . . . 7 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐴 / 𝐵) − ((𝐵 · 𝑄) / 𝐵)) = ((𝐴 / 𝐵) − 𝑄))
4745, 46eqtrd 2764 . . . . . 6 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐴 − (𝐵 · 𝑄)) / 𝐵) = ((𝐴 / 𝐵) − 𝑄))
4838, 47eqtrid 2776 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝑅 / 𝐵) = ((𝐴 / 𝐵) − 𝑄))
4913, 6dividd 11984 . . . . . 6 (𝐵 ∈ ℕ → (𝐵 / 𝐵) = 1)
5049adantl 481 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐵 / 𝐵) = 1)
5137, 48, 503brtr4d 5170 . . . 4 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝑅 / 𝐵) < (𝐵 / 𝐵))
5233nn0red 12529 . . . . 5 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝑅 ∈ ℝ)
53 ltdiv1 12074 . . . . 5 ((𝑅 ∈ ℝ ∧ 𝐵 ∈ ℝ ∧ (𝐵 ∈ ℝ ∧ 0 < 𝐵)) → (𝑅 < 𝐵 ↔ (𝑅 / 𝐵) < (𝐵 / 𝐵)))
5452, 5, 5, 25, 53syl112anc 1371 . . . 4 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝑅 < 𝐵 ↔ (𝑅 / 𝐵) < (𝐵 / 𝐵)))
5551, 54mpbird 257 . . 3 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝑅 < 𝐵)
5611oveq2i 7412 . . . 4 ((𝐵 · 𝑄) + 𝑅) = ((𝐵 · 𝑄) + (𝐴 − (𝐵 · 𝑄)))
5741, 40pncan3d 11570 . . . 4 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝐵 · 𝑄) + (𝐴 − (𝐵 · 𝑄))) = 𝐴)
5856, 57eqtr2id 2777 . . 3 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → 𝐴 = ((𝐵 · 𝑄) + 𝑅))
5955, 58jca 511 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝑅 < 𝐵𝐴 = ((𝐵 · 𝑄) + 𝑅)))
6010, 33, 59jca31 514 1 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → ((𝑄 ∈ ℤ ∧ 𝑅 ∈ ℕ0) ∧ (𝑅 < 𝐵𝐴 = ((𝐵 · 𝑄) + 𝑅))))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 205  wa 395   = wceq 1533  wcel 2098  wne 2932   class class class wbr 5138  cfv 6533  (class class class)co 7401  cc 11103  cr 11104  0cc0 11105  1c1 11106   + caddc 11108   · cmul 11110   < clt 11244  cle 11245  cmin 11440   / cdiv 11867  cn 12208  0cn0 12468  cz 12554  cfl 13751
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1905  ax-6 1963  ax-7 2003  ax-8 2100  ax-9 2108  ax-10 2129  ax-11 2146  ax-12 2163  ax-ext 2695  ax-sep 5289  ax-nul 5296  ax-pow 5353  ax-pr 5417  ax-un 7718  ax-cnex 11161  ax-resscn 11162  ax-1cn 11163  ax-icn 11164  ax-addcl 11165  ax-addrcl 11166  ax-mulcl 11167  ax-mulrcl 11168  ax-mulcom 11169  ax-addass 11170  ax-mulass 11171  ax-distr 11172  ax-i2m1 11173  ax-1ne0 11174  ax-1rid 11175  ax-rnegex 11176  ax-rrecex 11177  ax-cnre 11178  ax-pre-lttri 11179  ax-pre-lttrn 11180  ax-pre-ltadd 11181  ax-pre-mulgt0 11182  ax-pre-sup 11183
This theorem depends on definitions:  df-bi 206  df-an 396  df-or 845  df-3or 1085  df-3an 1086  df-tru 1536  df-fal 1546  df-ex 1774  df-nf 1778  df-sb 2060  df-mo 2526  df-eu 2555  df-clab 2702  df-cleq 2716  df-clel 2802  df-nfc 2877  df-ne 2933  df-nel 3039  df-ral 3054  df-rex 3063  df-rmo 3368  df-reu 3369  df-rab 3425  df-v 3468  df-sbc 3770  df-csb 3886  df-dif 3943  df-un 3945  df-in 3947  df-ss 3957  df-pss 3959  df-nul 4315  df-if 4521  df-pw 4596  df-sn 4621  df-pr 4623  df-op 4627  df-uni 4900  df-iun 4989  df-br 5139  df-opab 5201  df-mpt 5222  df-tr 5256  df-id 5564  df-eprel 5570  df-po 5578  df-so 5579  df-fr 5621  df-we 5623  df-xp 5672  df-rel 5673  df-cnv 5674  df-co 5675  df-dm 5676  df-rn 5677  df-res 5678  df-ima 5679  df-pred 6290  df-ord 6357  df-on 6358  df-lim 6359  df-suc 6360  df-iota 6485  df-fun 6535  df-fn 6536  df-f 6537  df-f1 6538  df-fo 6539  df-f1o 6540  df-fv 6541  df-riota 7357  df-ov 7404  df-oprab 7405  df-mpo 7406  df-om 7849  df-2nd 7969  df-frecs 8261  df-wrecs 8292  df-recs 8366  df-rdg 8405  df-er 8698  df-en 8935  df-dom 8936  df-sdom 8937  df-sup 9432  df-inf 9433  df-pnf 11246  df-mnf 11247  df-xr 11248  df-ltxr 11249  df-le 11250  df-sub 11442  df-neg 11443  df-div 11868  df-nn 12209  df-n0 12469  df-z 12555  df-uz 12819  df-fl 13753
This theorem is referenced by:  quoremnn0  13817
  Copyright terms: Public domain W3C validator