Theorem 2exple2exp 32905

Description: If a nonnegative integer 𝑋 is a multiple of a power of two, but less than the next power of two, it is itself a power of two. (Contributed by Thierry Arnoux, 19-Oct-2025.)

Hypotheses

Ref	Expression
2exple2exp.1	⊢ (𝜑 → 𝑋 ∈ ℕ)
2exple2exp.2	⊢ (𝜑 → 𝐾 ∈ ℕ0)
2exple2exp.3	⊢ (𝜑 → (2↑𝐾) ∥ 𝑋)
2exple2exp.4	⊢ (𝜑 → 𝑋 ≤ (2↑(𝐾 + 1)))

Assertion

Ref	Expression
2exple2exp	⊢ (𝜑 → ∃𝑛 ∈ ℕ0 𝑋 = (2↑𝑛))

Distinct variable groups:   𝑛,𝐾   𝑛,𝑋   𝜑,𝑛

Proof of Theorem 2exple2exp

Dummy variable 𝑚 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		oveq2 7366	. . . 4 ⊢ (𝑛 = 𝐾 → (2↑𝑛) = (2↑𝐾))
2	1	eqeq2d 2746	. . 3 ⊢ (𝑛 = 𝐾 → (𝑋 = (2↑𝑛) ↔ 𝑋 = (2↑𝐾)))
3		2exple2exp.2	. . . 4 ⊢ (𝜑 → 𝐾 ∈ ℕ0)
4	3	adantr 480	. . 3 ⊢ ((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) → 𝐾 ∈ ℕ0)
5		simplr 769	. . . . . . . 8 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 ∈ ℕ)
6	5	nnnn0d 12464	. . . . . . 7 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 ∈ ℕ0)
7		2nn 12220	. . . . . . . . . . . . . 14 ⊢ 2 ∈ ℕ
8	7	a1i 11	. . . . . . . . . . . . 13 ⊢ (𝜑 → 2 ∈ ℕ)
9	8, 3	nnexpcld 14170	. . . . . . . . . . . 12 ⊢ (𝜑 → (2↑𝐾) ∈ ℕ)
10	9	nncnd 12163	. . . . . . . . . . 11 ⊢ (𝜑 → (2↑𝐾) ∈ ℂ)
11	10	ad3antrrr 731	. . . . . . . . . 10 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (2↑𝐾) ∈ ℂ)
12	5	nncnd 12163	. . . . . . . . . 10 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 ∈ ℂ)
13	11, 12	mulcomd 11155	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → ((2↑𝐾) · 𝑚) = (𝑚 · (2↑𝐾)))
14		simpr 484	. . . . . . . . . 10 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (𝑚 · (2↑𝐾)) = 𝑋)
15		simpllr 776	. . . . . . . . . . 11 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑋 < (2↑(𝐾 + 1)))
16		2cnd 12225	. . . . . . . . . . . 12 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 2 ∈ ℂ)
17	3	ad3antrrr 731	. . . . . . . . . . . 12 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝐾 ∈ ℕ0)
18	16, 17	expp1d 14072	. . . . . . . . . . 11 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (2↑(𝐾 + 1)) = ((2↑𝐾) · 2))
19	15, 18	breqtrd 5123	. . . . . . . . . 10 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑋 < ((2↑𝐾) · 2))
20	14, 19	eqbrtrd 5119	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (𝑚 · (2↑𝐾)) < ((2↑𝐾) · 2))
21	13, 20	eqbrtrd 5119	. . . . . . . 8 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → ((2↑𝐾) · 𝑚) < ((2↑𝐾) · 2))
22	5	nnred 12162	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 ∈ ℝ)
23		2re 12221	. . . . . . . . . 10 ⊢ 2 ∈ ℝ
24	23	a1i 11	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 2 ∈ ℝ)
25	9	ad3antrrr 731	. . . . . . . . . 10 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (2↑𝐾) ∈ ℕ)
26	25	nnrpd 12949	. . . . . . . . 9 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (2↑𝐾) ∈ ℝ+)
27	22, 24, 26	ltmul2d 12993	. . . . . . . 8 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (𝑚 < 2 ↔ ((2↑𝐾) · 𝑚) < ((2↑𝐾) · 2)))
28	21, 27	mpbird 257	. . . . . . 7 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 < 2)
29	5	nnne0d 12197	. . . . . . . 8 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 ≠ 0)
30	29	neneqd 2936	. . . . . . 7 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → ¬ 𝑚 = 0)
31		nn0lt2 12557	. . . . . . . 8 ⊢ ((𝑚 ∈ ℕ0 ∧ 𝑚 < 2) → (𝑚 = 0 ∨ 𝑚 = 1))
32	31	orcanai 1005	. . . . . . 7 ⊢ (((𝑚 ∈ ℕ0 ∧ 𝑚 < 2) ∧ ¬ 𝑚 = 0) → 𝑚 = 1)
33	6, 28, 30, 32	syl21anc 838	. . . . . 6 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑚 = 1)
34	33	oveq1d 7373	. . . . 5 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (𝑚 · (2↑𝐾)) = (1 · (2↑𝐾)))
35	11	mullidd 11152	. . . . 5 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → (1 · (2↑𝐾)) = (2↑𝐾))
36	34, 14, 35	3eqtr3d 2778	. . . 4 ⊢ ((((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) ∧ 𝑚 ∈ ℕ) ∧ (𝑚 · (2↑𝐾)) = 𝑋) → 𝑋 = (2↑𝐾))
37		2exple2exp.1	. . . . . 6 ⊢ (𝜑 → 𝑋 ∈ ℕ)
38		2exple2exp.3	. . . . . 6 ⊢ (𝜑 → (2↑𝐾) ∥ 𝑋)
39		nndivides 16191	. . . . . . 7 ⊢ (((2↑𝐾) ∈ ℕ ∧ 𝑋 ∈ ℕ) → ((2↑𝐾) ∥ 𝑋 ↔ ∃𝑚 ∈ ℕ (𝑚 · (2↑𝐾)) = 𝑋))
40	39	biimpa 476	. . . . . 6 ⊢ ((((2↑𝐾) ∈ ℕ ∧ 𝑋 ∈ ℕ) ∧ (2↑𝐾) ∥ 𝑋) → ∃𝑚 ∈ ℕ (𝑚 · (2↑𝐾)) = 𝑋)
41	9, 37, 38, 40	syl21anc 838	. . . . 5 ⊢ (𝜑 → ∃𝑚 ∈ ℕ (𝑚 · (2↑𝐾)) = 𝑋)
42	41	adantr 480	. . . 4 ⊢ ((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) → ∃𝑚 ∈ ℕ (𝑚 · (2↑𝐾)) = 𝑋)
43	36, 42	r19.29a 3143	. . 3 ⊢ ((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) → 𝑋 = (2↑𝐾))
44	2, 4, 43	rspcedvdw 3578	. 2 ⊢ ((𝜑 ∧ 𝑋 < (2↑(𝐾 + 1))) → ∃𝑛 ∈ ℕ0 𝑋 = (2↑𝑛))
45		oveq2 7366	. . . 4 ⊢ (𝑛 = (𝐾 + 1) → (2↑𝑛) = (2↑(𝐾 + 1)))
46	45	eqeq2d 2746	. . 3 ⊢ (𝑛 = (𝐾 + 1) → (𝑋 = (2↑𝑛) ↔ 𝑋 = (2↑(𝐾 + 1))))
47		peano2nn0 12443	. . . . 5 ⊢ (𝐾 ∈ ℕ0 → (𝐾 + 1) ∈ ℕ0)
48	3, 47	syl 17	. . . 4 ⊢ (𝜑 → (𝐾 + 1) ∈ ℕ0)
49	48	adantr 480	. . 3 ⊢ ((𝜑 ∧ 𝑋 = (2↑(𝐾 + 1))) → (𝐾 + 1) ∈ ℕ0)
50		simpr 484	. . 3 ⊢ ((𝜑 ∧ 𝑋 = (2↑(𝐾 + 1))) → 𝑋 = (2↑(𝐾 + 1)))
51	46, 49, 50	rspcedvdw 3578	. 2 ⊢ ((𝜑 ∧ 𝑋 = (2↑(𝐾 + 1))) → ∃𝑛 ∈ ℕ0 𝑋 = (2↑𝑛))
52	37	nnred 12162	. . 3 ⊢ (𝜑 → 𝑋 ∈ ℝ)
53	23	a1i 11	. . . 4 ⊢ (𝜑 → 2 ∈ ℝ)
54	53, 48	reexpcld 14088	. . 3 ⊢ (𝜑 → (2↑(𝐾 + 1)) ∈ ℝ)
55		2exple2exp.4	. . 3 ⊢ (𝜑 → 𝑋 ≤ (2↑(𝐾 + 1)))
56		leloe 11221	. . . 4 ⊢ ((𝑋 ∈ ℝ ∧ (2↑(𝐾 + 1)) ∈ ℝ) → (𝑋 ≤ (2↑(𝐾 + 1)) ↔ (𝑋 < (2↑(𝐾 + 1)) ∨ 𝑋 = (2↑(𝐾 + 1)))))
57	56	biimpa 476	. . 3 ⊢ (((𝑋 ∈ ℝ ∧ (2↑(𝐾 + 1)) ∈ ℝ) ∧ 𝑋 ≤ (2↑(𝐾 + 1))) → (𝑋 < (2↑(𝐾 + 1)) ∨ 𝑋 = (2↑(𝐾 + 1))))
58	52, 54, 55, 57	syl21anc 838	. 2 ⊢ (𝜑 → (𝑋 < (2↑(𝐾 + 1)) ∨ 𝑋 = (2↑(𝐾 + 1))))
59	44, 51, 58	mpjaodan 961	1 ⊢ (𝜑 → ∃𝑛 ∈ ℕ0 𝑋 = (2↑𝑛))

Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 395   ∨ wo 848   = wceq 1542   ∈ wcel 2114  ∃wrex 3059   class class class wbr 5097  (class class class)co 7358  ℂcc 11026  ℝcr 11027  0cc0 11028  1c1 11029   + caddc 11031   · cmul 11033   < clt 11168   ≤ cle 11169  ℕcn 12147  2c2 12202  ℕ₀cn0 12403  ↑cexp 13986   ∥ cdvds 16181

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1969  ax-7 2010  ax-8 2116  ax-9 2124  ax-10 2147  ax-11 2163  ax-12 2183  ax-ext 2707  ax-sep 5240  ax-nul 5250  ax-pow 5309  ax-pr 5376  ax-un 7680  ax-cnex 11084  ax-resscn 11085  ax-1cn 11086  ax-icn 11087  ax-addcl 11088  ax-addrcl 11089  ax-mulcl 11090  ax-mulrcl 11091  ax-mulcom 11092  ax-addass 11093  ax-mulass 11094  ax-distr 11095  ax-i2m1 11096  ax-1ne0 11097  ax-1rid 11098  ax-rnegex 11099  ax-rrecex 11100  ax-cnre 11101  ax-pre-lttri 11102  ax-pre-lttrn 11103  ax-pre-ltadd 11104  ax-pre-mulgt0 11105

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1545  df-fal 1555  df-ex 1782  df-nf 1786  df-sb 2069  df-mo 2538  df-eu 2568  df-clab 2714  df-cleq 2727  df-clel 2810  df-nfc 2884  df-ne 2932  df-nel 3036  df-ral 3051  df-rex 3060  df-rmo 3349  df-reu 3350  df-rab 3399  df-v 3441  df-sbc 3740  df-csb 3849  df-dif 3903  df-un 3905  df-in 3907  df-ss 3917  df-pss 3920  df-nul 4285  df-if 4479  df-pw 4555  df-sn 4580  df-pr 4582  df-op 4586  df-uni 4863  df-iun 4947  df-br 5098  df-opab 5160  df-mpt 5179  df-tr 5205  df-id 5518  df-eprel 5523  df-po 5531  df-so 5532  df-fr 5576  df-we 5578  df-xp 5629  df-rel 5630  df-cnv 5631  df-co 5632  df-dm 5633  df-rn 5634  df-res 5635  df-ima 5636  df-pred 6258  df-ord 6319  df-on 6320  df-lim 6321  df-suc 6322  df-iota 6447  df-fun 6493  df-fn 6494  df-f 6495  df-f1 6496  df-fo 6497  df-f1o 6498  df-fv 6499  df-riota 7315  df-ov 7361  df-oprab 7362  df-mpo 7363  df-om 7809  df-2nd 7934  df-frecs 8223  df-wrecs 8254  df-recs 8303  df-rdg 8341  df-er 8635  df-en 8886  df-dom 8887  df-sdom 8888  df-pnf 11170  df-mnf 11171  df-xr 11172  df-ltxr 11173  df-le 11174  df-sub 11368  df-neg 11369  df-div 11797  df-nn 12148  df-2 12210  df-n0 12404  df-z 12491  df-uz 12754  df-rp 12908  df-seq 13927  df-exp 13987  df-dvds 16182

This theorem is referenced by:  fldext2rspun  33818