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	relogbcxpbap 16201	The logarithm is the inverse of the exponentiation. Observation in [Cohen4] p. 348. (Contributed by AV, 11-Jun-2020.)
|- ( ( ( B e. RR+ /\ B # 1 ) /\ X e. RR+ /\ Y e. RR ) -> ( ( B logb X ) = Y <-> ( B ^c Y ) = X ) )
Theorem	logbgt0b 16202	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.)
|- ( ( A e. RR+ /\ ( B e. RR+ /\ 1 < B ) ) -> ( 0 < ( B logb A ) <-> 1 < A ) )
Theorem	logbgcd1irr 16203	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 ) e. ( RR \ QQ ). (Contributed by AV, 29-Dec-2022.)
|- ( ( X e. ( ZZ>= ` 2 ) /\ B e. ( ZZ>= ` 2 ) /\ ( X gcd B ) = 1 ) -> ( B logb X ) e. ( RR \ QQ ) )
Theorem	logbgcd1irraplemexp 16204	Lemma for logbgcd1irrap 16206. Apartness of X ^ N and B ^ M. (Contributed by Jim Kingdon, 11-Jul-2024.)
|- ( ph -> X e. ( ZZ>= ` 2 ) )   &    |- ( ph -> B e. ( ZZ>= ` 2 ) )   &    |- ( ph -> ( X gcd B ) = 1 )   &    |- ( ph -> M e. ZZ )   &    |- ( ph -> N e. NN )   =>    |- ( ph -> ( X ^ N ) # ( B ^ M ) )
Theorem	logbgcd1irraplemap 16205	Lemma for logbgcd1irrap 16206. The result, with the rational number expressed as numerator and denominator. (Contributed by Jim Kingdon, 9-Jul-2024.)
|- ( ph -> X e. ( ZZ>= ` 2 ) )   &    |- ( ph -> B e. ( ZZ>= ` 2 ) )   &    |- ( ph -> ( X gcd B ) = 1 )   &    |- ( ph -> M e. ZZ )   &    |- ( ph -> N e. NN )   =>    |- ( ph -> ( B logb X ) # ( M / N ) )
Theorem	logbgcd1irrap 16206	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 ) # Q where Q is rational. (Contributed by AV, 29-Dec-2022.)
|- ( ( ( X e. ( ZZ>= ` 2 ) /\ B e. ( ZZ>= ` 2 ) ) /\ ( ( X gcd B ) = 1 /\ Q e. QQ ) ) -> ( B logb X ) # Q )
Theorem	2logb9irr 16207	Example for logbgcd1irr 16203. The logarithm of nine to base two is not rational. Also see 2logb9irrap 16213 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 ) e. ( RR \ QQ )
Theorem	logbprmirr 16208	The logarithm of a prime to a different prime base is not rational. For example, ( 2 logb 3 ) e. ( RR \ QQ ) (see 2logb3irr 16209). (Contributed by AV, 31-Dec-2022.)
|- ( ( X e. Prime /\ B e. Prime /\ X =/= B ) -> ( B logb X ) e. ( RR \ QQ ) )
Theorem	2logb3irr 16209	Example for logbprmirr 16208. The logarithm of three to base two is not rational. (Contributed by AV, 31-Dec-2022.)
|- ( 2 logb 3 ) e. ( RR \ QQ )
Theorem	2logb9irrALT 16210	Alternate proof of 2logb9irr 16207: 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 ) e. ( RR \ QQ )
Theorem	sqrt2cxp2logb9e3 16211	The square root of two to the power of the logarithm of nine to base two is three. ( sqr ` 2 ) and ( 2 logb 9 ) are not rational (see sqrt2irr0 12968 resp. 2logb9irr 16207), satisfying the statement in 2irrexpq 16212. (Contributed by AV, 29-Dec-2022.)
|- ( ( sqr ` 2 ) ^c ( 2 logb 9 ) ) = 3
Theorem	2irrexpq 16212*	There exist real numbers a and b which are not rational such that ( a ^ b ) 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 ( sqr ` 2 ) and ( 2 logb 9 ), see sqrt2irr0 12968, 2logb9irr 16207 and sqrt2cxp2logb9e3 16211. Therefore, this proof is acceptable/usable in intuitionistic logic. For a theorem which is the same but proves that a and b are irrational (in the sense of being apart from any rational number), see 2irrexpqap 16214. (Contributed by AV, 23-Dec-2022.)
|- E. a e. ( RR \ QQ ) E. b e. ( RR \ QQ ) ( a ^c b ) e. QQ
Theorem	2logb9irrap 16213	Example for logbgcd1irrap 16206. 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.)
|- ( Q e. QQ -> ( 2 logb 9 ) # Q )
Theorem	2irrexpqap 16214*	There exist real numbers a and b which are irrational (in the sense of being apart from any rational number) such that ( a ^ b ) 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 ( sqr ` 2 ) and ( 2 logb 9 ), see sqrt2irrap 12985, 2logb9irrap 16213 and sqrt2cxp2logb9e3 16211. Therefore, this proof is acceptable/usable in intuitionistic logic. (Contributed by Jim Kingdon, 12-Jul-2024.)
|- E. a e. RR E. b e. RR ( A. p e. QQ a # p /\ A. q e. QQ b # q /\ ( a ^c b ) e. QQ )
Theorem	zprmlogbaplem1 16215	Lemma for zprmlogbap 16218. Rearranging an expression involving logarithms. (Contributed by Jim Kingdon, 20-Aug-2026.)
|- ( ph -> B e. Prime )   &    |- ( ph -> M e. NN )   &    |- ( ph -> -. B || M )   &    |- ( ph -> A e. NN0 )   =>    |- ( ph -> ( B logb ( ( B ^ A ) x. M ) ) = ( A + ( B logb M ) ) )
Theorem	zprmlogbaplem2 16216*	Lemma for zprmlogbap 16218. The logarithm is either rational or irrational. (Contributed by Jim Kingdon, 20-Aug-2026.)
|- ( ph -> B e. Prime )   &    |- ( ph -> M e. NN )   &    |- ( ph -> -. B || M )   &    |- ( ph -> A e. NN0 )   &    |- X = ( ( B ^ A ) x. M )   =>    |- ( ph -> ( ( B logb X ) e. QQ \/ ( ( B logb X ) e. RR /\ A. q e. QQ ( B logb X ) # q ) ) )
Theorem	zprmlogbaplem3 16217*	Lemma for zprmlogbap 16218. 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.)
|- J = { z e. NN | -. B || z }   &    |- F = ( x e. J , y e. NN0 |-> ( ( B ^ y ) x. x ) )   =>    |- ( ( X e. NN /\ B e. Prime ) -> E. m e. NN E. a e. NN0 ( -. B || m /\ X = ( ( B ^ a ) x. m ) ) )
Theorem	zprmlogbap 16218*	The logarithm of a natural number to a prime base is either rational or irrational. The proof decomposes X into m e. NN and a e. NN0 such that X = ( ( B ^ a ) x. m ) (using nnmaxpw 12978). If m = 1 the logarithm is a, which is rational. If 1 < m then we can apply logbgcd1irrap 16206 to show that the logarithm is irrational. (Contributed by Jim Kingdon and Taylor Barrella, 20-Aug-2026.)
|- ( ( X e. NN /\ B e. Prime ) -> ( ( B logb X ) e. QQ \/ ( ( B logb X ) e. RR /\ A. q e. QQ ( B logb X ) # q ) ) )
11.2.5  Quartic binomial expansion
Theorem	binom4 16219	Work out a quartic binomial. (You would think that by this point it would be faster to use binom 12276, 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.)
|- ( ( A e. CC /\ B e. CC ) -> ( ( A + B ) ^ 4 ) = ( ( ( A ^ 4 ) + ( 4 x. ( ( A ^ 3 ) x. B ) ) ) + ( ( 6 x. ( ( A ^ 2 ) x. ( B ^ 2 ) ) ) + ( ( 4 x. ( A x. ( B ^ 3 ) ) ) + ( B ^ 4 ) ) ) ) )
11.2.6  Logarithms (cont.)
Theorem	log2tlbndlog2 16220*	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.)
|- seq 0 ( + , ( k e. NN0 |-> ( 2 / ( ( 3 x. ( ( 2 x. k ) + 1 ) ) x. ( 9 ^ k ) ) ) ) ) ~~> ( log ` 2 )   =>    |- ( N e. NN0 -> ( ( log ` 2 ) - sum_ n e. ( 0 ... ( N - 1 ) ) ( 2 / ( ( 3 x. ( ( 2 x. n ) + 1 ) ) x. ( 9 ^ n ) ) ) ) e. ( 0 [,] ( 3 / ( ( 4 x. ( ( 2 x. N ) + 1 ) ) x. ( 9 ^ N ) ) ) ) )
11.2.7  The Birthday Problem
Theorem	log2ublem1 16221	Lemma for log2ublog2 16224. The proof of log2ublog2 16224, which is simply the evaluation of log2tlbndlog2 16220 for N = 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 d (usually a large power of 1 0) and work with the closest approximations of the form n / d for some integer n instead. It turns out that for our purposes it is sufficient to take d = ( 3 ^ 7 ) x. 5 x. 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 ) x. ( 5 x. 7 ) ) x. A ) <_ B   &    |- A e. RR   &    |- D e. NN0   &    |- E e. NN   &    |- B e. NN0   &    |- F e. NN0   &    |- C = ( A + ( D / E ) )   &    |- ( B + F ) = G   &    |- ( ( ( 3 ^ 7 ) x. ( 5 x. 7 ) ) x. D ) <_ ( E x. F )   =>    |- ( ( ( 3 ^ 7 ) x. ( 5 x. 7 ) ) x. C ) <_ G
Theorem	log2ublem2 16222*	Lemma for log2ublog2 16224. (Contributed by Mario Carneiro, 17-Apr-2015.)
|- ( ( ( 3 ^ 7 ) x. ( 5 x. 7 ) ) x. sum_ n e. ( 0 ... K ) ( 2 / ( ( 3 x. ( ( 2 x. n ) + 1 ) ) x. ( 9 ^ n ) ) ) ) <_ ( 2 x. B )   &    |- B e. NN0   &    |- F e. NN0   &    |- N e. NN0   &    |- ( N - 1 ) = K   &    |- ( B + F ) = G   &    |- M e. NN0   &    |- ( M + N ) = 3   &    |- ( ( 5 x. 7 ) x. ( 9 ^ M ) ) = ( ( ( 2 x. N ) + 1 ) x. F )   =>    |- ( ( ( 3 ^ 7 ) x. ( 5 x. 7 ) ) x. sum_ n e. ( 0 ... N ) ( 2 / ( ( 3 x. ( ( 2 x. n ) + 1 ) ) x. ( 9 ^ n ) ) ) ) <_ ( 2 x. G )
Theorem	log2ublem3 16223	Lemma for log2ublog2 16224. In decimal, this is a proof that the first four terms of the series for log 2 is less than 5 3 0 5 6 / 7 6 5 4 5. (Contributed by Mario Carneiro, 17-Apr-2015.) (Proof shortened by AV, 15-Sep-2021.)
|- ( ( ( 3 ^ 7 ) x. ( 5 x. 7 ) ) x. sum_ n e. ( 0 ... 3 ) ( 2 / ( ( 3 x. ( ( 2 x. n ) + 1 ) ) x. ( 9 ^ n ) ) ) ) <_ ;;;; 5 3 0 5 6
Theorem	log2ublog2 16224	log 2 is less than 2 5 3 / 3 6 5. If written in decimal, this is because log 2 = 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.)
|- seq 0 ( + , ( k e. NN0 |-> ( 2 / ( ( 3 x. ( ( 2 x. k ) + 1 ) ) x. ( 9 ^ k ) ) ) ) ) ~~> ( log ` 2 )   =>    |- ( log ` 2 ) < (;; 2 5 3 / ;; 3 6 5 )
Theorem	birthdaylem1g 16225*	Lemma for birthdaylog2 16228. (Contributed by Mario Carneiro, 17-Apr-2015.)
|- S = { f | f : ( 1 ... K ) --> ( 1 ... N ) }   &    |- T = { f | f : ( 1 ... K ) -1-1-> ( 1 ... N ) }   =>    |- ( ( K e. NN0 /\ N e. NN ) -> ( T C_ S /\ S e. Fin /\ S =/= (/) ) )
Theorem	birthdaylem2 16226*	For general N and K, count the fraction of injective functions from 1 ... K to 1 ... N. (Contributed by Mario Carneiro, 7-May-2015.)
|- S = { f | f : ( 1 ... K ) --> ( 1 ... N ) }   &    |- T = { f | f : ( 1 ... K ) -1-1-> ( 1 ... N ) }   =>    |- ( ( N e. NN /\ K e. ( 0 ... N ) ) -> ( (♯ ` T ) / (♯ ` S ) ) = ( exp ` sum_ k e. ( 0 ... ( K - 1 ) ) ( log ` ( 1 - ( k / N ) ) ) ) )
Theorem	birthdaylem3 16227*	For general N and K, upper-bound the fraction of injective functions from 1 ... K to 1 ... N. (Contributed by Mario Carneiro, 17-Apr-2015.)
|- S = { f | f : ( 1 ... K ) --> ( 1 ... N ) }   &    |- T = { f | f : ( 1 ... K ) -1-1-> ( 1 ... N ) }   =>    |- ( ( K e. NN0 /\ N e. NN ) -> ( (♯ ` T ) / (♯ ` S ) ) <_ ( exp ` -u ( ( ( ( K ^ 2 ) - K ) / 2 ) / N ) ) )
Theorem	birthdaylog2 16228*	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 K = 2 3 and N = 3 6 5, fewer than half of the set of all functions from 1 ... K to 1 ... N 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.)
|- S = { f | f : ( 1 ... K ) --> ( 1 ... N ) }   &    |- T = { f | f : ( 1 ... K ) -1-1-> ( 1 ... N ) }   &    |- K = ; 2 3   &    |- N = ;; 3 6 5   &    |- seq 0 ( + , ( k e. NN0 |-> ( 2 / ( ( 3 x. ( ( 2 x. k ) + 1 ) ) x. ( 9 ^ k ) ) ) ) ) ~~> ( log ` 2 )   =>    |- ( (♯ ` T ) / (♯ ` S ) ) < ( 1 / 2 )
11.3  Pell equations
11.3.1  Pell equations 1: A nontrivial solution always exists
Theorem	pellexlem1 16229	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.)
|- ( ( ( D e. NN /\ A e. NN /\ B e. NN ) /\ -. ( sqr ` D ) e. QQ ) -> ( ( A ^ 2 ) - ( D x. ( B ^ 2 ) ) ) =/= 0 )
Theorem	pellexlem2 16230	Lemma for pellex . Arithmetical core of pellexlem3, norm upper bound. (Contributed by Stefan O'Rear, 14-Sep-2014.)
|- ( ( ( D e. NN /\ A e. NN /\ B e. NN ) /\ ( abs ` ( ( A / B ) - ( sqr ` D ) ) ) < ( B ^ -u 2 ) ) -> ( abs ` ( ( A ^ 2 ) - ( D x. ( B ^ 2 ) ) ) ) < ( 1 + ( 2 x. ( sqr ` D ) ) ) )
Theorem	pellexlem3 16231*	Lemma for pellex . To each good rational approximation of ( sqr ` D ), there exists a near-solution. (Contributed by Stefan O'Rear, 14-Sep-2014.)
|- ( ( D e. NN /\ -. ( sqr ` D ) e. QQ ) -> { x e. QQ | ( 0 < x /\ ( abs ` ( x - ( sqr ` D ) ) ) < ( (denom ` x ) ^ -u 2 ) ) } ~<_ { <. y , z >. | ( ( y e. NN /\ z e. NN ) /\ ( ( ( y ^ 2 ) - ( D x. ( z ^ 2 ) ) ) =/= 0 /\ ( abs ` ( ( y ^ 2 ) - ( D x. ( z ^ 2 ) ) ) ) < ( 1 + ( 2 x. ( sqr ` D ) ) ) ) ) } )
11.4  Basic number theory
11.4.1  Wilson's theorem
Theorem	wilthlem1 16232	The only elements that are equal to their own inverses in the multiplicative group of nonzero elements in ZZ / P ZZ are 1 and -u 1 == P - 1. (Note that from prmdiveq 13043, ( N ^ ( P - 2 ) ) mod P is the modular inverse of N in ZZ / P ZZ. (Contributed by Mario Carneiro, 24-Jan-2015.)
|- ( ( P e. Prime /\ N e. ( 1 ... ( P - 1 ) ) ) -> ( N = ( ( N ^ ( P - 2 ) ) mod P ) <-> ( N = 1 \/ N = ( P - 1 ) ) ) )
11.4.2  Number-theoretical functions
Syntax	ccht 16233	Extend class notation with the first Chebyshev function.
class theta
Syntax	cppi 16234	Extend class notation with the prime-counting function pi.
class π
Syntax	csgm 16235	Extend class notation with the divisor function.
class sigma
Definition	df-cht 16236*	Define the first Chebyshev function, which adds up the logarithms of all primes less than x, 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.)
|- theta = ( x e. RR |-> sum_ p e. ( ( 0 [,] x ) i^i Prime ) ( log ` p ) )
Definition	df-ppi 16237	Define the prime π function, which counts the number of primes less than or equal to x, see definition in [ApostolNT] p. 8. Most often x will be an integer, but many of our theorems support rational numbers (for example at ppiqsval 16240), and the definition would also work for cases such as numbers known to be irrational. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- π = ( x e. RR |-> (♯ ` ( ( 0 [,] x ) i^i Prime ) ) )
Definition	df-sgm 16238*	Define the sum of positive divisors function ( x sigma n ), which is the sum of the xth powers of the positive integer divisors of n, see definition in [ApostolNT] p. 38. For x = 0, ( x sigma n ) counts the number of divisors of n, i.e. ( 0 sigma n ) is the divisor function, see remark in [ApostolNT] p. 38. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- sigma = ( x e. CC , n e. NN |-> sum_ k e. { p e. NN | p || n } ( k ^c x ) )
Theorem	efnnfsumcl 16239*	Finite sum closure in the log-integers. (Contributed by Mario Carneiro, 7-Apr-2016.)
|- ( ph -> A e. Fin )   &    |- ( ( ph /\ k e. A ) -> B e. RR )   &    |- ( ( ph /\ k e. A ) -> ( exp ` B ) e. NN )   =>    |- ( ph -> ( exp ` sum_ k e. A B ) e. NN )
Theorem	ppiqsval 16240	The set of primes less than A expressed using a finite set of integers. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( A e. QQ -> ( ( 0 [,] A ) i^i Prime ) = ( ( 2 ... ( |_ ` A ) ) i^i Prime ) )
Theorem	ppiqsval2 16241	The set of primes less than A expressed using a finite set of integers. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. QQ /\ 2 e. ( ZZ>= ` M ) ) -> ( ( 0 [,] A ) i^i Prime ) = ( ( M ... ( |_ ` A ) ) i^i Prime ) )
Theorem	ppiqfi 16242	The set of primes less than A is a finite set. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- ( A e. QQ -> ( ( 0 [,] A ) i^i Prime ) e. Fin )
Theorem	prmdvdsfi 16243*	The set of prime divisors of a number is a finite set. (Contributed by Mario Carneiro, 7-Apr-2016.)
|- ( A e. NN -> { p e. Prime | p || A } e. Fin )
Theorem	chtqcl 16244	Rational closure of the Chebyshev function. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- ( A e. QQ -> ( theta ` A ) e. RR )
Theorem	chtqval 16245*	Value of the Chebyshev function. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- ( A e. QQ -> ( theta ` A ) = sum_ p e. ( ( 0 [,] A ) i^i Prime ) ( log ` p ) )
Theorem	efchtqcl 16246	The Chebyshev function is closed in the log-integers. (Contributed by Mario Carneiro, 22-Sep-2014.) (Revised by Mario Carneiro, 7-Apr-2016.)
|- ( A e. QQ -> ( exp ` ( theta ` A ) ) e. NN )
Theorem	chtqge0 16247	The Chebyshev function is always positive. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- ( A e. QQ -> 0 <_ ( theta ` A ) )
Theorem	ppiqval 16248	Value of the prime-counting function pi. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- ( A e. QQ -> (π ` A ) = (♯ ` ( ( 0 [,] A ) i^i Prime ) ) )
Theorem	ppival2 16249	Value of the prime-counting function pi. (Contributed by Mario Carneiro, 18-Sep-2014.)
|- ( A e. ZZ -> (π ` A ) = (♯ ` ( ( 2 ... A ) i^i Prime ) ) )
Theorem	ppival2g 16250	Value of the prime-counting function pi. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. ZZ /\ 2 e. ( ZZ>= ` M ) ) -> (π ` A ) = (♯ ` ( ( M ... A ) i^i Prime ) ) )
Theorem	ppiqcl 16251	Rational closure of the prime-counting function pi. (Contributed by Mario Carneiro, 15-Sep-2014.)
|- ( A e. QQ -> (π ` A ) e. NN0 )
Theorem	sgmval 16252*	The value of the divisor function. (Contributed by Mario Carneiro, 22-Sep-2014.) (Revised by Mario Carneiro, 21-Jun-2015.)
|- ( ( A e. CC /\ B e. NN ) -> ( A sigma B ) = sum_ k e. { p e. NN | p || B } ( k ^c A ) )
Theorem	sgmval2 16253*	The value of the divisor function. (Contributed by Mario Carneiro, 21-Jun-2015.)
|- ( ( A e. ZZ /\ B e. NN ) -> ( A sigma B ) = sum_ k e. { p e. NN | p || B } ( k ^ A ) )
Theorem	0sgm 16254*	The value of the sum-of-divisors function, usually denoted σ<SUB>0</SUB>(<i>n</i>). (Contributed by Mario Carneiro, 21-Jun-2015.)
|- ( A e. NN -> ( 0 sigma A ) = (♯ ` { p e. NN | p || A } ) )
Theorem	sgmf 16255	The divisor function is a function into the complex numbers. (Contributed by Mario Carneiro, 22-Sep-2014.) (Revised by Mario Carneiro, 21-Jun-2015.)
|- sigma : ( CC X. NN ) --> CC
Theorem	sgmcl 16256	Closure of the divisor function. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. CC /\ B e. NN ) -> ( A sigma B ) e. CC )
Theorem	sgmnncl 16257	Closure of the divisor function. (Contributed by Mario Carneiro, 21-Jun-2015.)
|- ( ( A e. NN0 /\ B e. NN ) -> ( A sigma B ) e. NN )
Theorem	chtqfl 16258	The Chebyshev function does not change off the integers. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( A e. QQ -> ( theta ` ( |_ ` A ) ) = ( theta ` A ) )
Theorem	ppiprm 16259	The prime-counting function π at a prime. (Contributed by Mario Carneiro, 19-Sep-2014.)
|- ( ( A e. ZZ /\ ( A + 1 ) e. Prime ) -> (π ` ( A + 1 ) ) = ( (π ` A ) + 1 ) )
Theorem	ppinprm 16260	The prime-counting function π at a non-prime. (Contributed by Mario Carneiro, 19-Sep-2014.)
|- ( ( A e. ZZ /\ -. ( A + 1 ) e. Prime ) -> (π ` ( A + 1 ) ) = (π ` A ) )
Theorem	chtprm 16261	The Chebyshev function at a prime. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. ZZ /\ ( A + 1 ) e. Prime ) -> ( theta ` ( A + 1 ) ) = ( ( theta ` A ) + ( log ` ( A + 1 ) ) ) )
Theorem	chtnprm 16262	The Chebyshev function at a non-prime. (Contributed by Mario Carneiro, 19-Sep-2014.)
|- ( ( A e. ZZ /\ -. ( A + 1 ) e. Prime ) -> ( theta ` ( A + 1 ) ) = ( theta ` A ) )
Theorem	chtqwordi 16263	The Chebyshev function is weakly increasing. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. QQ /\ B e. QQ /\ A <_ B ) -> ( theta ` A ) <_ ( theta ` B ) )
Theorem	chtdif 16264*	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.)
|- ( N e. ( ZZ>= ` M ) -> ( ( theta ` N ) - ( theta ` M ) ) = sum_ p e. ( ( ( M + 1 ) ... N ) i^i Prime ) ( log ` p ) )
Theorem	efchtqdvds 16265	The exponentiated Chebyshev function forms a divisibility chain between any two points. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. QQ /\ B e. QQ /\ A <_ B ) -> ( exp ` ( theta ` A ) ) || ( exp ` ( theta ` B ) ) )
Theorem	ppiqfl 16266	The prime-counting function π does not change off the integers. (Contributed by Mario Carneiro, 18-Sep-2014.)
|- ( A e. QQ -> (π ` ( |_ ` A ) ) = (π ` A ) )
Theorem	ppiqp1le 16267	The prime-counting function π cannot locally increase faster than the identity function. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- ( A e. QQ -> (π ` ( A + 1 ) ) <_ ( (π ` A ) + 1 ) )
Theorem	ppiqwordi 16268	The prime-counting function π is weakly increasing. (Contributed by Mario Carneiro, 19-Sep-2014.)
|- ( ( A e. QQ /\ B e. QQ /\ A <_ B ) -> (π ` A ) <_ (π ` B ) )
Theorem	ppidif 16269	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.)
|- ( N e. ( ZZ>= ` M ) -> ( (π ` N ) - (π ` M ) ) = (♯ ` ( ( ( M + 1 ) ... N ) i^i Prime ) ) )
Theorem	ppi1 16270	The prime-counting function π at 1. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- (π ` 1 ) = 0
Theorem	cht1 16271	The Chebyshev function at 1. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( theta ` 1 ) = 0
Theorem	ppi1i 16272	Inference form of ppiprm 16259. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- M e. NN0   &    |- N = ( M + 1 )   &    |- (π ` M ) = K   &    |- N e. Prime   =>    |- (π ` N ) = ( K + 1 )
Theorem	ppi2i 16273	Inference form of ppinprm 16260. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- M e. NN0   &    |- N = ( M + 1 )   &    |- (π ` M ) = K   &    |- -. N e. Prime   =>    |- (π ` N ) = K
Theorem	ppi2 16274	The prime-counting function π at 2. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- (π ` 2 ) = 1
Theorem	ppi3 16275	The prime-counting function π at 3. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- (π ` 3 ) = 2
Theorem	cht2 16276	The Chebyshev function at 2. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( theta ` 2 ) = ( log ` 2 )
Theorem	cht3 16277	The Chebyshev function at 3. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( theta ` 3 ) = ( log ` 6 )
Theorem	ppiqnncl 16278	Closure of the prime-counting function π in the positive integers. (Contributed by Mario Carneiro, 21-Sep-2014.)
|- ( ( A e. QQ /\ 2 <_ A ) -> (π ` A ) e. NN )
Theorem	chtqrpcl 16279	Closure of the Chebyshev function in the positive reals. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. QQ /\ 2 <_ A ) -> ( theta ` A ) e. RR+ )
Theorem	ppiqeq0 16280	The prime-counting function π is zero iff its argument is less than 2. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( A e. QQ -> ( (π ` A ) = 0 <-> A < 2 ) )
Theorem	ppiqltx 16281	The prime-counting function π is strictly less than the identity. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. QQ /\ 0 < A ) -> (π ` A ) < A )
Theorem	prmorcht 16282	Relate the primorial (product of the primes up to A) to the Chebyshev function. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- F = ( n e. NN |-> if ( n e. Prime , n , 1 ) )   =>    |- ( A e. NN -> ( exp ` ( theta ` A ) ) = ( seq 1 ( x. , F ) ` A ) )
Theorem	dvdsppwf1o 16283*	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.)
|- F = ( n e. ( 0 ... A ) |-> ( P ^ n ) )   =>    |- ( ( P e. Prime /\ A e. NN0 ) -> F : ( 0 ... A ) -1-1-onto-> { x e. NN | x || ( P ^ A ) } )
Theorem	mpodvdsmulf1o 16284*	If M and N are two coprime integers, multiplication forms a bijection from the set of pairs <. j , k >. where j || M and k || N, to the set of divisors of M x. N. (Contributed by GG, 18-Apr-2025.)
|- ( ph -> M e. NN )   &    |- ( ph -> N e. NN )   &    |- ( ph -> ( M gcd N ) = 1 )   &    |- X = { x e. NN | x || M }   &    |- Y = { x e. NN | x || N }   &    |- Z = { x e. NN | x || ( M x. N ) }   =>    |- ( ph -> ( ( x e. CC , y e. CC |-> ( x x. y ) ) |` ( X X. Y ) ) : ( X X. Y ) -1-1-onto-> Z )
Theorem	fsumdvdsmul 16285*	Product of two divisor sums. (This is also the main part of the proof that " sum_ k || N F ( k ) is a multiplicative function if F is".) (Contributed by Mario Carneiro, 2-Jul-2015.) Avoid ax-mulf 8308. (Revised by GG, 18-Apr-2025.)
|- ( ph -> M e. NN )   &    |- ( ph -> N e. NN )   &    |- ( ph -> ( M gcd N ) = 1 )   &    |- X = { x e. NN | x || M }   &    |- Y = { x e. NN | x || N }   &    |- Z = { x e. NN | x || ( M x. N ) }   &    |- ( ( ph /\ j e. X ) -> A e. CC )   &    |- ( ( ph /\ k e. Y ) -> B e. CC )   &    |- ( ( ph /\ ( j e. X /\ k e. Y ) ) -> ( A x. B ) = D )   &    |- ( i = ( j x. k ) -> C = D )   =>    |- ( ph -> ( sum_ j e. X A x. sum_ k e. Y B ) = sum_ i e. Z C )
Theorem	sgmppw 16286*	The value of the divisor function at a prime power. (Contributed by Mario Carneiro, 17-May-2016.)
|- ( ( A e. CC /\ P e. Prime /\ N e. NN0 ) -> ( A sigma ( P ^ N ) ) = sum_ k e. ( 0 ... N ) ( ( P ^c A ) ^ k ) )
Theorem	0sgmppw 16287	A prime power P ^ K has K + 1 divisors. (Contributed by Mario Carneiro, 17-May-2016.)
|- ( ( P e. Prime /\ K e. NN0 ) -> ( 0 sigma ( P ^ K ) ) = ( K + 1 ) )
Theorem	1sgmprm 16288	The sum of divisors for a prime is P + 1 because the only divisors are 1 and P. (Contributed by Mario Carneiro, 17-May-2016.)
|- ( P e. Prime -> ( 1 sigma P ) = ( P + 1 ) )
Theorem	1sgm2ppw 16289	The sum of the divisors of 2 ^ ( N - 1 ). (Contributed by Mario Carneiro, 17-May-2016.)
|- ( N e. NN -> ( 1 sigma ( 2 ^ ( N - 1 ) ) ) = ( ( 2 ^ N ) - 1 ) )
Theorem	sgmmul 16290	The divisor function for fixed parameter A is a multiplicative function. (Contributed by Mario Carneiro, 2-Jul-2015.)
|- ( ( A e. CC /\ ( M e. NN /\ N e. NN /\ ( M gcd N ) = 1 ) ) -> ( A sigma ( M x. N ) ) = ( ( A sigma M ) x. ( A sigma N ) ) )
Theorem	ppiublem1 16291	Lemma for ppiqub 16293. (Contributed by Mario Carneiro, 12-Mar-2014.)
|- ( N <_ 6 /\ ( ( P e. Prime /\ 4 <_ P ) -> ( ( P mod 6 ) e. ( N ... 5 ) -> ( P mod 6 ) e. { 1 , 5 } ) ) )   &    |- M e. NN0   &    |- N = ( M + 1 )   &    |- ( 2 || M \/ 3 || M \/ M e. { 1 , 5 } )   =>    |- ( M <_ 6 /\ ( ( P e. Prime /\ 4 <_ P ) -> ( ( P mod 6 ) e. ( M ... 5 ) -> ( P mod 6 ) e. { 1 , 5 } ) ) )
Theorem	ppiublem2 16292	A prime greater than 3 does not divide 2 or 3, so its residue mod 6 is 1 or 5. (Contributed by Mario Carneiro, 12-Mar-2014.)
|- ( ( P e. Prime /\ 4 <_ P ) -> ( P mod 6 ) e. { 1 , 5 } )
Theorem	ppiqub 16293	An upper bound on the prime-counting function π, which counts the number of primes less than N. (Contributed by Mario Carneiro, 13-Mar-2014.)
|- ( ( N e. QQ /\ 0 <_ N ) -> (π ` N ) <_ ( ( N / 3 ) + 2 ) )
Theorem	chtqleppi 16294	Upper bound on the theta function. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( ( A e. QQ /\ 0 < A ) -> ( theta ` A ) <_ ( (π ` A ) x. ( log ` A ) ) )
Theorem	chtublem 16295	Lemma for chtqub 16296. (Contributed by Mario Carneiro, 13-Mar-2014.)
|- ( N e. NN -> ( theta ` ( ( 2 x. N ) - 1 ) ) <_ ( ( theta ` N ) + ( ( log ` 4 ) x. ( N - 1 ) ) ) )
Theorem	chtqub 16296	An upper bound on the Chebyshev function. (Contributed by Mario Carneiro, 13-Mar-2014.) (Revised 22-Sep-2014.)
|- ( ( N e. QQ /\ 2 < N ) -> ( theta ` N ) < ( ( log ` 2 ) x. ( ( 2 x. N ) - 3 ) ) )
11.4.3  Perfect Number Theorem
Theorem	mersenne 16297	A Mersenne prime is a prime number of the form 2 ^ P - 1. This theorem shows that the P in this expression is necessarily also prime. (Contributed by Mario Carneiro, 17-May-2016.)
|- ( ( P e. ZZ /\ ( ( 2 ^ P ) - 1 ) e. Prime ) -> P e. Prime )
Theorem	perfect1 16298	Euclid's contribution to the Euclid-Euler theorem. A number of the form 2 ^ ( p - 1 ) x. ( 2 ^ p - 1 ) is a perfect number. (Contributed by Mario Carneiro, 17-May-2016.)
|- ( ( P e. ZZ /\ ( ( 2 ^ P ) - 1 ) e. Prime ) -> ( 1 sigma ( ( 2 ^ ( P - 1 ) ) x. ( ( 2 ^ P ) - 1 ) ) ) = ( ( 2 ^ P ) x. ( ( 2 ^ P ) - 1 ) ) )
Theorem	perfectlem1 16299	Lemma for perfect 16301. (Contributed by Mario Carneiro, 7-Jun-2016.)
|- ( ph -> A e. NN )   &    |- ( ph -> B e. NN )   &    |- ( ph -> -. 2 || B )   &    |- ( ph -> ( 1 sigma ( ( 2 ^ A ) x. B ) ) = ( 2 x. ( ( 2 ^ A ) x. B ) ) )   =>    |- ( ph -> ( ( 2 ^ ( A + 1 ) ) e. NN /\ ( ( 2 ^ ( A + 1 ) ) - 1 ) e. NN /\ ( B / ( ( 2 ^ ( A + 1 ) ) - 1 ) ) e. NN ) )
Theorem	perfectlem2 16300	Lemma for perfect 16301. (Contributed by Mario Carneiro, 17-May-2016.) (Revised by Wolf Lammen, 17-Sep-2020.)
|- ( ph -> A e. NN )   &    |- ( ph -> B e. NN )   &    |- ( ph -> -. 2 || B )   &    |- ( ph -> ( 1 sigma ( ( 2 ^ A ) x. B ) ) = ( 2 x. ( ( 2 ^ A ) x. B ) ) )   =>    |- ( ph -> ( B e. Prime /\ B = ( ( 2 ^ ( A + 1 ) ) - 1 ) ) )