P. 121 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 12001-12100   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	fzm1ndvds 12001	No number between 1 and M - 1 divides M. (Contributed by Mario Carneiro, 24-Jan-2015.)
|- ( ( M e. NN /\ N e. ( 1 ... ( M - 1 ) ) ) -> -. M || N )
Theorem	fzo0dvdseq 12002	Zero is the only one of the first A nonnegative integers that is divisible by A. (Contributed by Stefan O'Rear, 6-Sep-2015.)
|- ( B e. ( 0..^ A ) -> ( A || B <-> B = 0 ) )
Theorem	fzocongeq 12003	Two different elements of a half-open range are not congruent mod its length. (Contributed by Stefan O'Rear, 6-Sep-2015.)
|- ( ( A e. ( C..^ D ) /\ B e. ( C..^ D ) ) -> ( ( D - C ) || ( A - B ) <-> A = B ) )
Theorem	addmodlteqALT 12004	Two nonnegative integers less than the modulus are equal iff the sums of these integer with another integer are equal modulo the modulus. Shorter proof of addmodlteq 10472 based on the "divides" relation. (Contributed by AV, 14-Mar-2021.) (New usage is discouraged.) (Proof modification is discouraged.)
|- ( ( I e. ( 0..^ N ) /\ J e. ( 0..^ N ) /\ S e. ZZ ) -> ( ( ( I + S ) mod N ) = ( ( J + S ) mod N ) <-> I = J ) )
Theorem	dvdsfac 12005	A positive integer divides any greater factorial. (Contributed by Paul Chapman, 28-Nov-2012.)
|- ( ( K e. NN /\ N e. ( ZZ>= ` K ) ) -> K || ( ! ` N ) )
Theorem	dvdsexp 12006	A power divides a power with a greater exponent. (Contributed by Mario Carneiro, 23-Feb-2014.)
|- ( ( A e. ZZ /\ M e. NN0 /\ N e. ( ZZ>= ` M ) ) -> ( A ^ M ) || ( A ^ N ) )
Theorem	dvdsmod 12007	Any number K whose mod base N is divisible by a divisor P of the base is also divisible by P. This means that primes will also be relatively prime to the base when reduced mod N for any base. (Contributed by Mario Carneiro, 13-Mar-2014.)
|- ( ( ( P e. NN /\ N e. NN /\ K e. ZZ ) /\ P || N ) -> ( P || ( K mod N ) <-> P || K ) )
Theorem	mulmoddvds 12008	If an integer is divisible by a positive integer, the product of this integer with another integer modulo the positive integer is 0. (Contributed by Alexander van der Vekens, 30-Aug-2018.)
|- ( ( N e. NN /\ A e. ZZ /\ B e. ZZ ) -> ( N || A -> ( ( A x. B ) mod N ) = 0 ) )
Theorem	3dvdsdec 12009	A decimal number is divisible by three iff the sum of its two "digits" is divisible by three. The term "digits" in its narrow sense is only correct if A and B actually are digits (i.e. nonnegative integers less than 10). However, this theorem holds for arbitrary nonnegative integers A and B, especially if A is itself a decimal number, e.g., A = ; C D. (Contributed by AV, 14-Jun-2021.) (Revised by AV, 8-Sep-2021.)
|- A e. NN0   &    |- B e. NN0   =>    |- ( 3 || ; A B <-> 3 || ( A + B ) )
Theorem	3dvds2dec 12010	A decimal number is divisible by three iff the sum of its three "digits" is divisible by three. The term "digits" in its narrow sense is only correct if A, B and C actually are digits (i.e. nonnegative integers less than 10). However, this theorem holds for arbitrary nonnegative integers A, B and C. (Contributed by AV, 14-Jun-2021.) (Revised by AV, 1-Aug-2021.)
|- A e. NN0   &    |- B e. NN0   &    |- C e. NN0   =>    |- ( 3 || ;; A B C <-> 3 || ( ( A + B ) + C ) )
5.1.2  Even and odd numbers The set ZZ of integers can be partitioned into the set of even numbers and the set of odd numbers, see zeo4 12014. Instead of defining new class variables Even and Odd to represent these sets, we use the idiom 2 || N to say that " N is even" (which implies N e. ZZ, see evenelz 12011) and -. 2 || N to say that " N is odd" (under the assumption that N e. ZZ). The previously proven theorems about even and odd numbers, like zneo 9421, zeo 9425, zeo2 9426, etc. use different representations, which are equivalent with the representations using the divides relation, see evend2 12033 and oddp1d2 12034. The corresponding theorems are zeneo 12015, zeo3 12012 and zeo4 12014.
Theorem	evenelz 12011	An even number is an integer. This follows immediately from the reverse closure of the divides relation, see dvdszrcl 11938. (Contributed by AV, 22-Jun-2021.)
|- ( 2 || N -> N e. ZZ )
Theorem	zeo3 12012	An integer is even or odd. (Contributed by AV, 17-Jun-2021.)
|- ( N e. ZZ -> ( 2 || N \/ -. 2 || N ) )
Theorem	zeoxor 12013	An integer is even or odd but not both. (Contributed by Jim Kingdon, 10-Nov-2021.)
|- ( N e. ZZ -> ( 2 || N \/_ -. 2 || N ) )
Theorem	zeo4 12014	An integer is even or odd but not both. (Contributed by AV, 17-Jun-2021.)
|- ( N e. ZZ -> ( 2 || N <-> -. -. 2 || N ) )
Theorem	zeneo 12015	No even integer equals an odd integer (i.e. no integer can be both even and odd). Exercise 10(a) of [Apostol] p. 28. This variant of zneo 9421 follows immediately from the fact that a contradiction implies anything, see pm2.21i 647. (Contributed by AV, 22-Jun-2021.)
|- ( ( A e. ZZ /\ B e. ZZ ) -> ( ( 2 || A /\ -. 2 || B ) -> A =/= B ) )
Theorem	odd2np1lem 12016*	Lemma for odd2np1 12017. (Contributed by Scott Fenton, 3-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
|- ( N e. NN0 -> ( E. n e. ZZ ( ( 2 x. n ) + 1 ) = N \/ E. k e. ZZ ( k x. 2 ) = N ) )
Theorem	odd2np1 12017*	An integer is odd iff it is one plus twice another integer. (Contributed by Scott Fenton, 3-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
|- ( N e. ZZ -> ( -. 2 || N <-> E. n e. ZZ ( ( 2 x. n ) + 1 ) = N ) )
Theorem	even2n 12018*	An integer is even iff it is twice another integer. (Contributed by AV, 25-Jun-2020.)
|- ( 2 || N <-> E. n e. ZZ ( 2 x. n ) = N )
Theorem	oddm1even 12019	An integer is odd iff its predecessor is even. (Contributed by Mario Carneiro, 5-Sep-2016.)
|- ( N e. ZZ -> ( -. 2 || N <-> 2 || ( N - 1 ) ) )
Theorem	oddp1even 12020	An integer is odd iff its successor is even. (Contributed by Mario Carneiro, 5-Sep-2016.)
|- ( N e. ZZ -> ( -. 2 || N <-> 2 || ( N + 1 ) ) )
Theorem	oexpneg 12021	The exponential of the negative of a number, when the exponent is odd. (Contributed by Mario Carneiro, 25-Apr-2015.)
|- ( ( A e. CC /\ N e. NN /\ -. 2 || N ) -> ( -u A ^ N ) = -u ( A ^ N ) )
Theorem	mod2eq0even 12022	An integer is 0 modulo 2 iff it is even (i.e. divisible by 2), see example 2 in [ApostolNT] p. 107. (Contributed by AV, 21-Jul-2021.)
|- ( N e. ZZ -> ( ( N mod 2 ) = 0 <-> 2 || N ) )
Theorem	mod2eq1n2dvds 12023	An integer is 1 modulo 2 iff it is odd (i.e. not divisible by 2), see example 3 in [ApostolNT] p. 107. (Contributed by AV, 24-May-2020.)
|- ( N e. ZZ -> ( ( N mod 2 ) = 1 <-> -. 2 || N ) )
Theorem	oddnn02np1 12024*	A nonnegative integer is odd iff it is one plus twice another nonnegative integer. (Contributed by AV, 19-Jun-2021.)
|- ( N e. NN0 -> ( -. 2 || N <-> E. n e. NN0 ( ( 2 x. n ) + 1 ) = N ) )
Theorem	oddge22np1 12025*	An integer greater than one is odd iff it is one plus twice a positive integer. (Contributed by AV, 16-Aug-2021.)
|- ( N e. ( ZZ>= ` 2 ) -> ( -. 2 || N <-> E. n e. NN ( ( 2 x. n ) + 1 ) = N ) )
Theorem	evennn02n 12026*	A nonnegative integer is even iff it is twice another nonnegative integer. (Contributed by AV, 12-Aug-2021.)
|- ( N e. NN0 -> ( 2 || N <-> E. n e. NN0 ( 2 x. n ) = N ) )
Theorem	evennn2n 12027*	A positive integer is even iff it is twice another positive integer. (Contributed by AV, 12-Aug-2021.)
|- ( N e. NN -> ( 2 || N <-> E. n e. NN ( 2 x. n ) = N ) )
Theorem	2tp1odd 12028	A number which is twice an integer increased by 1 is odd. (Contributed by AV, 16-Jul-2021.)
|- ( ( A e. ZZ /\ B = ( ( 2 x. A ) + 1 ) ) -> -. 2 || B )
Theorem	mulsucdiv2z 12029	An integer multiplied with its successor divided by 2 yields an integer, i.e. an integer multiplied with its successor is even. (Contributed by AV, 19-Jul-2021.)
|- ( N e. ZZ -> ( ( N x. ( N + 1 ) ) / 2 ) e. ZZ )
Theorem	sqoddm1div8z 12030	A squared odd number minus 1 divided by 8 is an integer. (Contributed by AV, 19-Jul-2021.)
|- ( ( N e. ZZ /\ -. 2 || N ) -> ( ( ( N ^ 2 ) - 1 ) / 8 ) e. ZZ )
Theorem	2teven 12031	A number which is twice an integer is even. (Contributed by AV, 16-Jul-2021.)
|- ( ( A e. ZZ /\ B = ( 2 x. A ) ) -> 2 || B )
Theorem	zeo5 12032	An integer is either even or odd, version of zeo3 12012 avoiding the negation of the representation of an odd number. (Proposed by BJ, 21-Jun-2021.) (Contributed by AV, 26-Jun-2020.)
|- ( N e. ZZ -> ( 2 || N \/ 2 || ( N + 1 ) ) )
Theorem	evend2 12033	An integer is even iff its quotient with 2 is an integer. This is a representation of even numbers without using the divides relation, see zeo 9425 and zeo2 9426. (Contributed by AV, 22-Jun-2021.)
|- ( N e. ZZ -> ( 2 || N <-> ( N / 2 ) e. ZZ ) )
Theorem	oddp1d2 12034	An integer is odd iff its successor divided by 2 is an integer. This is a representation of odd numbers without using the divides relation, see zeo 9425 and zeo2 9426. (Contributed by AV, 22-Jun-2021.)
|- ( N e. ZZ -> ( -. 2 || N <-> ( ( N + 1 ) / 2 ) e. ZZ ) )
Theorem	zob 12035	Alternate characterizations of an odd number. (Contributed by AV, 7-Jun-2020.)
|- ( N e. ZZ -> ( ( ( N + 1 ) / 2 ) e. ZZ <-> ( ( N - 1 ) / 2 ) e. ZZ ) )
Theorem	oddm1d2 12036	An integer is odd iff its predecessor divided by 2 is an integer. This is another representation of odd numbers without using the divides relation. (Contributed by AV, 18-Jun-2021.) (Proof shortened by AV, 22-Jun-2021.)
|- ( N e. ZZ -> ( -. 2 || N <-> ( ( N - 1 ) / 2 ) e. ZZ ) )
Theorem	ltoddhalfle 12037	An integer is less than half of an odd number iff it is less than or equal to the half of the predecessor of the odd number (which is an even number). (Contributed by AV, 29-Jun-2021.)
|- ( ( N e. ZZ /\ -. 2 || N /\ M e. ZZ ) -> ( M < ( N / 2 ) <-> M <_ ( ( N - 1 ) / 2 ) ) )
Theorem	halfleoddlt 12038	An integer is greater than half of an odd number iff it is greater than or equal to the half of the odd number. (Contributed by AV, 1-Jul-2021.)
|- ( ( N e. ZZ /\ -. 2 || N /\ M e. ZZ ) -> ( ( N / 2 ) <_ M <-> ( N / 2 ) < M ) )
Theorem	opoe 12039	The sum of two odds is even. (Contributed by Scott Fenton, 7-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
|- ( ( ( A e. ZZ /\ -. 2 || A ) /\ ( B e. ZZ /\ -. 2 || B ) ) -> 2 || ( A + B ) )
Theorem	omoe 12040	The difference of two odds is even. (Contributed by Scott Fenton, 7-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
|- ( ( ( A e. ZZ /\ -. 2 || A ) /\ ( B e. ZZ /\ -. 2 || B ) ) -> 2 || ( A - B ) )
Theorem	opeo 12041	The sum of an odd and an even is odd. (Contributed by Scott Fenton, 7-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
|- ( ( ( A e. ZZ /\ -. 2 || A ) /\ ( B e. ZZ /\ 2 || B ) ) -> -. 2 || ( A + B ) )
Theorem	omeo 12042	The difference of an odd and an even is odd. (Contributed by Scott Fenton, 7-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
|- ( ( ( A e. ZZ /\ -. 2 || A ) /\ ( B e. ZZ /\ 2 || B ) ) -> -. 2 || ( A - B ) )
Theorem	m1expe 12043	Exponentiation of -1 by an even power. Variant of m1expeven 10660. (Contributed by AV, 25-Jun-2021.)
|- ( 2 || N -> ( -u 1 ^ N ) = 1 )
Theorem	m1expo 12044	Exponentiation of -1 by an odd power. (Contributed by AV, 26-Jun-2021.)
|- ( ( N e. ZZ /\ -. 2 || N ) -> ( -u 1 ^ N ) = -u 1 )
Theorem	m1exp1 12045	Exponentiation of negative one is one iff the exponent is even. (Contributed by AV, 20-Jun-2021.)
|- ( N e. ZZ -> ( ( -u 1 ^ N ) = 1 <-> 2 || N ) )
Theorem	nn0enne 12046	A positive integer is an even nonnegative integer iff it is an even positive integer. (Contributed by AV, 30-May-2020.)
|- ( N e. NN -> ( ( N / 2 ) e. NN0 <-> ( N / 2 ) e. NN ) )
Theorem	nn0ehalf 12047	The half of an even nonnegative integer is a nonnegative integer. (Contributed by AV, 22-Jun-2020.) (Revised by AV, 28-Jun-2021.)
|- ( ( N e. NN0 /\ 2 || N ) -> ( N / 2 ) e. NN0 )
Theorem	nnehalf 12048	The half of an even positive integer is a positive integer. (Contributed by AV, 28-Jun-2021.)
|- ( ( N e. NN /\ 2 || N ) -> ( N / 2 ) e. NN )
Theorem	nn0o1gt2 12049	An odd nonnegative integer is either 1 or greater than 2. (Contributed by AV, 2-Jun-2020.)
|- ( ( N e. NN0 /\ ( ( N + 1 ) / 2 ) e. NN0 ) -> ( N = 1 \/ 2 < N ) )
Theorem	nno 12050	An alternate characterization of an odd integer greater than 1. (Contributed by AV, 2-Jun-2020.)
|- ( ( N e. ( ZZ>= ` 2 ) /\ ( ( N + 1 ) / 2 ) e. NN0 ) -> ( ( N - 1 ) / 2 ) e. NN )
Theorem	nn0o 12051	An alternate characterization of an odd nonnegative integer. (Contributed by AV, 28-May-2020.) (Proof shortened by AV, 2-Jun-2020.)
|- ( ( N e. NN0 /\ ( ( N + 1 ) / 2 ) e. NN0 ) -> ( ( N - 1 ) / 2 ) e. NN0 )
Theorem	nn0ob 12052	Alternate characterizations of an odd nonnegative integer. (Contributed by AV, 4-Jun-2020.)
|- ( N e. NN0 -> ( ( ( N + 1 ) / 2 ) e. NN0 <-> ( ( N - 1 ) / 2 ) e. NN0 ) )
Theorem	nn0oddm1d2 12053	A positive integer is odd iff its predecessor divided by 2 is a positive integer. (Contributed by AV, 28-Jun-2021.)
|- ( N e. NN0 -> ( -. 2 || N <-> ( ( N - 1 ) / 2 ) e. NN0 ) )
Theorem	nnoddm1d2 12054	A positive integer is odd iff its successor divided by 2 is a positive integer. (Contributed by AV, 28-Jun-2021.)
|- ( N e. NN -> ( -. 2 || N <-> ( ( N + 1 ) / 2 ) e. NN ) )
Theorem	z0even 12055	0 is even. (Contributed by AV, 11-Feb-2020.) (Revised by AV, 23-Jun-2021.)
|- 2 || 0
Theorem	n2dvds1 12056	2 does not divide 1 (common case). That means 1 is odd. (Contributed by David A. Wheeler, 8-Dec-2018.)
|- -. 2 || 1
Theorem	n2dvdsm1 12057	2 does not divide -1. That means -1 is odd. (Contributed by AV, 15-Aug-2021.)
|- -. 2 || -u 1
Theorem	z2even 12058	2 is even. (Contributed by AV, 12-Feb-2020.) (Revised by AV, 23-Jun-2021.)
|- 2 || 2
Theorem	n2dvds3 12059	2 does not divide 3, i.e. 3 is an odd number. (Contributed by AV, 28-Feb-2021.)
|- -. 2 || 3
Theorem	z4even 12060	4 is an even number. (Contributed by AV, 23-Jul-2020.) (Revised by AV, 4-Jul-2021.)
|- 2 || 4
Theorem	4dvdseven 12061	An integer which is divisible by 4 is an even integer. (Contributed by AV, 4-Jul-2021.)
|- ( 4 || N -> 2 || N )
5.1.3  The division algorithm
Theorem	divalglemnn 12062*	Lemma for divalg 12068. Existence for a positive denominator. (Contributed by Jim Kingdon, 30-Nov-2021.)
|- ( ( N e. ZZ /\ D e. NN ) -> E. r e. ZZ E. q e. ZZ ( 0 <_ r /\ r < ( abs ` D ) /\ N = ( ( q x. D ) + r ) ) )
Theorem	divalglemqt 12063	Lemma for divalg 12068. The Q = T case involved in showing uniqueness. (Contributed by Jim Kingdon, 5-Dec-2021.)
|- ( ph -> D e. ZZ )   &    |- ( ph -> R e. ZZ )   &    |- ( ph -> S e. ZZ )   &    |- ( ph -> Q e. ZZ )   &    |- ( ph -> T e. ZZ )   &    |- ( ph -> Q = T )   &    |- ( ph -> ( ( Q x. D ) + R ) = ( ( T x. D ) + S ) )   =>    |- ( ph -> R = S )
Theorem	divalglemnqt 12064	Lemma for divalg 12068. The Q < T case involved in showing uniqueness. (Contributed by Jim Kingdon, 4-Dec-2021.)
|- ( ph -> D e. NN )   &    |- ( ph -> R e. ZZ )   &    |- ( ph -> S e. ZZ )   &    |- ( ph -> Q e. ZZ )   &    |- ( ph -> T e. ZZ )   &    |- ( ph -> 0 <_ S )   &    |- ( ph -> R < D )   &    |- ( ph -> ( ( Q x. D ) + R ) = ( ( T x. D ) + S ) )   =>    |- ( ph -> -. Q < T )
Theorem	divalglemeunn 12065*	Lemma for divalg 12068. Uniqueness for a positive denominator. (Contributed by Jim Kingdon, 4-Dec-2021.)
|- ( ( N e. ZZ /\ D e. NN ) -> E! r e. ZZ E. q e. ZZ ( 0 <_ r /\ r < ( abs ` D ) /\ N = ( ( q x. D ) + r ) ) )
Theorem	divalglemex 12066*	Lemma for divalg 12068. The quotient and remainder exist. (Contributed by Jim Kingdon, 30-Nov-2021.)
|- ( ( N e. ZZ /\ D e. ZZ /\ D =/= 0 ) -> E. r e. ZZ E. q e. ZZ ( 0 <_ r /\ r < ( abs ` D ) /\ N = ( ( q x. D ) + r ) ) )
Theorem	divalglemeuneg 12067*	Lemma for divalg 12068. Uniqueness for a negative denominator. (Contributed by Jim Kingdon, 4-Dec-2021.)
|- ( ( N e. ZZ /\ D e. ZZ /\ D < 0 ) -> E! r e. ZZ E. q e. ZZ ( 0 <_ r /\ r < ( abs ` D ) /\ N = ( ( q x. D ) + r ) ) )
Theorem	divalg 12068*	The division algorithm (theorem). Dividing an integer N by a nonzero integer D produces a (unique) quotient q and a unique remainder 0 <_ r < ( abs ` D ). Theorem 1.14 in [ApostolNT] p. 19. (Contributed by Paul Chapman, 21-Mar-2011.)
|- ( ( N e. ZZ /\ D e. ZZ /\ D =/= 0 ) -> E! r e. ZZ E. q e. ZZ ( 0 <_ r /\ r < ( abs ` D ) /\ N = ( ( q x. D ) + r ) ) )
Theorem	divalgb 12069*	Express the division algorithm as stated in divalg 12068 in terms of ||. (Contributed by Paul Chapman, 31-Mar-2011.)
|- ( ( N e. ZZ /\ D e. ZZ /\ D =/= 0 ) -> ( E! r e. ZZ E. q e. ZZ ( 0 <_ r /\ r < ( abs ` D ) /\ N = ( ( q x. D ) + r ) ) <-> E! r e. NN0 ( r < ( abs ` D ) /\ D || ( N - r ) ) ) )
Theorem	divalg2 12070*	The division algorithm (theorem) for a positive divisor. (Contributed by Paul Chapman, 21-Mar-2011.)
|- ( ( N e. ZZ /\ D e. NN ) -> E! r e. NN0 ( r < D /\ D || ( N - r ) ) )
Theorem	divalgmod 12071	The result of the mod operator satisfies the requirements for the remainder R in the division algorithm for a positive divisor (compare divalg2 12070 and divalgb 12069). This demonstration theorem justifies the use of mod to yield an explicit remainder from this point forward. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by AV, 21-Aug-2021.)
|- ( ( N e. ZZ /\ D e. NN ) -> ( R = ( N mod D ) <-> ( R e. NN0 /\ ( R < D /\ D || ( N - R ) ) ) ) )
Theorem	divalgmodcl 12072	The result of the mod operator satisfies the requirements for the remainder R in the division algorithm for a positive divisor. Variant of divalgmod 12071. (Contributed by Stefan O'Rear, 17-Oct-2014.) (Proof shortened by AV, 21-Aug-2021.)
|- ( ( N e. ZZ /\ D e. NN /\ R e. NN0 ) -> ( R = ( N mod D ) <-> ( R < D /\ D || ( N - R ) ) ) )
Theorem	modremain 12073*	The result of the modulo operation is the remainder of the division algorithm. (Contributed by AV, 19-Aug-2021.)
|- ( ( N e. ZZ /\ D e. NN /\ ( R e. NN0 /\ R < D ) ) -> ( ( N mod D ) = R <-> E. z e. ZZ ( ( z x. D ) + R ) = N ) )
Theorem	ndvdssub 12074	Corollary of the division algorithm. If an integer D greater than 1 divides N, then it does not divide any of N - 1, N - 2... N - ( D - 1 ). (Contributed by Paul Chapman, 31-Mar-2011.)
|- ( ( N e. ZZ /\ D e. NN /\ ( K e. NN /\ K < D ) ) -> ( D || N -> -. D || ( N - K ) ) )
Theorem	ndvdsadd 12075	Corollary of the division algorithm. If an integer D greater than 1 divides N, then it does not divide any of N + 1, N + 2... N + ( D - 1 ). (Contributed by Paul Chapman, 31-Mar-2011.)
|- ( ( N e. ZZ /\ D e. NN /\ ( K e. NN /\ K < D ) ) -> ( D || N -> -. D || ( N + K ) ) )
Theorem	ndvdsp1 12076	Special case of ndvdsadd 12075. If an integer D greater than 1 divides N, it does not divide N + 1. (Contributed by Paul Chapman, 31-Mar-2011.)
|- ( ( N e. ZZ /\ D e. NN /\ 1 < D ) -> ( D || N -> -. D || ( N + 1 ) ) )
Theorem	ndvdsi 12077	A quick test for non-divisibility. (Contributed by Mario Carneiro, 18-Feb-2014.)
|- A e. NN   &    |- Q e. NN0   &    |- R e. NN   &    |- ( ( A x. Q ) + R ) = B   &    |- R < A   =>    |- -. A || B
Theorem	flodddiv4 12078	The floor of an odd integer divided by 4. (Contributed by AV, 17-Jun-2021.)
|- ( ( M e. ZZ /\ N = ( ( 2 x. M ) + 1 ) ) -> ( |_ ` ( N / 4 ) ) = if ( 2 || M , ( M / 2 ) , ( ( M - 1 ) / 2 ) ) )
Theorem	fldivndvdslt 12079	The floor of an integer divided by a nonzero integer not dividing the first integer is less than the integer divided by the positive integer. (Contributed by AV, 4-Jul-2021.)
|- ( ( K e. ZZ /\ ( L e. ZZ /\ L =/= 0 ) /\ -. L || K ) -> ( |_ ` ( K / L ) ) < ( K / L ) )
Theorem	flodddiv4lt 12080	The floor of an odd number divided by 4 is less than the odd number divided by 4. (Contributed by AV, 4-Jul-2021.)
|- ( ( N e. ZZ /\ -. 2 || N ) -> ( |_ ` ( N / 4 ) ) < ( N / 4 ) )
Theorem	flodddiv4t2lthalf 12081	The floor of an odd number divided by 4, multiplied by 2 is less than the half of the odd number. (Contributed by AV, 4-Jul-2021.)
|- ( ( N e. ZZ /\ -. 2 || N ) -> ( ( |_ ` ( N / 4 ) ) x. 2 ) < ( N / 2 ) )
5.1.4  The greatest common divisor operator
Syntax	cgcd 12082	Extend the definition of a class to include the greatest common divisor operator.
class gcd
Definition	df-gcd 12083*	Define the gcd operator. For example, ( -u 6 gcd 9 ) = 3 (ex-gcd 15293). (Contributed by Paul Chapman, 21-Mar-2011.)
|- gcd = ( x e. ZZ , y e. ZZ |-> if ( ( x = 0 /\ y = 0 ) , 0 , sup ( { n e. ZZ | ( n || x /\ n || y ) } , RR , < ) ) )
Theorem	gcdmndc 12084	Decidablity lemma used in various proofs related to gcd. (Contributed by Jim Kingdon, 12-Dec-2021.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> DECID ( M = 0 /\ N = 0 ) )
Theorem	zsupcllemstep 12085*	Lemma for zsupcl 12087. Induction step. (Contributed by Jim Kingdon, 7-Dec-2021.)
|- ( ( ph /\ n e. ( ZZ>= ` M ) ) -> DECID ps )   =>    |- ( K e. ( ZZ>= ` M ) -> ( ( ( ph /\ A. n e. ( ZZ>= ` K ) -. ps ) -> E. x e. ZZ ( A. y e. { n e. ZZ | ps } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ps } y < z ) ) ) -> ( ( ph /\ A. n e. ( ZZ>= ` ( K + 1 ) ) -. ps ) -> E. x e. ZZ ( A. y e. { n e. ZZ | ps } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ps } y < z ) ) ) ) )
Theorem	zsupcllemex 12086*	Lemma for zsupcl 12087. Existence of the supremum. (Contributed by Jim Kingdon, 7-Dec-2021.)
|- ( ph -> M e. ZZ )   &    |- ( n = M -> ( ps <-> ch ) )   &    |- ( ph -> ch )   &    |- ( ( ph /\ n e. ( ZZ>= ` M ) ) -> DECID ps )   &    |- ( ph -> E. j e. ( ZZ>= ` M ) A. n e. ( ZZ>= ` j ) -. ps )   =>    |- ( ph -> E. x e. ZZ ( A. y e. { n e. ZZ | ps } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ps } y < z ) ) )
Theorem	zsupcl 12087*	Closure of supremum for decidable integer properties. The property which defines the set we are taking the supremum of must (a) be true at M (which corresponds to the nonempty condition of classical supremum theorems), (b) decidable at each value after M, and (c) be false after j (which corresponds to the upper bound condition found in classical supremum theorems). (Contributed by Jim Kingdon, 7-Dec-2021.)
|- ( ph -> M e. ZZ )   &    |- ( n = M -> ( ps <-> ch ) )   &    |- ( ph -> ch )   &    |- ( ( ph /\ n e. ( ZZ>= ` M ) ) -> DECID ps )   &    |- ( ph -> E. j e. ( ZZ>= ` M ) A. n e. ( ZZ>= ` j ) -. ps )   =>    |- ( ph -> sup ( { n e. ZZ | ps } , RR , < ) e. ( ZZ>= ` M ) )
Theorem	zssinfcl 12088*	The infimum of a set of integers is an element of the set. (Contributed by Jim Kingdon, 16-Jan-2022.)
|- ( ph -> E. x e. RR ( A. y e. B -. y < x /\ A. y e. RR ( x < y -> E. z e. B z < y ) ) )   &    |- ( ph -> B C_ ZZ )   &    |- ( ph -> inf ( B , RR , < ) e. ZZ )   =>    |- ( ph -> inf ( B , RR , < ) e. B )
Theorem	infssuzex 12089*	Existence of the infimum of a subset of an upper set of integers. (Contributed by Jim Kingdon, 13-Jan-2022.)
|- ( ph -> M e. ZZ )   &    |- S = { n e. ( ZZ>= ` M ) | ps }   &    |- ( ph -> A e. S )   &    |- ( ( ph /\ n e. ( M ... A ) ) -> DECID ps )   =>    |- ( ph -> E. x e. RR ( A. y e. S -. y < x /\ A. y e. RR ( x < y -> E. z e. S z < y ) ) )
Theorem	infssuzledc 12090*	The infimum of a subset of an upper set of integers is less than or equal to all members of the subset. (Contributed by Jim Kingdon, 13-Jan-2022.)
|- ( ph -> M e. ZZ )   &    |- S = { n e. ( ZZ>= ` M ) | ps }   &    |- ( ph -> A e. S )   &    |- ( ( ph /\ n e. ( M ... A ) ) -> DECID ps )   =>    |- ( ph -> inf ( S , RR , < ) <_ A )
Theorem	infssuzcldc 12091*	The infimum of a subset of an upper set of integers belongs to the subset. (Contributed by Jim Kingdon, 20-Jan-2022.)
|- ( ph -> M e. ZZ )   &    |- S = { n e. ( ZZ>= ` M ) | ps }   &    |- ( ph -> A e. S )   &    |- ( ( ph /\ n e. ( M ... A ) ) -> DECID ps )   =>    |- ( ph -> inf ( S , RR , < ) e. S )
Theorem	suprzubdc 12092*	The supremum of a bounded-above decidable set of integers is greater than any member of the set. (Contributed by Mario Carneiro, 21-Apr-2015.) (Revised by Jim Kingdon, 5-Oct-2024.)
|- ( ph -> A C_ ZZ )   &    |- ( ph -> A. x e. ZZ DECID x e. A )   &    |- ( ph -> E. x e. ZZ A. y e. A y <_ x )   &    |- ( ph -> B e. A )   =>    |- ( ph -> B <_ sup ( A , RR , < ) )
Theorem	nninfdcex 12093*	A decidable set of natural numbers has an infimum. (Contributed by Jim Kingdon, 28-Sep-2024.)
|- ( ph -> A C_ NN )   &    |- ( ph -> A. x e. NN DECID x e. A )   &    |- ( ph -> E. y y e. A )   =>    |- ( ph -> E. x e. RR ( A. y e. A -. y < x /\ A. y e. RR ( x < y -> E. z e. A z < y ) ) )
Theorem	zsupssdc 12094*	An inhabited decidable bounded subset of integers has a supremum in the set. (The proof does not use ax-pre-suploc 7995.) (Contributed by Mario Carneiro, 21-Apr-2015.) (Revised by Jim Kingdon, 5-Oct-2024.)
|- ( ph -> A C_ ZZ )   &    |- ( ph -> E. x x e. A )   &    |- ( ph -> A. x e. ZZ DECID x e. A )   &    |- ( ph -> E. x e. ZZ A. y e. A y <_ x )   =>    |- ( ph -> E. x e. A ( A. y e. A -. x < y /\ A. y e. B ( y < x -> E. z e. A y < z ) ) )
Theorem	suprzcl2dc 12095*	The supremum of a bounded-above decidable set of integers is a member of the set. (This theorem avoids ax-pre-suploc 7995.) (Contributed by Mario Carneiro, 21-Apr-2015.) (Revised by Jim Kingdon, 6-Oct-2024.)
|- ( ph -> A C_ ZZ )   &    |- ( ph -> A. x e. ZZ DECID x e. A )   &    |- ( ph -> E. x e. ZZ A. y e. A y <_ x )   &    |- ( ph -> E. x x e. A )   =>    |- ( ph -> sup ( A , RR , < ) e. A )
Theorem	dvdsbnd 12096*	There is an upper bound to the divisors of a nonzero integer. (Contributed by Jim Kingdon, 11-Dec-2021.)
|- ( ( A e. ZZ /\ A =/= 0 ) -> E. n e. NN A. m e. ( ZZ>= ` n ) -. m || A )
Theorem	gcdsupex 12097*	Existence of the supremum used in defining gcd. (Contributed by Jim Kingdon, 12-Dec-2021.)
|- ( ( ( X e. ZZ /\ Y e. ZZ ) /\ -. ( X = 0 /\ Y = 0 ) ) -> E. x e. ZZ ( A. y e. { n e. ZZ | ( n || X /\ n || Y ) } -. x < y /\ A. y e. RR ( y < x -> E. z e. { n e. ZZ | ( n || X /\ n || Y ) } y < z ) ) )
Theorem	gcdsupcl 12098*	Closure of the supremum used in defining gcd. A lemma for gcdval 12099 and gcdn0cl 12102. (Contributed by Jim Kingdon, 11-Dec-2021.)
|- ( ( ( X e. ZZ /\ Y e. ZZ ) /\ -. ( X = 0 /\ Y = 0 ) ) -> sup ( { n e. ZZ | ( n || X /\ n || Y ) } , RR , < ) e. NN )
Theorem	gcdval 12099*	The value of the gcd operator. ( M gcd N ) is the greatest common divisor of M and N. If M and N are both 0, the result is defined conventionally as 0. (Contributed by Paul Chapman, 21-Mar-2011.) (Revised by Mario Carneiro, 10-Nov-2013.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M gcd N ) = if ( ( M = 0 /\ N = 0 ) , 0 , sup ( { n e. ZZ | ( n || M /\ n || N ) } , RR , < ) ) )
Theorem	gcd0val 12100	The value, by convention, of the gcd operator when both operands are 0. (Contributed by Paul Chapman, 21-Mar-2011.)
|- ( 0 gcd 0 ) = 0