P. 130 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 12901-13000   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	rpdvds 12901	If K is relatively prime to N then it is also relatively prime to any divisor M of N. (Contributed by Mario Carneiro, 19-Jun-2015.)
|- ( ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) /\ ( ( K gcd N ) = 1 /\ M || N ) ) -> ( K gcd M ) = 1 )
5.1.12  Cancellability of congruences
Theorem	congr 12902*	Definition of congruence by integer multiple (see ProofWiki "Congruence (Number Theory)", 11-Jul-2021, https://proofwiki.org/wiki/Definition:Congruence_(Number_Theory)): An integer A is congruent to an integer B modulo M if their difference is a multiple of M. See also the definition in [ApostolNT] p. 104: "... a is congruent to b modulo m, and we write a == b (mod m) if m divides the difference a - b", or Wikipedia "Modular arithmetic - Congruence", https://en.wikipedia.org/wiki/Modular_arithmetic#Congruence, 11-Jul-2021,: "Given an integer n > 1, called a modulus, two integers are said to be congruent modulo n, if n is a divisor of their difference (i.e., if there is an integer k such that a-b = kn)". (Contributed by AV, 11-Jul-2021.)
|- ( ( A e. ZZ /\ B e. ZZ /\ M e. NN ) -> ( ( A mod M ) = ( B mod M ) <-> E. n e. ZZ ( n x. M ) = ( A - B ) ) )
Theorem	divgcdcoprm0 12903	Integers divided by gcd are coprime. (Contributed by AV, 12-Jul-2021.)
|- ( ( A e. ZZ /\ B e. ZZ /\ B =/= 0 ) -> ( ( A / ( A gcd B ) ) gcd ( B / ( A gcd B ) ) ) = 1 )
Theorem	divgcdcoprmex 12904*	Integers divided by gcd are coprime (see ProofWiki "Integers Divided by GCD are Coprime", 11-Jul-2021, https://proofwiki.org/wiki/Integers_Divided_by_GCD_are_Coprime): Any pair of integers, not both zero, can be reduced to a pair of coprime ones by dividing them by their gcd. (Contributed by AV, 12-Jul-2021.)
|- ( ( A e. ZZ /\ ( B e. ZZ /\ B =/= 0 ) /\ M = ( A gcd B ) ) -> E. a e. ZZ E. b e. ZZ ( A = ( M x. a ) /\ B = ( M x. b ) /\ ( a gcd b ) = 1 ) )
Theorem	cncongr1 12905	One direction of the bicondition in cncongr 12907. Theorem 5.4 in [ApostolNT] p. 109. (Contributed by AV, 13-Jul-2021.)
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) -> ( A mod M ) = ( B mod M ) ) )
Theorem	cncongr2 12906	The other direction of the bicondition in cncongr 12907. (Contributed by AV, 11-Jul-2021.)
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( A mod M ) = ( B mod M ) -> ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) ) )
Theorem	cncongr 12907	Cancellability of Congruences (see ProofWiki "Cancellability of Congruences, https://proofwiki.org/wiki/Cancellability_of_Congruences, 10-Jul-2021): Two products with a common factor are congruent modulo a positive integer iff the other factors are congruent modulo the integer divided by the greates common divisor of the integer and the common factor. See also Theorem 5.4 "Cancellation law" in [ApostolNT] p. 109. (Contributed by AV, 13-Jul-2021.)
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ M = ( N / ( C gcd N ) ) ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> ( A mod M ) = ( B mod M ) ) )
Theorem	cncongrcoprm 12908	Corollary 1 of Cancellability of Congruences: Two products with a common factor are congruent modulo an integer being coprime to the common factor iff the other factors are congruent modulo the integer. (Contributed by AV, 13-Jul-2021.)
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( N e. NN /\ ( C gcd N ) = 1 ) ) -> ( ( ( A x. C ) mod N ) = ( ( B x. C ) mod N ) <-> ( A mod N ) = ( B mod N ) ) )
5.2  Elementary prime number theory
5.2.1  Elementary properties Remark: to represent odd prime numbers, i.e., all prime numbers except 2, the idiom P e. ( Prime \ { 2 } ) is used. It is a little bit shorter than ( P e. Prime /\ P =/= 2 ). Both representations can be converted into each other by eldifsn 3841.
Syntax	cprime 12909	Extend the definition of a class to include the set of prime numbers.
class Prime
Definition	df-prm 12910*	Define the set of prime numbers. (Contributed by Paul Chapman, 22-Jun-2011.)
|- Prime = { p e. NN | { n e. NN | n || p } ~~ 2o }
Theorem	isprm 12911*	The predicate "is a prime number". A prime number is a positive integer with exactly two positive divisors. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( P e. Prime <-> ( P e. NN /\ { n e. NN | n || P } ~~ 2o ) )
Theorem	prmnn 12912	A prime number is a positive integer. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( P e. Prime -> P e. NN )
Theorem	prmz 12913	A prime number is an integer. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Jonathan Yan, 16-Jul-2017.)
|- ( P e. Prime -> P e. ZZ )
Theorem	prmssnn 12914	The prime numbers are a subset of the positive integers. (Contributed by AV, 22-Jul-2020.)
|- Prime C_ NN
Theorem	prmex 12915	The set of prime numbers exists. (Contributed by AV, 22-Jul-2020.)
|- Prime e. _V
Theorem	1nprm 12916	1 is not a prime number. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Fan Zheng, 3-Jul-2016.)
|- -. 1 e. Prime
Theorem	1idssfct 12917*	The positive divisors of a positive integer include 1 and itself. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( N e. NN -> { 1 , N } C_ { n e. NN | n || N } )
Theorem	isprm2lem 12918*	Lemma for isprm2 12919. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( ( P e. NN /\ P =/= 1 ) -> ( { n e. NN | n || P } ~~ 2o <-> { n e. NN | n || P } = { 1 , P } ) )
Theorem	isprm2 12919*	The predicate "is a prime number". A prime number is an integer greater than or equal to 2 whose only positive divisors are 1 and itself. Definition in [ApostolNT] p. 16. (Contributed by Paul Chapman, 26-Oct-2012.)
|- ( P e. Prime <-> ( P e. ( ZZ>= ` 2 ) /\ A. z e. NN ( z || P -> ( z = 1 \/ z = P ) ) ) )
Theorem	isprm3 12920*	The predicate "is a prime number". A prime number is an integer greater than or equal to 2 with no divisors strictly between 1 and itself. (Contributed by Paul Chapman, 26-Oct-2012.)
|- ( P e. Prime <-> ( P e. ( ZZ>= ` 2 ) /\ A. z e. ( 2 ... ( P - 1 ) ) -. z || P ) )
Theorem	isprm4 12921*	The predicate "is a prime number". A prime number is an integer greater than or equal to 2 whose only divisor greater than or equal to 2 is itself. (Contributed by Paul Chapman, 26-Oct-2012.)
|- ( P e. Prime <-> ( P e. ( ZZ>= ` 2 ) /\ A. z e. ( ZZ>= ` 2 ) ( z || P -> z = P ) ) )
Theorem	prmind2 12922*	A variation on prmind 12923 assuming complete induction for primes. (Contributed by Mario Carneiro, 20-Jun-2015.)
|- ( x = 1 -> ( ph <-> ps ) )   &    |- ( x = y -> ( ph <-> ch ) )   &    |- ( x = z -> ( ph <-> th ) )   &    |- ( x = ( y x. z ) -> ( ph <-> ta ) )   &    |- ( x = A -> ( ph <-> et ) )   &    |- ps   &    |- ( ( x e. Prime /\ A. y e. ( 1 ... ( x - 1 ) ) ch ) -> ph )   &    |- ( ( y e. ( ZZ>= ` 2 ) /\ z e. ( ZZ>= ` 2 ) ) -> ( ( ch /\ th ) -> ta ) )   =>    |- ( A e. NN -> et )
Theorem	prmind 12923*	Perform induction over the multiplicative structure of NN. If a property ph ( x ) holds for the primes and 1 and is preserved under multiplication, then it holds for every positive integer. (Contributed by Mario Carneiro, 20-Jun-2015.)
|- ( x = 1 -> ( ph <-> ps ) )   &    |- ( x = y -> ( ph <-> ch ) )   &    |- ( x = z -> ( ph <-> th ) )   &    |- ( x = ( y x. z ) -> ( ph <-> ta ) )   &    |- ( x = A -> ( ph <-> et ) )   &    |- ps   &    |- ( x e. Prime -> ph )   &    |- ( ( y e. ( ZZ>= ` 2 ) /\ z e. ( ZZ>= ` 2 ) ) -> ( ( ch /\ th ) -> ta ) )   =>    |- ( A e. NN -> et )
Theorem	dvdsprime 12924	If M divides a prime, then M is either the prime or one. (Contributed by Scott Fenton, 8-Apr-2014.)
|- ( ( P e. Prime /\ M e. NN ) -> ( M || P <-> ( M = P \/ M = 1 ) ) )
Theorem	nprm 12925	A product of two integers greater than one is composite. (Contributed by Mario Carneiro, 20-Jun-2015.)
|- ( ( A e. ( ZZ>= ` 2 ) /\ B e. ( ZZ>= ` 2 ) ) -> -. ( A x. B ) e. Prime )
Theorem	nprmi 12926	An inference for compositeness. (Contributed by Mario Carneiro, 18-Feb-2014.) (Revised by Mario Carneiro, 20-Jun-2015.)
|- A e. NN   &    |- B e. NN   &    |- 1 < A   &    |- 1 < B   &    |- ( A x. B ) = N   =>    |- -. N e. Prime
Theorem	dvdsnprmd 12927	If a number is divisible by an integer greater than 1 and less then the number, the number is not prime. (Contributed by AV, 24-Jul-2021.)
|- ( ph -> 1 < A )   &    |- ( ph -> A < N )   &    |- ( ph -> A || N )   =>    |- ( ph -> -. N e. Prime )
Theorem	prm2orodd 12928	A prime number is either 2 or odd. (Contributed by AV, 19-Jun-2021.)
|- ( P e. Prime -> ( P = 2 \/ -. 2 || P ) )
Theorem	2prm 12929	2 is a prime number. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Fan Zheng, 16-Jun-2016.)
|- 2 e. Prime
Theorem	3prm 12930	3 is a prime number. (Contributed by Paul Chapman, 22-Jun-2011.)
|- 3 e. Prime
Theorem	4nprm 12931	4 is not a prime number. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Mario Carneiro, 18-Feb-2014.)
|- -. 4 e. Prime
Theorem	prmdc 12932	Primality is decidable. (Contributed by Jim Kingdon, 30-Sep-2024.)
|- ( N e. NN -> DECID N e. Prime )
Theorem	prmdcz 12933	Primality is decidable. (Contributed by Jim Kingdon, 27-Aug-2026.)
|- ( N e. ZZ -> DECID N e. Prime )
Theorem	prmuz2 12934	A prime number is an integer greater than or equal to 2. (Contributed by Paul Chapman, 17-Nov-2012.)
|- ( P e. Prime -> P e. ( ZZ>= ` 2 ) )
Theorem	prmgt1 12935	A prime number is an integer greater than 1. (Contributed by Alexander van der Vekens, 17-May-2018.)
|- ( P e. Prime -> 1 < P )
Theorem	prmm2nn0 12936	Subtracting 2 from a prime number results in a nonnegative integer. (Contributed by Alexander van der Vekens, 30-Aug-2018.)
|- ( P e. Prime -> ( P - 2 ) e. NN0 )
Theorem	oddprmgt2 12937	An odd prime is greater than 2. (Contributed by AV, 20-Aug-2021.)
|- ( P e. ( Prime \ { 2 } ) -> 2 < P )
Theorem	oddprmge3 12938	An odd prime is greater than or equal to 3. (Contributed by Alexander van der Vekens, 7-Oct-2018.) (Revised by AV, 20-Aug-2021.)
|- ( P e. ( Prime \ { 2 } ) -> P e. ( ZZ>= ` 3 ) )
Theorem	sqnprm 12939	A square is never prime. (Contributed by Mario Carneiro, 20-Jun-2015.)
|- ( A e. ZZ -> -. ( A ^ 2 ) e. Prime )
Theorem	dvdsprm 12940	An integer greater than or equal to 2 divides a prime number iff it is equal to it. (Contributed by Paul Chapman, 26-Oct-2012.)
|- ( ( N e. ( ZZ>= ` 2 ) /\ P e. Prime ) -> ( N || P <-> N = P ) )
Theorem	exprmfct 12941*	Every integer greater than or equal to 2 has a prime factor. (Contributed by Paul Chapman, 26-Oct-2012.) (Proof shortened by Mario Carneiro, 20-Jun-2015.)
|- ( N e. ( ZZ>= ` 2 ) -> E. p e. Prime p || N )
Theorem	prmdvdsfz 12942*	Each integer greater than 1 and less then or equal to a fixed number is divisible by a prime less then or equal to this fixed number. (Contributed by AV, 15-Aug-2020.)
|- ( ( N e. NN /\ I e. ( 2 ... N ) ) -> E. p e. Prime ( p <_ N /\ p || I ) )
Theorem	nprmdvds1 12943	No prime number divides 1. (Contributed by Paul Chapman, 17-Nov-2012.) (Proof shortened by Mario Carneiro, 2-Jul-2015.)
|- ( P e. Prime -> -. P || 1 )
Theorem	isprm5lem 12944*	Lemma for isprm5 12945. The interesting direction (showing that one only needs to check prime divisors up to the square root of P). (Contributed by Jim Kingdon, 20-Oct-2024.)
|- ( ph -> P e. ( ZZ>= ` 2 ) )   &    |- ( ph -> A. z e. Prime ( ( z ^ 2 ) <_ P -> -. z || P ) )   &    |- ( ph -> X e. ( 2 ... ( P - 1 ) ) )   =>    |- ( ph -> -. X || P )
Theorem	isprm5 12945*	One need only check prime divisors of P up to sqr P in order to ensure primality. (Contributed by Mario Carneiro, 18-Feb-2014.)
|- ( P e. Prime <-> ( P e. ( ZZ>= ` 2 ) /\ A. z e. Prime ( ( z ^ 2 ) <_ P -> -. z || P ) ) )
Theorem	divgcdodd 12946	Either A / ( A gcd B ) is odd or B / ( A gcd B ) is odd. (Contributed by Scott Fenton, 19-Apr-2014.)
|- ( ( A e. NN /\ B e. NN ) -> ( -. 2 || ( A / ( A gcd B ) ) \/ -. 2 || ( B / ( A gcd B ) ) ) )
5.2.2  Coprimality and Euclid's lemma (cont.) This section is about coprimality with respect to primes, and a special version of Euclid's lemma for primes is provided, see euclemma 12949.
Theorem	coprm 12947	A prime number either divides an integer or is coprime to it, but not both. Theorem 1.8 in [ApostolNT] p. 17. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( ( P e. Prime /\ N e. ZZ ) -> ( -. P || N <-> ( P gcd N ) = 1 ) )
Theorem	prmrp 12948	Unequal prime numbers are relatively prime. (Contributed by Mario Carneiro, 23-Feb-2014.)
|- ( ( P e. Prime /\ Q e. Prime ) -> ( ( P gcd Q ) = 1 <-> P =/= Q ) )
Theorem	euclemma 12949	Euclid's lemma. A prime number divides the product of two integers iff it divides at least one of them. Theorem 1.9 in [ApostolNT] p. 17. (Contributed by Paul Chapman, 17-Nov-2012.)
|- ( ( P e. Prime /\ M e. ZZ /\ N e. ZZ ) -> ( P || ( M x. N ) <-> ( P || M \/ P || N ) ) )
Theorem	isprm6 12950*	A number is prime iff it satisfies Euclid's lemma euclemma 12949. (Contributed by Mario Carneiro, 6-Sep-2015.)
|- ( P e. Prime <-> ( P e. ( ZZ>= ` 2 ) /\ A. x e. ZZ A. y e. ZZ ( P || ( x x. y ) -> ( P || x \/ P || y ) ) ) )
Theorem	prmdvdsexp 12951	A prime divides a positive power of an integer iff it divides the integer. (Contributed by Mario Carneiro, 24-Feb-2014.) (Revised by Mario Carneiro, 17-Jul-2014.)
|- ( ( P e. Prime /\ A e. ZZ /\ N e. NN ) -> ( P || ( A ^ N ) <-> P || A ) )
Theorem	prmdvdsexpb 12952	A prime divides a positive power of another iff they are equal. (Contributed by Paul Chapman, 30-Nov-2012.) (Revised by Mario Carneiro, 24-Feb-2014.)
|- ( ( P e. Prime /\ Q e. Prime /\ N e. NN ) -> ( P || ( Q ^ N ) <-> P = Q ) )
Theorem	prmdvdsexpr 12953	If a prime divides a nonnegative power of another, then they are equal. (Contributed by Mario Carneiro, 16-Jan-2015.)
|- ( ( P e. Prime /\ Q e. Prime /\ N e. NN0 ) -> ( P || ( Q ^ N ) -> P = Q ) )
Theorem	prmexpb 12954	Two positive prime powers are equal iff the primes and the powers are equal. (Contributed by Paul Chapman, 30-Nov-2012.)
|- ( ( ( P e. Prime /\ Q e. Prime ) /\ ( M e. NN /\ N e. NN ) ) -> ( ( P ^ M ) = ( Q ^ N ) <-> ( P = Q /\ M = N ) ) )
Theorem	prmfac1 12955	The factorial of a number only contains primes less than the base. (Contributed by Mario Carneiro, 6-Mar-2014.)
|- ( ( N e. NN0 /\ P e. Prime /\ P || ( ! ` N ) ) -> P <_ N )
Theorem	rpexp 12956	If two numbers A and B are relatively prime, then they are still relatively prime if raised to a power. (Contributed by Mario Carneiro, 24-Feb-2014.)
|- ( ( A e. ZZ /\ B e. ZZ /\ N e. NN ) -> ( ( ( A ^ N ) gcd B ) = 1 <-> ( A gcd B ) = 1 ) )
Theorem	rpexp1i 12957	Relative primality passes to asymmetric powers. (Contributed by Stefan O'Rear, 27-Sep-2014.)
|- ( ( A e. ZZ /\ B e. ZZ /\ M e. NN0 ) -> ( ( A gcd B ) = 1 -> ( ( A ^ M ) gcd B ) = 1 ) )
Theorem	rpexp12i 12958	Relative primality passes to symmetric powers. (Contributed by Stefan O'Rear, 27-Sep-2014.)
|- ( ( A e. ZZ /\ B e. ZZ /\ ( M e. NN0 /\ N e. NN0 ) ) -> ( ( A gcd B ) = 1 -> ( ( A ^ M ) gcd ( B ^ N ) ) = 1 ) )
Theorem	prmndvdsfaclt 12959	A prime number does not divide the factorial of a nonnegative integer less than the prime number. (Contributed by AV, 13-Jul-2021.)
|- ( ( P e. Prime /\ N e. NN0 ) -> ( N < P -> -. P || ( ! ` N ) ) )
Theorem	cncongrprm 12960	Corollary 2 of Cancellability of Congruences: Two products with a common factor are congruent modulo a prime number not dividing the common factor iff the other factors are congruent modulo the prime number. (Contributed by AV, 13-Jul-2021.)
|- ( ( ( A e. ZZ /\ B e. ZZ /\ C e. ZZ ) /\ ( P e. Prime /\ -. P || C ) ) -> ( ( ( A x. C ) mod P ) = ( ( B x. C ) mod P ) <-> ( A mod P ) = ( B mod P ) ) )
Theorem	isevengcd2 12961	The predicate "is an even number". An even number and 2 have 2 as greatest common divisor. (Contributed by AV, 1-Jul-2020.) (Revised by AV, 8-Aug-2021.)
|- ( Z e. ZZ -> ( 2 || Z <-> ( 2 gcd Z ) = 2 ) )
Theorem	isoddgcd1 12962	The predicate "is an odd number". An odd number and 2 have 1 as greatest common divisor. (Contributed by AV, 1-Jul-2020.) (Revised by AV, 8-Aug-2021.)
|- ( Z e. ZZ -> ( -. 2 || Z <-> ( 2 gcd Z ) = 1 ) )
Theorem	3lcm2e6 12963	The least common multiple of three and two is six. The operands are unequal primes and thus coprime, so the result is (the absolute value of) their product. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 27-Aug-2020.)
|- ( 3 lcm 2 ) = 6
5.2.3  Non-rationality of square root of 2
Theorem	sqrt2irrlem 12964	Lemma for sqrt2irr 12965. This is the core of the proof: - if A / B = sqr ( 2 ), then A and B are even, so A / 2 and B / 2 are smaller representatives, which is absurd by the method of infinite descent (here implemented by strong induction). (Contributed by NM, 20-Aug-2001.) (Revised by Mario Carneiro, 12-Sep-2015.)
|- ( ph -> A e. ZZ )   &    |- ( ph -> B e. NN )   &    |- ( ph -> ( sqr ` 2 ) = ( A / B ) )   =>    |- ( ph -> ( ( A / 2 ) e. ZZ /\ ( B / 2 ) e. NN ) )
Theorem	sqrt2irr 12965	The square root of 2 is not rational. That is, for any rational number, ( sqr ` 2 ) does not equal it. However, if we were to say "the square root of 2 is irrational" that would mean something stronger: "for any rational number, ( sqr ` 2 ) is apart from it" (the two statements are equivalent given excluded middle). See sqrt2irrap 12984 for the proof that the square root of two is irrational. The proof's core is proven in sqrt2irrlem 12964, which shows that if A / B = sqr ( 2 ), then A and B are even, so A / 2 and B / 2 are smaller representatives, which is absurd. (Contributed by NM, 8-Jan-2002.) (Proof shortened by Mario Carneiro, 12-Sep-2015.)
|- ( sqr ` 2 ) e/ QQ
Theorem	sqrt2re 12966	The square root of 2 exists and is a real number. (Contributed by NM, 3-Dec-2004.)
|- ( sqr ` 2 ) e. RR
Theorem	sqrt2irr0 12967	The square root of 2 is not rational. (Contributed by AV, 23-Dec-2022.)
|- ( sqr ` 2 ) e. ( RR \ QQ )
Theorem	pwbdvdslemn 12968*	Lemma for pwbdvds 12969. If a natural number has some power of a base which does not divide it, there is a highest power of the base which does divide it. (Contributed by Jim Kingdon, 14-Nov-2021.) (Revised by Jim Kingdon, 17-Aug-2026.)
|- ( ph -> N e. NN )   &    |- ( ph -> A e. NN )   &    |- ( ph -> B e. NN )   &    |- ( ph -> -. ( B ^ A ) || N )   =>    |- ( ph -> E. m e. NN0 ( ( B ^ m ) || N /\ -. ( B ^ ( m + 1 ) ) || N ) )
Theorem	pwbdvds 12969*	A natural number has a highest power of a base which divides it. (Contributed by Jim Kingdon, 16-Nov-2021.) (Revised by Jim Kingdon, 18-Aug-2026.)
|- ( ( N e. NN /\ B e. ( ZZ>= ` 2 ) ) -> E. m e. NN0 ( ( B ^ m ) || N /\ -. ( B ^ ( m + 1 ) ) || N ) )
Theorem	pwbdvdseulemle 12970	Lemma for pwbdvdseu 12971. Powers of a base which do and do not divide a natural number. (Contributed by Jim Kingdon, 17-Nov-2021.) (Revised by Jim Kingdon, 18-Aug-2026.)
|- ( ph -> N e. NN )   &    |- ( ph -> A e. NN0 )   &    |- ( ph -> B e. NN0 )   &    |- ( ph -> P e. NN )   &    |- ( ph -> ( P ^ A ) || N )   &    |- ( ph -> -. ( P ^ ( B + 1 ) ) || N )   =>    |- ( ph -> A <_ B )
Theorem	pwbdvdseu 12971*	A natural number has a unique highest power of a base which divides it. (Contributed by Jim Kingdon, 16-Nov-2021.) (Revised by Jim Kingdon, 18-Aug-2026.)
|- ( ( N e. NN /\ B e. ( ZZ>= ` 2 ) ) -> E! m e. NN0 ( ( B ^ m ) || N /\ -. ( B ^ ( m + 1 ) ) || N ) )
Theorem	nnmaxpwlemxy 12972*	Lemma for nnmaxpw 12977. Another way of stating that decomposing a natural number into a power of a base and a number not divisible by that base is unique. (Contributed by Jim Kingdon, 16-Nov-2021.) (Revised by Jim Kingdon, 18-Aug-2026.)
|- ( ph -> X e. NN )   &    |- ( ph -> B e. ( ZZ>= ` 2 ) )   &    |- ( ph -> -. B || X )   &    |- ( ph -> Y e. NN0 )   &    |- ( ph -> A = ( ( B ^ Y ) x. X ) )   =>    |- ( ph -> ( X = ( A / ( B ^ ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) ) ) /\ Y = ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) ) )
Theorem	nnmaxpwlemdvds 12973*	Lemma for nnmaxpw 12977. A natural number is divisible by the highest power of a base which divides it. (Contributed by Jim Kingdon, 17-Nov-2021.) (Revised by Jim Kingdon, 19-Aug-2026.)
|- ( ( A e. NN /\ B e. ( ZZ>= ` 2 ) ) -> ( B ^ ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) ) || A )
Theorem	nnmaxpwlemndvds 12974*	Lemma for nnmaxpw 12977. A natural number is not divisible by one more than the highest power of a base which divides it. (Contributed by Jim Kingdon, 17-Nov-2021.) (Revised by Jim Kingdon, 19-Aug-2026.)
|- ( ( A e. NN /\ B e. ( ZZ>= ` 2 ) ) -> -. ( B ^ ( ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) + 1 ) ) || A )
Theorem	nnmaxpwlemnfac 12975*	Lemma for nnmaxpw 12977. Removing the powers of a base from a natural number produces a number not divisible by that base. (Contributed by Jim Kingdon, 16-Nov-2021.) (Revised by Jim Kingdon, 19-Aug-2026.)
|- ( ( A e. NN /\ B e. ( ZZ>= ` 2 ) ) -> -. B || ( A / ( B ^ ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) ) ) )
Theorem	nnmaxpwlemparts 12976*	Lemma for nnmaxpw 12977. Decomposing a number into parts. (Contributed by Jim Kingdon, 16-Nov-2021.) (Revised by Jim Kingdon, 19-Aug-2026.)
|- ( B e. ( ZZ>= ` 2 ) -> ( ( ( ( X e. NN /\ -. B || X ) /\ Y e. NN0 ) /\ A = ( ( B ^ Y ) x. X ) ) <-> ( A e. NN /\ ( X = ( A / ( B ^ ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) ) ) /\ Y = ( iota_ z e. NN0 ( ( B ^ z ) || A /\ -. ( B ^ ( z + 1 ) ) || A ) ) ) ) ) )
Theorem	nnmaxpw 12977*	The function F that decomposes a number into its "odd" and "even" parts, which is to say the largest power of a base and largest divisor of the number not divisible by that base, is a bijection from pairs of a nonnegative integer and a number not divisible by that base to positive integers. (Contributed by Thierry Arnoux, 15-Aug-2017.) (Revised by Jim Kingdon, 19-Aug-2026.)
|- J = { z e. NN | -. B || z }   &    |- F = ( x e. J , y e. NN0 |-> ( ( B ^ y ) x. x ) )   =>    |- ( B e. ( ZZ>= ` 2 ) -> F : ( J X. NN0 ) -1-1-onto-> NN )
Theorem	oddpwdc 12978*	The function F that decomposes a number into its "odd" and "even" parts, which is to say the largest power of two and largest odd divisor of a number, is a bijection from pairs of a nonnegative integer and an odd number to positive integers. (Contributed by Thierry Arnoux, 15-Aug-2017.)
|- J = { z e. NN | -. 2 || z }   &    |- F = ( x e. J , y e. NN0 |-> ( ( 2 ^ y ) x. x ) )   =>    |- F : ( J X. NN0 ) -1-1-onto-> NN
Theorem	sqpweven 12979*	The greatest power of two dividing the square of an integer is an even power of two. (Contributed by Jim Kingdon, 17-Nov-2021.)
|- J = { z e. NN | -. 2 || z }   &    |- F = ( x e. J , y e. NN0 |-> ( ( 2 ^ y ) x. x ) )   =>    |- ( A e. NN -> 2 || ( 2nd ` ( `' F ` ( A ^ 2 ) ) ) )
Theorem	2sqpwodd 12980*	The greatest power of two dividing twice the square of an integer is an odd power of two. (Contributed by Jim Kingdon, 17-Nov-2021.)
|- J = { z e. NN | -. 2 || z }   &    |- F = ( x e. J , y e. NN0 |-> ( ( 2 ^ y ) x. x ) )   =>    |- ( A e. NN -> -. 2 || ( 2nd ` ( `' F ` ( 2 x. ( A ^ 2 ) ) ) ) )
Theorem	sqne2sq 12981	The square of a natural number can never be equal to two times the square of a natural number. (Contributed by Jim Kingdon, 17-Nov-2021.)
|- ( ( A e. NN /\ B e. NN ) -> ( A ^ 2 ) =/= ( 2 x. ( B ^ 2 ) ) )
Theorem	znege1 12982	The absolute value of the difference between two unequal integers is at least one. (Contributed by Jim Kingdon, 31-Jan-2022.)
|- ( ( A e. ZZ /\ B e. ZZ /\ A =/= B ) -> 1 <_ ( abs ` ( A - B ) ) )
Theorem	sqrt2irraplemnn 12983	Lemma for sqrt2irrap 12984. The square root of 2 is apart from a positive rational expressed as a numerator and denominator. (Contributed by Jim Kingdon, 2-Oct-2021.)
|- ( ( A e. NN /\ B e. NN ) -> ( sqr ` 2 ) # ( A / B ) )
Theorem	sqrt2irrap 12984	The square root of 2 is irrational. That is, for any rational number, ( sqr ` 2 ) is apart from it. In the absence of excluded middle, we can distinguish between this and "the square root of 2 is not rational" which is sqrt2irr 12965. (Contributed by Jim Kingdon, 2-Oct-2021.)
|- ( Q e. QQ -> ( sqr ` 2 ) # Q )
5.2.4  Properties of the canonical representation of a rational
Syntax	cnumer 12985	Extend class notation to include canonical numerator function.
class numer
Syntax	cdenom 12986	Extend class notation to include canonical denominator function.
class denom
Definition	df-numer 12987*	The canonical numerator of a rational is the numerator of the rational's reduced fraction representation (no common factors, denominator positive). (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- numer = ( y e. QQ |-> ( 1st ` ( iota_ x e. ( ZZ X. NN ) ( ( ( 1st ` x ) gcd ( 2nd ` x ) ) = 1 /\ y = ( ( 1st ` x ) / ( 2nd ` x ) ) ) ) ) )
Definition	df-denom 12988*	The canonical denominator of a rational is the denominator of the rational's reduced fraction representation (no common factors, denominator positive). (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- denom = ( y e. QQ |-> ( 2nd ` ( iota_ x e. ( ZZ X. NN ) ( ( ( 1st ` x ) gcd ( 2nd ` x ) ) = 1 /\ y = ( ( 1st ` x ) / ( 2nd ` x ) ) ) ) ) )
Theorem	qnumval 12989*	Value of the canonical numerator function. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> (numer ` A ) = ( 1st ` ( iota_ x e. ( ZZ X. NN ) ( ( ( 1st ` x ) gcd ( 2nd ` x ) ) = 1 /\ A = ( ( 1st ` x ) / ( 2nd ` x ) ) ) ) ) )
Theorem	qdenval 12990*	Value of the canonical denominator function. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> (denom ` A ) = ( 2nd ` ( iota_ x e. ( ZZ X. NN ) ( ( ( 1st ` x ) gcd ( 2nd ` x ) ) = 1 /\ A = ( ( 1st ` x ) / ( 2nd ` x ) ) ) ) ) )
Theorem	qnumdencl 12991	Lemma for qnumcl 12992 and qdencl 12993. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> ( (numer ` A ) e. ZZ /\ (denom ` A ) e. NN ) )
Theorem	qnumcl 12992	The canonical numerator of a rational is an integer. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> (numer ` A ) e. ZZ )
Theorem	qdencl 12993	The canonical denominator is a positive integer. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> (denom ` A ) e. NN )
Theorem	fnum 12994	Canonical numerator defines a function. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- numer : QQ --> ZZ
Theorem	fden 12995	Canonical denominator defines a function. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- denom : QQ --> NN
Theorem	qnumdenbi 12996	Two numbers are the canonical representation of a rational iff they are coprime and have the right quotient. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( ( A e. QQ /\ B e. ZZ /\ C e. NN ) -> ( ( ( B gcd C ) = 1 /\ A = ( B / C ) ) <-> ( (numer ` A ) = B /\ (denom ` A ) = C ) ) )
Theorem	qnumdencoprm 12997	The canonical representation of a rational is fully reduced. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> ( (numer ` A ) gcd (denom ` A ) ) = 1 )
Theorem	qeqnumdivden 12998	Recover a rational number from its canonical representation. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> A = ( (numer ` A ) / (denom ` A ) ) )
Theorem	qmuldeneqnum 12999	Multiplying a rational by its denominator results in an integer. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( A e. QQ -> ( A x. (denom ` A ) ) = (numer ` A ) )
Theorem	divnumden 13000	Calculate the reduced form of a quotient using gcd. (Contributed by Stefan O'Rear, 13-Sep-2014.)
|- ( ( A e. ZZ /\ B e. NN ) -> ( (numer ` ( A / B ) ) = ( A / ( A gcd B ) ) /\ (denom ` ( A / B ) ) = ( B / ( A gcd B ) ) ) )