![]() |
Intuitionistic Logic Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > ILE Home > Th. List > modqval | GIF version |
Description: The value of the modulo operation. The modulo congruence notation of number theory, 𝐽≡𝐾 (modulo 𝑁), can be expressed in our notation as (𝐽 mod 𝑁) = (𝐾 mod 𝑁). Definition 1 in Knuth, The Art of Computer Programming, Vol. I (1972), p. 38. Knuth uses "mod" for the operation and "modulo" for the congruence. Unlike Knuth, we restrict the second argument to positive numbers to simplify certain theorems. (This also gives us future flexibility to extend it to any one of several different conventions for a zero or negative second argument, should there be an advantage in doing so.) As with flqcl 9829 we only prove this for rationals although other particular kinds of real numbers may be possible. (Contributed by Jim Kingdon, 16-Oct-2021.) |
Ref | Expression |
---|---|
modqval | ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (𝐴 mod 𝐵) = (𝐴 − (𝐵 · (⌊‘(𝐴 / 𝐵))))) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | qre 9209 | . . 3 ⊢ (𝐴 ∈ ℚ → 𝐴 ∈ ℝ) | |
2 | 1 | 3ad2ant1 967 | . 2 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → 𝐴 ∈ ℝ) |
3 | qre 9209 | . . . 4 ⊢ (𝐵 ∈ ℚ → 𝐵 ∈ ℝ) | |
4 | 3 | 3ad2ant2 968 | . . 3 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → 𝐵 ∈ ℝ) |
5 | simp3 948 | . . 3 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → 0 < 𝐵) | |
6 | 4, 5 | elrpd 9270 | . 2 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → 𝐵 ∈ ℝ+) |
7 | 5 | gt0ne0d 8087 | . . . . . . 7 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → 𝐵 ≠ 0) |
8 | qdivcl 9227 | . . . . . . 7 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 𝐵 ≠ 0) → (𝐴 / 𝐵) ∈ ℚ) | |
9 | 7, 8 | syld3an3 1226 | . . . . . 6 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (𝐴 / 𝐵) ∈ ℚ) |
10 | 9 | flqcld 9833 | . . . . 5 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (⌊‘(𝐴 / 𝐵)) ∈ ℤ) |
11 | 10 | zred 8967 | . . . 4 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (⌊‘(𝐴 / 𝐵)) ∈ ℝ) |
12 | 4, 11 | remulcld 7615 | . . 3 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (𝐵 · (⌊‘(𝐴 / 𝐵))) ∈ ℝ) |
13 | 2, 12 | resubcld 7956 | . 2 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (𝐴 − (𝐵 · (⌊‘(𝐴 / 𝐵)))) ∈ ℝ) |
14 | oveq1 5697 | . . . . . 6 ⊢ (𝑥 = 𝐴 → (𝑥 / 𝑦) = (𝐴 / 𝑦)) | |
15 | 14 | fveq2d 5344 | . . . . 5 ⊢ (𝑥 = 𝐴 → (⌊‘(𝑥 / 𝑦)) = (⌊‘(𝐴 / 𝑦))) |
16 | 15 | oveq2d 5706 | . . . 4 ⊢ (𝑥 = 𝐴 → (𝑦 · (⌊‘(𝑥 / 𝑦))) = (𝑦 · (⌊‘(𝐴 / 𝑦)))) |
17 | oveq12 5699 | . . . 4 ⊢ ((𝑥 = 𝐴 ∧ (𝑦 · (⌊‘(𝑥 / 𝑦))) = (𝑦 · (⌊‘(𝐴 / 𝑦)))) → (𝑥 − (𝑦 · (⌊‘(𝑥 / 𝑦)))) = (𝐴 − (𝑦 · (⌊‘(𝐴 / 𝑦))))) | |
18 | 16, 17 | mpdan 413 | . . 3 ⊢ (𝑥 = 𝐴 → (𝑥 − (𝑦 · (⌊‘(𝑥 / 𝑦)))) = (𝐴 − (𝑦 · (⌊‘(𝐴 / 𝑦))))) |
19 | oveq2 5698 | . . . . . 6 ⊢ (𝑦 = 𝐵 → (𝐴 / 𝑦) = (𝐴 / 𝐵)) | |
20 | 19 | fveq2d 5344 | . . . . 5 ⊢ (𝑦 = 𝐵 → (⌊‘(𝐴 / 𝑦)) = (⌊‘(𝐴 / 𝐵))) |
21 | oveq12 5699 | . . . . 5 ⊢ ((𝑦 = 𝐵 ∧ (⌊‘(𝐴 / 𝑦)) = (⌊‘(𝐴 / 𝐵))) → (𝑦 · (⌊‘(𝐴 / 𝑦))) = (𝐵 · (⌊‘(𝐴 / 𝐵)))) | |
22 | 20, 21 | mpdan 413 | . . . 4 ⊢ (𝑦 = 𝐵 → (𝑦 · (⌊‘(𝐴 / 𝑦))) = (𝐵 · (⌊‘(𝐴 / 𝐵)))) |
23 | 22 | oveq2d 5706 | . . 3 ⊢ (𝑦 = 𝐵 → (𝐴 − (𝑦 · (⌊‘(𝐴 / 𝑦)))) = (𝐴 − (𝐵 · (⌊‘(𝐴 / 𝐵))))) |
24 | df-mod 9879 | . . 3 ⊢ mod = (𝑥 ∈ ℝ, 𝑦 ∈ ℝ+ ↦ (𝑥 − (𝑦 · (⌊‘(𝑥 / 𝑦))))) | |
25 | 18, 23, 24 | ovmpt2g 5817 | . 2 ⊢ ((𝐴 ∈ ℝ ∧ 𝐵 ∈ ℝ+ ∧ (𝐴 − (𝐵 · (⌊‘(𝐴 / 𝐵)))) ∈ ℝ) → (𝐴 mod 𝐵) = (𝐴 − (𝐵 · (⌊‘(𝐴 / 𝐵))))) |
26 | 2, 6, 13, 25 | syl3anc 1181 | 1 ⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 0 < 𝐵) → (𝐴 mod 𝐵) = (𝐴 − (𝐵 · (⌊‘(𝐴 / 𝐵))))) |
Colors of variables: wff set class |
Syntax hints: → wi 4 ∧ w3a 927 = wceq 1296 ∈ wcel 1445 ≠ wne 2262 class class class wbr 3867 ‘cfv 5049 (class class class)co 5690 ℝcr 7446 0cc0 7447 · cmul 7452 < clt 7619 − cmin 7750 / cdiv 8236 ℚcq 9203 ℝ+crp 9233 ⌊cfl 9824 mod cmo 9878 |
This theorem was proved from axioms: ax-1 5 ax-2 6 ax-mp 7 ax-ia1 105 ax-ia2 106 ax-ia3 107 ax-in1 582 ax-in2 583 ax-io 668 ax-5 1388 ax-7 1389 ax-gen 1390 ax-ie1 1434 ax-ie2 1435 ax-8 1447 ax-10 1448 ax-11 1449 ax-i12 1450 ax-bndl 1451 ax-4 1452 ax-13 1456 ax-14 1457 ax-17 1471 ax-i9 1475 ax-ial 1479 ax-i5r 1480 ax-ext 2077 ax-sep 3978 ax-pow 4030 ax-pr 4060 ax-un 4284 ax-setind 4381 ax-cnex 7533 ax-resscn 7534 ax-1cn 7535 ax-1re 7536 ax-icn 7537 ax-addcl 7538 ax-addrcl 7539 ax-mulcl 7540 ax-mulrcl 7541 ax-addcom 7542 ax-mulcom 7543 ax-addass 7544 ax-mulass 7545 ax-distr 7546 ax-i2m1 7547 ax-0lt1 7548 ax-1rid 7549 ax-0id 7550 ax-rnegex 7551 ax-precex 7552 ax-cnre 7553 ax-pre-ltirr 7554 ax-pre-ltwlin 7555 ax-pre-lttrn 7556 ax-pre-apti 7557 ax-pre-ltadd 7558 ax-pre-mulgt0 7559 ax-pre-mulext 7560 ax-arch 7561 |
This theorem depends on definitions: df-bi 116 df-3or 928 df-3an 929 df-tru 1299 df-fal 1302 df-nf 1402 df-sb 1700 df-eu 1958 df-mo 1959 df-clab 2082 df-cleq 2088 df-clel 2091 df-nfc 2224 df-ne 2263 df-nel 2358 df-ral 2375 df-rex 2376 df-reu 2377 df-rmo 2378 df-rab 2379 df-v 2635 df-sbc 2855 df-csb 2948 df-dif 3015 df-un 3017 df-in 3019 df-ss 3026 df-pw 3451 df-sn 3472 df-pr 3473 df-op 3475 df-uni 3676 df-int 3711 df-iun 3754 df-br 3868 df-opab 3922 df-mpt 3923 df-id 4144 df-po 4147 df-iso 4148 df-xp 4473 df-rel 4474 df-cnv 4475 df-co 4476 df-dm 4477 df-rn 4478 df-res 4479 df-ima 4480 df-iota 5014 df-fun 5051 df-fn 5052 df-f 5053 df-fv 5057 df-riota 5646 df-ov 5693 df-oprab 5694 df-mpt2 5695 df-1st 5949 df-2nd 5950 df-pnf 7621 df-mnf 7622 df-xr 7623 df-ltxr 7624 df-le 7625 df-sub 7752 df-neg 7753 df-reap 8149 df-ap 8156 df-div 8237 df-inn 8521 df-n0 8772 df-z 8849 df-q 9204 df-rp 9234 df-fl 9826 df-mod 9879 |
This theorem is referenced by: modqvalr 9881 modqcl 9882 modq0 9885 modqge0 9888 modqlt 9889 modqdiffl 9891 modqfrac 9893 modqmulnn 9898 zmodcl 9900 modqid 9905 modqcyc 9915 modqadd1 9917 modqmul1 9933 modqdi 9948 modqsubdir 9949 iexpcyc 10174 dvdsmod 11290 divalgmod 11354 modgcd 11409 |
Copyright terms: Public domain | W3C validator |