![]() |
Mathbox for Alexander van der Vekens |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > Mathboxes > nnpw2p | Structured version Visualization version GIF version |
Description: Every positive integer can be represented as the sum of a power of 2 and a "remainder" smaller than the power. (Contributed by AV, 31-May-2020.) |
Ref | Expression |
---|---|
nnpw2p | ⊢ (𝑁 ∈ ℕ → ∃𝑖 ∈ ℕ0 ∃𝑟 ∈ (0..^(2↑𝑖))𝑁 = ((2↑𝑖) + 𝑟)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | blennnelnn 44034 | . . 3 ⊢ (𝑁 ∈ ℕ → (#b‘𝑁) ∈ ℕ) | |
2 | nnm1nn0 11749 | . . 3 ⊢ ((#b‘𝑁) ∈ ℕ → ((#b‘𝑁) − 1) ∈ ℕ0) | |
3 | 1, 2 | syl 17 | . 2 ⊢ (𝑁 ∈ ℕ → ((#b‘𝑁) − 1) ∈ ℕ0) |
4 | oveq2 6983 | . . . . 5 ⊢ (𝑖 = ((#b‘𝑁) − 1) → (2↑𝑖) = (2↑((#b‘𝑁) − 1))) | |
5 | 4 | oveq2d 6991 | . . . 4 ⊢ (𝑖 = ((#b‘𝑁) − 1) → (0..^(2↑𝑖)) = (0..^(2↑((#b‘𝑁) − 1)))) |
6 | 4 | oveq1d 6990 | . . . . 5 ⊢ (𝑖 = ((#b‘𝑁) − 1) → ((2↑𝑖) + 𝑟) = ((2↑((#b‘𝑁) − 1)) + 𝑟)) |
7 | 6 | eqeq2d 2783 | . . . 4 ⊢ (𝑖 = ((#b‘𝑁) − 1) → (𝑁 = ((2↑𝑖) + 𝑟) ↔ 𝑁 = ((2↑((#b‘𝑁) − 1)) + 𝑟))) |
8 | 5, 7 | rexeqbidv 3337 | . . 3 ⊢ (𝑖 = ((#b‘𝑁) − 1) → (∃𝑟 ∈ (0..^(2↑𝑖))𝑁 = ((2↑𝑖) + 𝑟) ↔ ∃𝑟 ∈ (0..^(2↑((#b‘𝑁) − 1)))𝑁 = ((2↑((#b‘𝑁) − 1)) + 𝑟))) |
9 | 8 | adantl 474 | . 2 ⊢ ((𝑁 ∈ ℕ ∧ 𝑖 = ((#b‘𝑁) − 1)) → (∃𝑟 ∈ (0..^(2↑𝑖))𝑁 = ((2↑𝑖) + 𝑟) ↔ ∃𝑟 ∈ (0..^(2↑((#b‘𝑁) − 1)))𝑁 = ((2↑((#b‘𝑁) − 1)) + 𝑟))) |
10 | nnz 11816 | . . . 4 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℤ) | |
11 | 2nn 11512 | . . . . . 6 ⊢ 2 ∈ ℕ | |
12 | 11 | a1i 11 | . . . . 5 ⊢ (𝑁 ∈ ℕ → 2 ∈ ℕ) |
13 | 12, 3 | nnexpcld 13420 | . . . 4 ⊢ (𝑁 ∈ ℕ → (2↑((#b‘𝑁) − 1)) ∈ ℕ) |
14 | zmodfzo 13076 | . . . 4 ⊢ ((𝑁 ∈ ℤ ∧ (2↑((#b‘𝑁) − 1)) ∈ ℕ) → (𝑁 mod (2↑((#b‘𝑁) − 1))) ∈ (0..^(2↑((#b‘𝑁) − 1)))) | |
15 | 10, 13, 14 | syl2anc 576 | . . 3 ⊢ (𝑁 ∈ ℕ → (𝑁 mod (2↑((#b‘𝑁) − 1))) ∈ (0..^(2↑((#b‘𝑁) − 1)))) |
16 | oveq2 6983 | . . . . 5 ⊢ (𝑟 = (𝑁 mod (2↑((#b‘𝑁) − 1))) → ((2↑((#b‘𝑁) − 1)) + 𝑟) = ((2↑((#b‘𝑁) − 1)) + (𝑁 mod (2↑((#b‘𝑁) − 1))))) | |
17 | 16 | eqeq2d 2783 | . . . 4 ⊢ (𝑟 = (𝑁 mod (2↑((#b‘𝑁) − 1))) → (𝑁 = ((2↑((#b‘𝑁) − 1)) + 𝑟) ↔ 𝑁 = ((2↑((#b‘𝑁) − 1)) + (𝑁 mod (2↑((#b‘𝑁) − 1)))))) |
18 | 17 | adantl 474 | . . 3 ⊢ ((𝑁 ∈ ℕ ∧ 𝑟 = (𝑁 mod (2↑((#b‘𝑁) − 1)))) → (𝑁 = ((2↑((#b‘𝑁) − 1)) + 𝑟) ↔ 𝑁 = ((2↑((#b‘𝑁) − 1)) + (𝑁 mod (2↑((#b‘𝑁) − 1)))))) |
19 | nnpw2pmod 44041 | . . 3 ⊢ (𝑁 ∈ ℕ → 𝑁 = ((2↑((#b‘𝑁) − 1)) + (𝑁 mod (2↑((#b‘𝑁) − 1))))) | |
20 | 15, 18, 19 | rspcedvd 3537 | . 2 ⊢ (𝑁 ∈ ℕ → ∃𝑟 ∈ (0..^(2↑((#b‘𝑁) − 1)))𝑁 = ((2↑((#b‘𝑁) − 1)) + 𝑟)) |
21 | 3, 9, 20 | rspcedvd 3537 | 1 ⊢ (𝑁 ∈ ℕ → ∃𝑖 ∈ ℕ0 ∃𝑟 ∈ (0..^(2↑𝑖))𝑁 = ((2↑𝑖) + 𝑟)) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ↔ wb 198 = wceq 1508 ∈ wcel 2051 ∃wrex 3084 ‘cfv 6186 (class class class)co 6975 0cc0 10334 1c1 10335 + caddc 10337 − cmin 10669 ℕcn 11438 2c2 11494 ℕ0cn0 11706 ℤcz 11792 ..^cfzo 12848 mod cmo 13051 ↑cexp 13243 #bcblen 44027 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1759 ax-4 1773 ax-5 1870 ax-6 1929 ax-7 1966 ax-8 2053 ax-9 2060 ax-10 2080 ax-11 2094 ax-12 2107 ax-13 2302 ax-ext 2745 ax-rep 5046 ax-sep 5057 ax-nul 5064 ax-pow 5116 ax-pr 5183 ax-un 7278 ax-inf2 8897 ax-cnex 10390 ax-resscn 10391 ax-1cn 10392 ax-icn 10393 ax-addcl 10394 ax-addrcl 10395 ax-mulcl 10396 ax-mulrcl 10397 ax-mulcom 10398 ax-addass 10399 ax-mulass 10400 ax-distr 10401 ax-i2m1 10402 ax-1ne0 10403 ax-1rid 10404 ax-rnegex 10405 ax-rrecex 10406 ax-cnre 10407 ax-pre-lttri 10408 ax-pre-lttrn 10409 ax-pre-ltadd 10410 ax-pre-mulgt0 10411 ax-pre-sup 10412 ax-addf 10413 ax-mulf 10414 |
This theorem depends on definitions: df-bi 199 df-an 388 df-or 835 df-3or 1070 df-3an 1071 df-tru 1511 df-fal 1521 df-ex 1744 df-nf 1748 df-sb 2017 df-mo 2548 df-eu 2585 df-clab 2754 df-cleq 2766 df-clel 2841 df-nfc 2913 df-ne 2963 df-nel 3069 df-ral 3088 df-rex 3089 df-reu 3090 df-rmo 3091 df-rab 3092 df-v 3412 df-sbc 3677 df-csb 3782 df-dif 3827 df-un 3829 df-in 3831 df-ss 3838 df-pss 3840 df-nul 4174 df-if 4346 df-pw 4419 df-sn 4437 df-pr 4439 df-tp 4441 df-op 4443 df-uni 4710 df-int 4747 df-iun 4791 df-iin 4792 df-br 4927 df-opab 4989 df-mpt 5006 df-tr 5028 df-id 5309 df-eprel 5314 df-po 5323 df-so 5324 df-fr 5363 df-se 5364 df-we 5365 df-xp 5410 df-rel 5411 df-cnv 5412 df-co 5413 df-dm 5414 df-rn 5415 df-res 5416 df-ima 5417 df-pred 5984 df-ord 6030 df-on 6031 df-lim 6032 df-suc 6033 df-iota 6150 df-fun 6188 df-fn 6189 df-f 6190 df-f1 6191 df-fo 6192 df-f1o 6193 df-fv 6194 df-isom 6195 df-riota 6936 df-ov 6978 df-oprab 6979 df-mpo 6980 df-of 7226 df-om 7396 df-1st 7500 df-2nd 7501 df-supp 7633 df-wrecs 7749 df-recs 7811 df-rdg 7849 df-1o 7904 df-2o 7905 df-oadd 7908 df-er 8088 df-map 8207 df-pm 8208 df-ixp 8259 df-en 8306 df-dom 8307 df-sdom 8308 df-fin 8309 df-fsupp 8628 df-fi 8669 df-sup 8700 df-inf 8701 df-oi 8768 df-card 9161 df-cda 9387 df-pnf 10475 df-mnf 10476 df-xr 10477 df-ltxr 10478 df-le 10479 df-sub 10671 df-neg 10672 df-div 11098 df-nn 11439 df-2 11502 df-3 11503 df-4 11504 df-5 11505 df-6 11506 df-7 11507 df-8 11508 df-9 11509 df-n0 11707 df-z 11793 df-dec 11911 df-uz 12058 df-q 12162 df-rp 12204 df-xneg 12323 df-xadd 12324 df-xmul 12325 df-ioo 12557 df-ioc 12558 df-ico 12559 df-icc 12560 df-fz 12708 df-fzo 12849 df-fl 12976 df-mod 13052 df-seq 13184 df-exp 13244 df-fac 13448 df-bc 13477 df-hash 13505 df-shft 14286 df-cj 14318 df-re 14319 df-im 14320 df-sqrt 14454 df-abs 14455 df-limsup 14688 df-clim 14705 df-rlim 14706 df-sum 14903 df-ef 15280 df-sin 15282 df-cos 15283 df-pi 15285 df-struct 16340 df-ndx 16341 df-slot 16342 df-base 16344 df-sets 16345 df-ress 16346 df-plusg 16433 df-mulr 16434 df-starv 16435 df-sca 16436 df-vsca 16437 df-ip 16438 df-tset 16439 df-ple 16440 df-ds 16442 df-unif 16443 df-hom 16444 df-cco 16445 df-rest 16551 df-topn 16552 df-0g 16570 df-gsum 16571 df-topgen 16572 df-pt 16573 df-prds 16576 df-xrs 16630 df-qtop 16635 df-imas 16636 df-xps 16638 df-mre 16728 df-mrc 16729 df-acs 16731 df-mgm 17723 df-sgrp 17765 df-mnd 17776 df-submnd 17817 df-mulg 18025 df-cntz 18231 df-cmn 18681 df-psmet 20255 df-xmet 20256 df-met 20257 df-bl 20258 df-mopn 20259 df-fbas 20260 df-fg 20261 df-cnfld 20264 df-top 21222 df-topon 21239 df-topsp 21261 df-bases 21274 df-cld 21347 df-ntr 21348 df-cls 21349 df-nei 21426 df-lp 21464 df-perf 21465 df-cn 21555 df-cnp 21556 df-haus 21643 df-tx 21890 df-hmeo 22083 df-fil 22174 df-fm 22266 df-flim 22267 df-flf 22268 df-xms 22649 df-ms 22650 df-tms 22651 df-cncf 23205 df-limc 24183 df-dv 24184 df-log 24857 df-cxp 24858 df-logb 25060 df-blen 44028 |
This theorem is referenced by: nnpw2pb 44045 |
Copyright terms: Public domain | W3C validator |