P. 163 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 16201-16300   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	rplogb1 16201	The logarithm of 1 to an arbitrary base 𝐵 is 0. Property 1(b) of [Cohen4] p. 361. See log1 16112. (Contributed by Stefan O'Rear, 19-Sep-2014.) (Revised by Thierry Arnoux, 27-Sep-2017.)
⊢ ((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) → (𝐵 logb 1) = 0)
Theorem	rpelogb 16202	The general logarithm of a number to the base being Euler's constant is the natural logarithm of the number. Put another way, using e as the base in logb is the same as log. Definition in [Cohen4] p. 352. (Contributed by David A. Wheeler, 17-Oct-2017.) (Revised by David A. Wheeler and AV, 16-Jun-2020.)
⊢ (𝐴 ∈ ℝ+ → (e logb 𝐴) = (log‘𝐴))
Theorem	rplogbchbase 16203	Change of base for logarithms. Property in [Cohen4] p. 367. (Contributed by AV, 11-Jun-2020.)
⊢ (((𝐴 ∈ ℝ+ ∧ 𝐴 # 1) ∧ (𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ 𝑋 ∈ ℝ+) → (𝐴 logb 𝑋) = ((𝐵 logb 𝑋) / (𝐵 logb 𝐴)))
Theorem	relogbval 16204	Value of the general logarithm with integer base. (Contributed by Thierry Arnoux, 27-Sep-2017.)
⊢ ((𝐵 ∈ (ℤ≥‘2) ∧ 𝑋 ∈ ℝ+) → (𝐵 logb 𝑋) = ((log‘𝑋) / (log‘𝐵)))
Theorem	relogbzcl 16205	Closure of the general logarithm with integer base on positive reals. (Contributed by Thierry Arnoux, 27-Sep-2017.) (Proof shortened by AV, 9-Jun-2020.)
⊢ ((𝐵 ∈ (ℤ≥‘2) ∧ 𝑋 ∈ ℝ+) → (𝐵 logb 𝑋) ∈ ℝ)
Theorem	rplogbreexp 16206	Power law for the general logarithm for real powers: The logarithm of a positive real number to the power of a real number is equal to the product of the exponent and the logarithm of the base of the power. Property 4 of [Cohen4] p. 361. (Contributed by AV, 9-Jun-2020.)
⊢ (((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ 𝐶 ∈ ℝ+ ∧ 𝐸 ∈ ℝ) → (𝐵 logb (𝐶↑𝑐𝐸)) = (𝐸 · (𝐵 logb 𝐶)))
Theorem	rplogbzexp 16207	Power law for the general logarithm for integer powers: The logarithm of a positive real number to the power of an integer is equal to the product of the exponent and the logarithm of the base of the power. (Contributed by Stefan O'Rear, 19-Sep-2014.) (Revised by AV, 9-Jun-2020.)
⊢ (((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ 𝐶 ∈ ℝ+ ∧ 𝑁 ∈ ℤ) → (𝐵 logb (𝐶↑𝑁)) = (𝑁 · (𝐵 logb 𝐶)))
Theorem	rprelogbmul 16208	The logarithm of the product of two positive real numbers is the sum of logarithms. Property 2 of [Cohen4] p. 361. (Contributed by Stefan O'Rear, 19-Sep-2014.) (Revised by AV, 29-May-2020.)
⊢ (((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ (𝐴 ∈ ℝ+ ∧ 𝐶 ∈ ℝ+)) → (𝐵 logb (𝐴 · 𝐶)) = ((𝐵 logb 𝐴) + (𝐵 logb 𝐶)))
Theorem	rprelogbmulexp 16209	The logarithm of the product of a positive real and a positive real number to the power of a real number is the sum of the logarithm of the first real number and the scaled logarithm of the second real number. (Contributed by AV, 29-May-2020.)
⊢ (((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ (𝐴 ∈ ℝ+ ∧ 𝐶 ∈ ℝ+ ∧ 𝐸 ∈ ℝ)) → (𝐵 logb (𝐴 · (𝐶↑𝑐𝐸))) = ((𝐵 logb 𝐴) + (𝐸 · (𝐵 logb 𝐶))))
Theorem	rprelogbdiv 16210	The logarithm of the quotient of two positive real numbers is the difference of logarithms. Property 3 of [Cohen4] p. 361. (Contributed by AV, 29-May-2020.)
⊢ (((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ (𝐴 ∈ ℝ+ ∧ 𝐶 ∈ ℝ+)) → (𝐵 logb (𝐴 / 𝐶)) = ((𝐵 logb 𝐴) − (𝐵 logb 𝐶)))
Theorem	relogbexpap 16211	Identity law for general logarithm: the logarithm of a power to the base is the exponent. Property 6 of [Cohen4] p. 361. (Contributed by Stefan O'Rear, 19-Sep-2014.) (Revised by AV, 9-Jun-2020.)
⊢ ((𝐵 ∈ ℝ+ ∧ 𝐵 # 1 ∧ 𝑀 ∈ ℤ) → (𝐵 logb (𝐵↑𝑀)) = 𝑀)
Theorem	nnlogbexp 16212	Identity law for general logarithm with integer base. (Contributed by Stefan O'Rear, 19-Sep-2014.) (Revised by Thierry Arnoux, 27-Sep-2017.)
⊢ ((𝐵 ∈ (ℤ≥‘2) ∧ 𝑀 ∈ ℤ) → (𝐵 logb (𝐵↑𝑀)) = 𝑀)
Theorem	logbrec 16213	Logarithm of a reciprocal changes sign. Particular case of Property 3 of [Cohen4] p. 361. (Contributed by Thierry Arnoux, 27-Sep-2017.)
⊢ ((𝐵 ∈ (ℤ≥‘2) ∧ 𝐴 ∈ ℝ+) → (𝐵 logb (1 / 𝐴)) = -(𝐵 logb 𝐴))
Theorem	logbleb 16214	The general logarithm function is monotone/increasing. See logleb 16122. (Contributed by Stefan O'Rear, 19-Oct-2014.) (Revised by AV, 31-May-2020.)
⊢ ((𝐵 ∈ (ℤ≥‘2) ∧ 𝑋 ∈ ℝ+ ∧ 𝑌 ∈ ℝ+) → (𝑋 ≤ 𝑌 ↔ (𝐵 logb 𝑋) ≤ (𝐵 logb 𝑌)))
Theorem	logblt 16215	The general logarithm function is strictly monotone/increasing. Property 2 of [Cohen4] p. 377. See logltb 16121. (Contributed by Stefan O'Rear, 19-Oct-2014.) (Revised by Thierry Arnoux, 27-Sep-2017.)
⊢ ((𝐵 ∈ (ℤ≥‘2) ∧ 𝑋 ∈ ℝ+ ∧ 𝑌 ∈ ℝ+) → (𝑋 < 𝑌 ↔ (𝐵 logb 𝑋) < (𝐵 logb 𝑌)))
Theorem	rplogbcxp 16216	Identity law for the general logarithm for real numbers. (Contributed by AV, 22-May-2020.)
⊢ ((𝐵 ∈ ℝ+ ∧ 𝐵 # 1 ∧ 𝑋 ∈ ℝ) → (𝐵 logb (𝐵↑𝑐𝑋)) = 𝑋)
Theorem	rpcxplogb 16217	Identity law for the general logarithm. (Contributed by AV, 22-May-2020.)
⊢ ((𝐵 ∈ ℝ+ ∧ 𝐵 # 1 ∧ 𝑋 ∈ ℝ+) → (𝐵↑𝑐(𝐵 logb 𝑋)) = 𝑋)
Theorem	relogbcxpbap 16218	The logarithm is the inverse of the exponentiation. Observation in [Cohen4] p. 348. (Contributed by AV, 11-Jun-2020.)
⊢ (((𝐵 ∈ ℝ+ ∧ 𝐵 # 1) ∧ 𝑋 ∈ ℝ+ ∧ 𝑌 ∈ ℝ) → ((𝐵 logb 𝑋) = 𝑌 ↔ (𝐵↑𝑐𝑌) = 𝑋))
Theorem	logbgt0b 16219	The logarithm of a positive real number to a real base greater than 1 is positive iff the number is greater than 1. (Contributed by AV, 29-Dec-2022.)
⊢ ((𝐴 ∈ ℝ+ ∧ (𝐵 ∈ ℝ+ ∧ 1 < 𝐵)) → (0 < (𝐵 logb 𝐴) ↔ 1 < 𝐴))
Theorem	logbgcd1irr 16220	The logarithm of an integer greater than 1 to an integer base greater than 1 is not rational if the argument and the base are relatively prime. For example, (2 logb 9) ∈ (ℝ ∖ ℚ). (Contributed by AV, 29-Dec-2022.)
⊢ ((𝑋 ∈ (ℤ≥‘2) ∧ 𝐵 ∈ (ℤ≥‘2) ∧ (𝑋 gcd 𝐵) = 1) → (𝐵 logb 𝑋) ∈ (ℝ ∖ ℚ))
Theorem	logbgcd1irraplemexp 16221	Lemma for logbgcd1irrap 16223. Apartness of 𝑋↑𝑁 and 𝐵↑𝑀. (Contributed by Jim Kingdon, 11-Jul-2024.)
⊢ (𝜑 → 𝑋 ∈ (ℤ≥‘2))    &   ⊢ (𝜑 → 𝐵 ∈ (ℤ≥‘2))    &   ⊢ (𝜑 → (𝑋 gcd 𝐵) = 1)    &   ⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ)    ⇒   ⊢ (𝜑 → (𝑋↑𝑁) # (𝐵↑𝑀))
Theorem	logbgcd1irraplemap 16222	Lemma for logbgcd1irrap 16223. The result, with the rational number expressed as numerator and denominator. (Contributed by Jim Kingdon, 9-Jul-2024.)
⊢ (𝜑 → 𝑋 ∈ (ℤ≥‘2))    &   ⊢ (𝜑 → 𝐵 ∈ (ℤ≥‘2))    &   ⊢ (𝜑 → (𝑋 gcd 𝐵) = 1)    &   ⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ)    ⇒   ⊢ (𝜑 → (𝐵 logb 𝑋) # (𝑀 / 𝑁))
Theorem	logbgcd1irrap 16223	The logarithm of an integer greater than 1 to an integer base greater than 1 is irrational (in the sense of being apart from any rational number) if the argument and the base are relatively prime. For example, (2 logb 9) # 𝑄 where 𝑄 is rational. (Contributed by AV, 29-Dec-2022.)
⊢ (((𝑋 ∈ (ℤ≥‘2) ∧ 𝐵 ∈ (ℤ≥‘2)) ∧ ((𝑋 gcd 𝐵) = 1 ∧ 𝑄 ∈ ℚ)) → (𝐵 logb 𝑋) # 𝑄)
Theorem	2logb9irr 16224	Example for logbgcd1irr 16220. The logarithm of nine to base two is not rational. Also see 2logb9irrap 16230 which says that it is irrational (in the sense of being apart from any rational number). (Contributed by AV, 29-Dec-2022.)
⊢ (2 logb 9) ∈ (ℝ ∖ ℚ)
Theorem	logbprmirr 16225	The logarithm of a prime to a different prime base is not rational. For example, (2 logb 3) ∈ (ℝ ∖ ℚ) (see 2logb3irr 16226). (Contributed by AV, 31-Dec-2022.)
⊢ ((𝑋 ∈ ℙ ∧ 𝐵 ∈ ℙ ∧ 𝑋 ≠ 𝐵) → (𝐵 logb 𝑋) ∈ (ℝ ∖ ℚ))
Theorem	2logb3irr 16226	Example for logbprmirr 16225. The logarithm of three to base two is not rational. (Contributed by AV, 31-Dec-2022.)
⊢ (2 logb 3) ∈ (ℝ ∖ ℚ)
Theorem	2logb9irrALT 16227	Alternate proof of 2logb9irr 16224: The logarithm of nine to base two is not rational. (Contributed by AV, 31-Dec-2022.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (2 logb 9) ∈ (ℝ ∖ ℚ)
Theorem	sqrt2cxp2logb9e3 16228	The square root of two to the power of the logarithm of nine to base two is three. (√‘2) and (2 logb 9) are not rational (see sqrt2irr0 12967 resp. 2logb9irr 16224), satisfying the statement in 2irrexpq 16229. (Contributed by AV, 29-Dec-2022.)
⊢ ((√‘2)↑𝑐(2 logb 9)) = 3
Theorem	2irrexpq 16229*	There exist real numbers 𝑎 and 𝑏 which are not rational such that (𝑎↑𝑏) is rational. Statement in the Metamath book, section 1.1.5, footnote 27 on page 17, and the "constructive proof" for theorem 1.2 of [Bauer], p. 483. This is a constructive proof because it is based on two explicitly named non-rational numbers (√‘2) and (2 logb 9), see sqrt2irr0 12967, 2logb9irr 16224 and sqrt2cxp2logb9e3 16228. Therefore, this proof is acceptable/usable in intuitionistic logic. For a theorem which is the same but proves that 𝑎 and 𝑏 are irrational (in the sense of being apart from any rational number), see 2irrexpqap 16231. (Contributed by AV, 23-Dec-2022.)
⊢ ∃𝑎 ∈ (ℝ ∖ ℚ)∃𝑏 ∈ (ℝ ∖ ℚ)(𝑎↑𝑐𝑏) ∈ ℚ
Theorem	2logb9irrap 16230	Example for logbgcd1irrap 16223. The logarithm of nine to base two is irrational (in the sense of being apart from any rational number). (Contributed by Jim Kingdon, 12-Jul-2024.)
⊢ (𝑄 ∈ ℚ → (2 logb 9) # 𝑄)
Theorem	2irrexpqap 16231*	There exist real numbers 𝑎 and 𝑏 which are irrational (in the sense of being apart from any rational number) such that (𝑎↑𝑏) is rational. Statement in the Metamath book, section 1.1.5, footnote 27 on page 17, and the "constructive proof" for theorem 1.2 of [Bauer], p. 483. This is a constructive proof because it is based on two explicitly named irrational numbers (√‘2) and (2 logb 9), see sqrt2irrap 12984, 2logb9irrap 16230 and sqrt2cxp2logb9e3 16228. Therefore, this proof is acceptable/usable in intuitionistic logic. (Contributed by Jim Kingdon, 12-Jul-2024.)
⊢ ∃𝑎 ∈ ℝ ∃𝑏 ∈ ℝ (∀𝑝 ∈ ℚ 𝑎 # 𝑝 ∧ ∀𝑞 ∈ ℚ 𝑏 # 𝑞 ∧ (𝑎↑𝑐𝑏) ∈ ℚ)
Theorem	zprmlogbaplem1 16232	Lemma for zprmlogbap 16235. Rearranging an expression involving logarithms. (Contributed by Jim Kingdon, 20-Aug-2026.)
⊢ (𝜑 → 𝐵 ∈ ℙ)    &   ⊢ (𝜑 → 𝑀 ∈ ℕ)    &   ⊢ (𝜑 → ¬ 𝐵 ∥ 𝑀)    &   ⊢ (𝜑 → 𝐴 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (𝐵 logb ((𝐵↑𝐴) · 𝑀)) = (𝐴 + (𝐵 logb 𝑀)))
Theorem	zprmlogbaplem2 16233*	Lemma for zprmlogbap 16235. The logarithm is either rational or irrational. (Contributed by Jim Kingdon, 20-Aug-2026.)
⊢ (𝜑 → 𝐵 ∈ ℙ)    &   ⊢ (𝜑 → 𝑀 ∈ ℕ)    &   ⊢ (𝜑 → ¬ 𝐵 ∥ 𝑀)    &   ⊢ (𝜑 → 𝐴 ∈ ℕ0)    &   ⊢ 𝑋 = ((𝐵↑𝐴) · 𝑀)    ⇒   ⊢ (𝜑 → ((𝐵 logb 𝑋) ∈ ℚ ∨ ((𝐵 logb 𝑋) ∈ ℝ ∧ ∀𝑞 ∈ ℚ (𝐵 logb 𝑋) # 𝑞)))
Theorem	zprmlogbaplem3 16234*	Lemma for zprmlogbap 16235. Decomposing a natural number into a power of a prime base and a factor not divisible by that prime. (Contributed by Jim Kingdon, 20-Aug-2026.)
⊢ 𝐽 = {𝑧 ∈ ℕ ∣ ¬ 𝐵 ∥ 𝑧}    &   ⊢ 𝐹 = (𝑥 ∈ 𝐽, 𝑦 ∈ ℕ0 ↦ ((𝐵↑𝑦) · 𝑥))    ⇒   ⊢ ((𝑋 ∈ ℕ ∧ 𝐵 ∈ ℙ) → ∃𝑚 ∈ ℕ ∃𝑎 ∈ ℕ0 (¬ 𝐵 ∥ 𝑚 ∧ 𝑋 = ((𝐵↑𝑎) · 𝑚)))
Theorem	zprmlogbap 16235*	The logarithm of a natural number to a prime base is either rational or irrational. The proof decomposes 𝑋 into 𝑚 ∈ ℕ and 𝑎 ∈ ℕ0 such that 𝑋 = ((𝐵↑𝑎) · 𝑚) (using nnmaxpw 12977). If 𝑚 = 1 the logarithm is 𝑎, which is rational. If 1 < 𝑚 then we can apply logbgcd1irrap 16223 to show that the logarithm is irrational. (Contributed by Jim Kingdon and Taylor Barrella, 20-Aug-2026.)
⊢ ((𝑋 ∈ ℕ ∧ 𝐵 ∈ ℙ) → ((𝐵 logb 𝑋) ∈ ℚ ∨ ((𝐵 logb 𝑋) ∈ ℝ ∧ ∀𝑞 ∈ ℚ (𝐵 logb 𝑋) # 𝑞)))
11.2.5  Quartic binomial expansion
Theorem	binom4 16236	Work out a quartic binomial. (You would think that by this point it would be faster to use binom 12275, but it turns out to be just as much work to put it into this form after clearing all the sums and calculating binomial coefficients.) (Contributed by Mario Carneiro, 6-May-2015.)
⊢ ((𝐴 ∈ ℂ ∧ 𝐵 ∈ ℂ) → ((𝐴 + 𝐵)↑4) = (((𝐴↑4) + (4 · ((𝐴↑3) · 𝐵))) + ((6 · ((𝐴↑2) · (𝐵↑2))) + ((4 · (𝐴 · (𝐵↑3))) + (𝐵↑4)))))
11.2.6  Logarithms (cont.)
Theorem	log2tlbndlog2 16237*	Bound the error term in the series of the hypothesis. The presence of the hypothesis here is a temporary measure until it can be proved as log2cnv . (Contributed by Mario Carneiro, 7-Apr-2015.)
⊢ seq0( + , (𝑘 ∈ ℕ0 ↦ (2 / ((3 · ((2 · 𝑘) + 1)) · (9↑𝑘))))) ⇝ (log‘2)    ⇒   ⊢ (𝑁 ∈ ℕ0 → ((log‘2) − Σ𝑛 ∈ (0...(𝑁 − 1))(2 / ((3 · ((2 · 𝑛) + 1)) · (9↑𝑛)))) ∈ (0[,](3 / ((4 · ((2 · 𝑁) + 1)) · (9↑𝑁)))))
11.2.7  The Birthday Problem
Theorem	log2ublem1 16238	Lemma for log2ublog2 16241. The proof of log2ublog2 16241, which is simply the evaluation of log2tlbndlog2 16237 for 𝑁 = 4, takes the form of the addition of five fractions and showing this is less than another fraction. We could just perform exact arithmetic on these fractions, get a large rational number, and just multiply everything to verify the claim, but as anyone who uses decimal numbers for this task knows, it is often better to pick a common denominator 𝑑 (usually a large power of 10) and work with the closest approximations of the form 𝑛 / 𝑑 for some integer 𝑛 instead. It turns out that for our purposes it is sufficient to take 𝑑 = (3↑7) · 5 · 7, which is also nice because it shares many factors in common with the fractions in question. (Contributed by Mario Carneiro, 17-Apr-2015.)
⊢ (((3↑7) · (5 · 7)) · 𝐴) ≤ 𝐵    &   ⊢ 𝐴 ∈ ℝ    &   ⊢ 𝐷 ∈ ℕ0    &   ⊢ 𝐸 ∈ ℕ    &   ⊢ 𝐵 ∈ ℕ0    &   ⊢ 𝐹 ∈ ℕ0    &   ⊢ 𝐶 = (𝐴 + (𝐷 / 𝐸))    &   ⊢ (𝐵 + 𝐹) = 𝐺    &   ⊢ (((3↑7) · (5 · 7)) · 𝐷) ≤ (𝐸 · 𝐹)    ⇒   ⊢ (((3↑7) · (5 · 7)) · 𝐶) ≤ 𝐺
Theorem	log2ublem2 16239*	Lemma for log2ublog2 16241. (Contributed by Mario Carneiro, 17-Apr-2015.)
⊢ (((3↑7) · (5 · 7)) · Σ𝑛 ∈ (0...𝐾)(2 / ((3 · ((2 · 𝑛) + 1)) · (9↑𝑛)))) ≤ (2 · 𝐵)    &   ⊢ 𝐵 ∈ ℕ0    &   ⊢ 𝐹 ∈ ℕ0    &   ⊢ 𝑁 ∈ ℕ0    &   ⊢ (𝑁 − 1) = 𝐾    &   ⊢ (𝐵 + 𝐹) = 𝐺    &   ⊢ 𝑀 ∈ ℕ0    &   ⊢ (𝑀 + 𝑁) = 3    &   ⊢ ((5 · 7) · (9↑𝑀)) = (((2 · 𝑁) + 1) · 𝐹)    ⇒   ⊢ (((3↑7) · (5 · 7)) · Σ𝑛 ∈ (0...𝑁)(2 / ((3 · ((2 · 𝑛) + 1)) · (9↑𝑛)))) ≤ (2 · 𝐺)
Theorem	log2ublem3 16240	Lemma for log2ublog2 16241. In decimal, this is a proof that the first four terms of the series for log2 is less than 53056 / 76545. (Contributed by Mario Carneiro, 17-Apr-2015.) (Proof shortened by AV, 15-Sep-2021.)
⊢ (((3↑7) · (5 · 7)) · Σ𝑛 ∈ (0...3)(2 / ((3 · ((2 · 𝑛) + 1)) · (9↑𝑛)))) ≤ ;;;;53056
Theorem	log2ublog2 16241	log2 is less than 253 / 365. If written in decimal, this is because log2 = 0.693147... is less than 253/365 = 0.693151... , so this is a very tight bound, at five decimal places. The presence of the hypothesis here is a temporary measure until it can be proved as log2cnv . (Contributed by Mario Carneiro, 7-Apr-2015.) (Proof shortened by AV, 16-Sep-2021.)
⊢ seq0( + , (𝑘 ∈ ℕ0 ↦ (2 / ((3 · ((2 · 𝑘) + 1)) · (9↑𝑘))))) ⇝ (log‘2)    ⇒   ⊢ (log‘2) < (;;253 / ;;365)
Theorem	birthdaylem1g 16242*	Lemma for birthdaylog2 16245. (Contributed by Mario Carneiro, 17-Apr-2015.)
⊢ 𝑆 = {𝑓 ∣ 𝑓:(1...𝐾)⟶(1...𝑁)}    &   ⊢ 𝑇 = {𝑓 ∣ 𝑓:(1...𝐾)–1-1→(1...𝑁)}    ⇒   ⊢ ((𝐾 ∈ ℕ0 ∧ 𝑁 ∈ ℕ) → (𝑇 ⊆ 𝑆 ∧ 𝑆 ∈ Fin ∧ 𝑆 ≠ ∅))
Theorem	birthdaylem2 16243*	For general 𝑁 and 𝐾, count the fraction of injective functions from 1...𝐾 to 1...𝑁. (Contributed by Mario Carneiro, 7-May-2015.)
⊢ 𝑆 = {𝑓 ∣ 𝑓:(1...𝐾)⟶(1...𝑁)}    &   ⊢ 𝑇 = {𝑓 ∣ 𝑓:(1...𝐾)–1-1→(1...𝑁)}    ⇒   ⊢ ((𝑁 ∈ ℕ ∧ 𝐾 ∈ (0...𝑁)) → ((♯‘𝑇) / (♯‘𝑆)) = (exp‘Σ𝑘 ∈ (0...(𝐾 − 1))(log‘(1 − (𝑘 / 𝑁)))))
Theorem	birthdaylem3 16244*	For general 𝑁 and 𝐾, upper-bound the fraction of injective functions from 1...𝐾 to 1...𝑁. (Contributed by Mario Carneiro, 17-Apr-2015.)
⊢ 𝑆 = {𝑓 ∣ 𝑓:(1...𝐾)⟶(1...𝑁)}    &   ⊢ 𝑇 = {𝑓 ∣ 𝑓:(1...𝐾)–1-1→(1...𝑁)}    ⇒   ⊢ ((𝐾 ∈ ℕ0 ∧ 𝑁 ∈ ℕ) → ((♯‘𝑇) / (♯‘𝑆)) ≤ (exp‘ -((((𝐾↑2) − 𝐾) / 2) / 𝑁)))
Theorem	birthdaylog2 16245*	The Birthday Problem. There is a more than even chance that out of 23 people in a room, at least two of them have the same birthday. Mathematically, this is asserting that for 𝐾 = 23 and 𝑁 = 365, fewer than half of the set of all functions from 1...𝐾 to 1...𝑁 are injective. The presence of the hypothesis giving a series which converges to (log‘2) is a temporary measure until it can be proved as log2cnv . Although this is Metamath 100 proof #93, we cannot consider it proved until we prove the missing log2cnv piece (or prove the theorem another way which does not require it). (Contributed by Mario Carneiro, 17-Apr-2015.)
⊢ 𝑆 = {𝑓 ∣ 𝑓:(1...𝐾)⟶(1...𝑁)}    &   ⊢ 𝑇 = {𝑓 ∣ 𝑓:(1...𝐾)–1-1→(1...𝑁)}    &   ⊢ 𝐾 = ;23    &   ⊢ 𝑁 = ;;365    &   ⊢ seq0( + , (𝑘 ∈ ℕ0 ↦ (2 / ((3 · ((2 · 𝑘) + 1)) · (9↑𝑘))))) ⇝ (log‘2)    ⇒   ⊢ ((♯‘𝑇) / (♯‘𝑆)) < (1 / 2)
11.3  Pell equations
11.3.1  Pell equations 1: A nontrivial solution always exists
Theorem	pellexlem1 16246	Lemma for pellex . Arithmetical core of pellexlem3, norm lower bound. This begins Dirichlet's proof of the Pell equation solution existence; the proof here follows theorem 62 of [vandenDries] p. 43. (Contributed by Stefan O'Rear, 14-Sep-2014.)
⊢ (((𝐷 ∈ ℕ ∧ 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) ∧ ¬ (√‘𝐷) ∈ ℚ) → ((𝐴↑2) − (𝐷 · (𝐵↑2))) ≠ 0)
Theorem	pellexlem2 16247	Lemma for pellex . Arithmetical core of pellexlem3, norm upper bound. (Contributed by Stefan O'Rear, 14-Sep-2014.)
⊢ (((𝐷 ∈ ℕ ∧ 𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) ∧ (abs‘((𝐴 / 𝐵) − (√‘𝐷))) < (𝐵↑ -2)) → (abs‘((𝐴↑2) − (𝐷 · (𝐵↑2)))) < (1 + (2 · (√‘𝐷))))
Theorem	pellexlem3 16248*	Lemma for pellex . To each good rational approximation of (√‘𝐷), there exists a near-solution. (Contributed by Stefan O'Rear, 14-Sep-2014.)
⊢ ((𝐷 ∈ ℕ ∧ ¬ (√‘𝐷) ∈ ℚ) → {𝑥 ∈ ℚ ∣ (0 < 𝑥 ∧ (abs‘(𝑥 − (√‘𝐷))) < ((denom‘𝑥)↑ -2))} ≼ {⟨𝑦, 𝑧⟩ ∣ ((𝑦 ∈ ℕ ∧ 𝑧 ∈ ℕ) ∧ (((𝑦↑2) − (𝐷 · (𝑧↑2))) ≠ 0 ∧ (abs‘((𝑦↑2) − (𝐷 · (𝑧↑2)))) < (1 + (2 · (√‘𝐷)))))})
11.4  Basic number theory
11.4.1  Wilson's theorem
Theorem	wilthlem1 16249	The only elements that are equal to their own inverses in the multiplicative group of nonzero elements in ℤ / 𝑃ℤ are 1 and -1≡𝑃 − 1. (Note that from prmdiveq 13042, (𝑁↑(𝑃 − 2)) mod 𝑃 is the modular inverse of 𝑁 in ℤ / 𝑃ℤ. (Contributed by Mario Carneiro, 24-Jan-2015.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑁 ∈ (1...(𝑃 − 1))) → (𝑁 = ((𝑁↑(𝑃 − 2)) mod 𝑃) ↔ (𝑁 = 1 ∨ 𝑁 = (𝑃 − 1))))
11.4.2  Number-theoretical functions
Syntax	ccht 16250	Extend class notation with the first Chebyshev function.
class θ
Syntax	cppi 16251	Extend class notation with the prime-counting function pi.
class π
Syntax	csgm 16252	Extend class notation with the divisor function.
class σ
Definition	df-cht 16253*	Define the first Chebyshev function, which adds up the logarithms of all primes less than 𝑥, see definition in [ApostolNT] p. 75. The symbol used to represent this function is sometimes the variant greek letter theta shown here and sometimes the greek letter psi, ψ; however, this notation can also refer to the second Chebyshev function, which adds up the logarithms of prime powers instead. See https://en.wikipedia.org/wiki/Chebyshev_function for a discussion of the two functions. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ θ = (𝑥 ∈ ℝ ↦ Σ𝑝 ∈ ((0[,]𝑥) ∩ ℙ)(log‘𝑝))
Definition	df-ppi 16254	Define the prime π function, which counts the number of primes less than or equal to 𝑥, see definition in [ApostolNT] p. 8. Most often 𝑥 will be an integer, but many of our theorems support rational numbers (for example at ppiqsval 16257), and the definition would also work for cases such as numbers known to be irrational. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ π = (𝑥 ∈ ℝ ↦ (♯‘((0[,]𝑥) ∩ ℙ)))
Definition	df-sgm 16255*	Define the sum of positive divisors function (𝑥 σ 𝑛), which is the sum of the xth powers of the positive integer divisors of n, see definition in [ApostolNT] p. 38. For 𝑥 = 0, (𝑥 σ 𝑛) counts the number of divisors of 𝑛, i.e. (0 σ 𝑛) is the divisor function, see remark in [ApostolNT] p. 38. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ σ = (𝑥 ∈ ℂ, 𝑛 ∈ ℕ ↦ Σ𝑘 ∈ {𝑝 ∈ ℕ ∣ 𝑝 ∥ 𝑛} (𝑘↑𝑐𝑥))
Theorem	efnnfsumcl 16256*	Finite sum closure in the log-integers. (Contributed by Mario Carneiro, 7-Apr-2016.)
⊢ (𝜑 → 𝐴 ∈ Fin)    &   ⊢ ((𝜑 ∧ 𝑘 ∈ 𝐴) → 𝐵 ∈ ℝ)    &   ⊢ ((𝜑 ∧ 𝑘 ∈ 𝐴) → (exp‘𝐵) ∈ ℕ)    ⇒   ⊢ (𝜑 → (exp‘Σ𝑘 ∈ 𝐴 𝐵) ∈ ℕ)
Theorem	ppiqsval 16257	The set of primes less than 𝐴 expressed using a finite set of integers. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (𝐴 ∈ ℚ → ((0[,]𝐴) ∩ ℙ) = ((2...(⌊‘𝐴)) ∩ ℙ))
Theorem	ppiqsval2 16258	The set of primes less than 𝐴 expressed using a finite set of integers. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 2 ∈ (ℤ≥‘𝑀)) → ((0[,]𝐴) ∩ ℙ) = ((𝑀...(⌊‘𝐴)) ∩ ℙ))
Theorem	ppiqfi 16259	The set of primes less than 𝐴 is a finite set. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ (𝐴 ∈ ℚ → ((0[,]𝐴) ∩ ℙ) ∈ Fin)
Theorem	prmdvdsfi 16260*	The set of prime divisors of a number is a finite set. (Contributed by Mario Carneiro, 7-Apr-2016.)
⊢ (𝐴 ∈ ℕ → {𝑝 ∈ ℙ ∣ 𝑝 ∥ 𝐴} ∈ Fin)
Theorem	chtqcl 16261	Rational closure of the Chebyshev function. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (θ‘𝐴) ∈ ℝ)
Theorem	chtqval 16262*	Value of the Chebyshev function. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (θ‘𝐴) = Σ𝑝 ∈ ((0[,]𝐴) ∩ ℙ)(log‘𝑝))
Theorem	efchtqcl 16263	The Chebyshev function is closed in the log-integers. (Contributed by Mario Carneiro, 22-Sep-2014.) (Revised by Mario Carneiro, 7-Apr-2016.)
⊢ (𝐴 ∈ ℚ → (exp‘(θ‘𝐴)) ∈ ℕ)
Theorem	chtqge0 16264	The Chebyshev function is always positive. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ (𝐴 ∈ ℚ → 0 ≤ (θ‘𝐴))
Theorem	ppiqval 16265	Value of the prime-counting function pi. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (π‘𝐴) = (♯‘((0[,]𝐴) ∩ ℙ)))
Theorem	ppival2 16266	Value of the prime-counting function pi. (Contributed by Mario Carneiro, 18-Sep-2014.)
⊢ (𝐴 ∈ ℤ → (π‘𝐴) = (♯‘((2...𝐴) ∩ ℙ)))
Theorem	ppival2g 16267	Value of the prime-counting function pi. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ 2 ∈ (ℤ≥‘𝑀)) → (π‘𝐴) = (♯‘((𝑀...𝐴) ∩ ℙ)))
Theorem	ppiqcl 16268	Rational closure of the prime-counting function pi. (Contributed by Mario Carneiro, 15-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (π‘𝐴) ∈ ℕ0)
Theorem	sgmval 16269*	The value of the divisor function. (Contributed by Mario Carneiro, 22-Sep-2014.) (Revised by Mario Carneiro, 21-Jun-2015.)
⊢ ((𝐴 ∈ ℂ ∧ 𝐵 ∈ ℕ) → (𝐴 σ 𝐵) = Σ𝑘 ∈ {𝑝 ∈ ℕ ∣ 𝑝 ∥ 𝐵} (𝑘↑𝑐𝐴))
Theorem	sgmval2 16270*	The value of the divisor function. (Contributed by Mario Carneiro, 21-Jun-2015.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℕ) → (𝐴 σ 𝐵) = Σ𝑘 ∈ {𝑝 ∈ ℕ ∣ 𝑝 ∥ 𝐵} (𝑘↑𝐴))
Theorem	0sgm 16271*	The value of the sum-of-divisors function, usually denoted σ<SUB>0</SUB>(<i>n</i>). (Contributed by Mario Carneiro, 21-Jun-2015.)
⊢ (𝐴 ∈ ℕ → (0 σ 𝐴) = (♯‘{𝑝 ∈ ℕ ∣ 𝑝 ∥ 𝐴}))
Theorem	sgmf 16272	The divisor function is a function into the complex numbers. (Contributed by Mario Carneiro, 22-Sep-2014.) (Revised by Mario Carneiro, 21-Jun-2015.)
⊢ σ :(ℂ × ℕ)⟶ℂ
Theorem	sgmcl 16273	Closure of the divisor function. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℂ ∧ 𝐵 ∈ ℕ) → (𝐴 σ 𝐵) ∈ ℂ)
Theorem	sgmnncl 16274	Closure of the divisor function. (Contributed by Mario Carneiro, 21-Jun-2015.)
⊢ ((𝐴 ∈ ℕ0 ∧ 𝐵 ∈ ℕ) → (𝐴 σ 𝐵) ∈ ℕ)
Theorem	chtqfl 16275	The Chebyshev function does not change off the integers. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (θ‘(⌊‘𝐴)) = (θ‘𝐴))
Theorem	ppiprm 16276	The prime-counting function π at a prime. (Contributed by Mario Carneiro, 19-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ (𝐴 + 1) ∈ ℙ) → (π‘(𝐴 + 1)) = ((π‘𝐴) + 1))
Theorem	ppinprm 16277	The prime-counting function π at a non-prime. (Contributed by Mario Carneiro, 19-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ ¬ (𝐴 + 1) ∈ ℙ) → (π‘(𝐴 + 1)) = (π‘𝐴))
Theorem	chtprm 16278	The Chebyshev function at a prime. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ (𝐴 + 1) ∈ ℙ) → (θ‘(𝐴 + 1)) = ((θ‘𝐴) + (log‘(𝐴 + 1))))
Theorem	chtnprm 16279	The Chebyshev function at a non-prime. (Contributed by Mario Carneiro, 19-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ ¬ (𝐴 + 1) ∈ ℙ) → (θ‘(𝐴 + 1)) = (θ‘𝐴))
Theorem	chtqwordi 16280	The Chebyshev function is weakly increasing. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 𝐴 ≤ 𝐵) → (θ‘𝐴) ≤ (θ‘𝐵))
Theorem	chtdif 16281*	The difference of the Chebyshev function at two points sums the logarithms of the primes in an interval. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (𝑁 ∈ (ℤ≥‘𝑀) → ((θ‘𝑁) − (θ‘𝑀)) = Σ𝑝 ∈ (((𝑀 + 1)...𝑁) ∩ ℙ)(log‘𝑝))
Theorem	efchtqdvds 16282	The exponentiated Chebyshev function forms a divisibility chain between any two points. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 𝐴 ≤ 𝐵) → (exp‘(θ‘𝐴)) ∥ (exp‘(θ‘𝐵)))
Theorem	ppiqfl 16283	The prime-counting function π does not change off the integers. (Contributed by Mario Carneiro, 18-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (π‘(⌊‘𝐴)) = (π‘𝐴))
Theorem	ppiqp1le 16284	The prime-counting function π cannot locally increase faster than the identity function. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ (𝐴 ∈ ℚ → (π‘(𝐴 + 1)) ≤ ((π‘𝐴) + 1))
Theorem	ppiqwordi 16285	The prime-counting function π is weakly increasing. (Contributed by Mario Carneiro, 19-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 𝐵 ∈ ℚ ∧ 𝐴 ≤ 𝐵) → (π‘𝐴) ≤ (π‘𝐵))
Theorem	ppidif 16286	The difference of the prime-counting function π at two points counts the number of primes in an interval. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ (𝑁 ∈ (ℤ≥‘𝑀) → ((π‘𝑁) − (π‘𝑀)) = (♯‘(((𝑀 + 1)...𝑁) ∩ ℙ)))
Theorem	ppi1 16287	The prime-counting function π at 1. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ (π‘1) = 0
Theorem	cht1 16288	The Chebyshev function at 1. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (θ‘1) = 0
Theorem	ppi1i 16289	Inference form of ppiprm 16276. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ 𝑀 ∈ ℕ0    &   ⊢ 𝑁 = (𝑀 + 1)    &   ⊢ (π‘𝑀) = 𝐾    &   ⊢ 𝑁 ∈ ℙ    ⇒   ⊢ (π‘𝑁) = (𝐾 + 1)
Theorem	ppi2i 16290	Inference form of ppinprm 16277. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ 𝑀 ∈ ℕ0    &   ⊢ 𝑁 = (𝑀 + 1)    &   ⊢ (π‘𝑀) = 𝐾    &   ⊢ ¬ 𝑁 ∈ ℙ    ⇒   ⊢ (π‘𝑁) = 𝐾
Theorem	ppi2 16291	The prime-counting function π at 2. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ (π‘2) = 1
Theorem	ppi3 16292	The prime-counting function π at 3. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ (π‘3) = 2
Theorem	cht2 16293	The Chebyshev function at 2. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (θ‘2) = (log‘2)
Theorem	cht3 16294	The Chebyshev function at 3. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (θ‘3) = (log‘6)
Theorem	ppiqnncl 16295	Closure of the prime-counting function π in the positive integers. (Contributed by Mario Carneiro, 21-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 2 ≤ 𝐴) → (π‘𝐴) ∈ ℕ)
Theorem	chtqrpcl 16296	Closure of the Chebyshev function in the positive reals. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 2 ≤ 𝐴) → (θ‘𝐴) ∈ ℝ+)
Theorem	ppiqeq0 16297	The prime-counting function π is zero iff its argument is less than 2. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ (𝐴 ∈ ℚ → ((π‘𝐴) = 0 ↔ 𝐴 < 2))
Theorem	ppiqltx 16298	The prime-counting function π is strictly less than the identity. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ ((𝐴 ∈ ℚ ∧ 0 < 𝐴) → (π‘𝐴) < 𝐴)
Theorem	prmorcht 16299	Relate the primorial (product of the primes up to 𝐴) to the Chebyshev function. (Contributed by Mario Carneiro, 22-Sep-2014.)
⊢ 𝐹 = (𝑛 ∈ ℕ ↦ if(𝑛 ∈ ℙ, 𝑛, 1))    ⇒   ⊢ (𝐴 ∈ ℕ → (exp‘(θ‘𝐴)) = (seq1( · , 𝐹)‘𝐴))
Theorem	dvdsppwf1o 16300*	A bijection between the divisors of a prime power and the integers less than or equal to the exponent. (Contributed by Mario Carneiro, 5-May-2016.)
⊢ 𝐹 = (𝑛 ∈ (0...𝐴) ↦ (𝑃↑𝑛))    ⇒   ⊢ ((𝑃 ∈ ℙ ∧ 𝐴 ∈ ℕ0) → 𝐹:(0...𝐴)–1-1-onto→{𝑥 ∈ ℕ ∣ 𝑥 ∥ (𝑃↑𝐴)})