P. 119 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 11801-11900   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	dvdssubr 11801	An integer divides another iff it divides their difference. (Contributed by Paul Chapman, 31-Mar-2011.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M || N <-> M || ( N - M ) ) )
Theorem	dvdsadd2b 11802	Adding a multiple of the base does not affect divisibility. (Contributed by Stefan O'Rear, 23-Sep-2014.)
|- ( ( A e. ZZ /\ B e. ZZ /\ ( C e. ZZ /\ A || C ) ) -> ( A || B <-> A || ( C + B ) ) )
Theorem	dvdslelemd 11803	Lemma for dvdsle 11804. (Contributed by Jim Kingdon, 8-Nov-2021.)
|- ( ph -> M e. ZZ )   &    |- ( ph -> N e. NN )   &    |- ( ph -> K e. ZZ )   &    |- ( ph -> N < M )   =>    |- ( ph -> ( K x. M ) =/= N )
Theorem	dvdsle 11804	The divisors of a positive integer are bounded by it. The proof does not use /. (Contributed by Paul Chapman, 21-Mar-2011.)
|- ( ( M e. ZZ /\ N e. NN ) -> ( M || N -> M <_ N ) )
Theorem	dvdsleabs 11805	The divisors of a nonzero integer are bounded by its absolute value. Theorem 1.1(i) in [ApostolNT] p. 14 (comparison property of the divides relation). (Contributed by Paul Chapman, 21-Mar-2011.) (Proof shortened by Fan Zheng, 3-Jul-2016.)
|- ( ( M e. ZZ /\ N e. ZZ /\ N =/= 0 ) -> ( M || N -> M <_ ( abs ` N ) ) )
Theorem	dvdsleabs2 11806	Transfer divisibility to an order constraint on absolute values. (Contributed by Stefan O'Rear, 24-Sep-2014.)
|- ( ( M e. ZZ /\ N e. ZZ /\ N =/= 0 ) -> ( M || N -> ( abs ` M ) <_ ( abs ` N ) ) )
Theorem	dvdsabseq 11807	If two integers divide each other, they must be equal, up to a difference in sign. Theorem 1.1(j) in [ApostolNT] p. 14. (Contributed by Mario Carneiro, 30-May-2014.) (Revised by AV, 7-Aug-2021.)
|- ( ( M || N /\ N || M ) -> ( abs ` M ) = ( abs ` N ) )
Theorem	dvdseq 11808	If two nonnegative integers divide each other, they must be equal. (Contributed by Mario Carneiro, 30-May-2014.) (Proof shortened by AV, 7-Aug-2021.)
|- ( ( ( M e. NN0 /\ N e. NN0 ) /\ ( M || N /\ N || M ) ) -> M = N )
Theorem	divconjdvds 11809	If a nonzero integer M divides another integer N, the other integer N divided by the nonzero integer M (i.e. the divisor conjugate of N to M) divides the other integer N. Theorem 1.1(k) in [ApostolNT] p. 14. (Contributed by AV, 7-Aug-2021.)
|- ( ( M || N /\ M =/= 0 ) -> ( N / M ) || N )
Theorem	dvdsdivcl 11810*	The complement of a divisor of N is also a divisor of N. (Contributed by Mario Carneiro, 2-Jul-2015.) (Proof shortened by AV, 9-Aug-2021.)
|- ( ( N e. NN /\ A e. { x e. NN | x || N } ) -> ( N / A ) e. { x e. NN | x || N } )
Theorem	dvdsflip 11811*	An involution of the divisors of a number. (Contributed by Stefan O'Rear, 12-Sep-2015.) (Proof shortened by Mario Carneiro, 13-May-2016.)
|- A = { x e. NN | x || N }   &    |- F = ( y e. A |-> ( N / y ) )   =>    |- ( N e. NN -> F : A -1-1-onto-> A )
Theorem	dvdsssfz1 11812*	The set of divisors of a number is a subset of a finite set. (Contributed by Mario Carneiro, 22-Sep-2014.)
|- ( A e. NN -> { p e. NN | p || A } C_ ( 1 ... A ) )
Theorem	dvds1 11813	The only nonnegative integer that divides 1 is 1. (Contributed by Mario Carneiro, 2-Jul-2015.)
|- ( M e. NN0 -> ( M || 1 <-> M = 1 ) )
Theorem	alzdvds 11814*	Only 0 is divisible by all integers. (Contributed by Paul Chapman, 21-Mar-2011.)
|- ( N e. ZZ -> ( A. x e. ZZ x || N <-> N = 0 ) )
Theorem	dvdsext 11815*	Poset extensionality for division. (Contributed by Stefan O'Rear, 6-Sep-2015.)
|- ( ( A e. NN0 /\ B e. NN0 ) -> ( A = B <-> A. x e. NN0 ( A || x <-> B || x ) ) )
Theorem	fzm1ndvds 11816	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 11817	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 11818	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 11819	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 10354 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 11820	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 11821	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 11822	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 11823	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 11824	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 11825	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 11829. 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 11826) 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 9313, zeo 9317, zeo2 9318, etc. use different representations, which are equivalent with the representations using the divides relation, see evend2 11848 and oddp1d2 11849. The corresponding theorems are zeneo 11830, zeo3 11827 and zeo4 11829.
Theorem	evenelz 11826	An even number is an integer. This follows immediately from the reverse closure of the divides relation, see dvdszrcl 11754. (Contributed by AV, 22-Jun-2021.)
|- ( 2 || N -> N e. ZZ )
Theorem	zeo3 11827	An integer is even or odd. (Contributed by AV, 17-Jun-2021.)
|- ( N e. ZZ -> ( 2 || N \/ -. 2 || N ) )
Theorem	zeoxor 11828	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 11829	An integer is even or odd but not both. (Contributed by AV, 17-Jun-2021.)
|- ( N e. ZZ -> ( 2 || N <-> -. -. 2 || N ) )
Theorem	zeneo 11830	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 9313 follows immediately from the fact that a contradiction implies anything, see pm2.21i 641. (Contributed by AV, 22-Jun-2021.)
|- ( ( A e. ZZ /\ B e. ZZ ) -> ( ( 2 || A /\ -. 2 || B ) -> A =/= B ) )
Theorem	odd2np1lem 11831*	Lemma for odd2np1 11832. (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 11832*	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 11833*	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 11834	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 11835	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 11836	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 11837	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 11838	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 11839*	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 11840*	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 11841*	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 11842*	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 11843	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 11844	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 11845	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 11846	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 11847	An integer is either even or odd, version of zeo3 11827 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 11848	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 9317 and zeo2 9318. (Contributed by AV, 22-Jun-2021.)
|- ( N e. ZZ -> ( 2 || N <-> ( N / 2 ) e. ZZ ) )
Theorem	oddp1d2 11849	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 9317 and zeo2 9318. (Contributed by AV, 22-Jun-2021.)
|- ( N e. ZZ -> ( -. 2 || N <-> ( ( N + 1 ) / 2 ) e. ZZ ) )
Theorem	zob 11850	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 11851	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 11852	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 11853	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 11854	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 11855	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 11856	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 11857	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 11858	Exponentiation of -1 by an even power. Variant of m1expeven 10523. (Contributed by AV, 25-Jun-2021.)
|- ( 2 || N -> ( -u 1 ^ N ) = 1 )
Theorem	m1expo 11859	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 11860	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 11861	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 11862	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 11863	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 11864	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 11865	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 11866	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 11867	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 11868	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 11869	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 11870	0 is even. (Contributed by AV, 11-Feb-2020.) (Revised by AV, 23-Jun-2021.)
|- 2 || 0
Theorem	n2dvds1 11871	2 does not divide 1 (common case). That means 1 is odd. (Contributed by David A. Wheeler, 8-Dec-2018.)
|- -. 2 || 1
Theorem	n2dvdsm1 11872	2 does not divide -1. That means -1 is odd. (Contributed by AV, 15-Aug-2021.)
|- -. 2 || -u 1
Theorem	z2even 11873	2 is even. (Contributed by AV, 12-Feb-2020.) (Revised by AV, 23-Jun-2021.)
|- 2 || 2
Theorem	n2dvds3 11874	2 does not divide 3, i.e. 3 is an odd number. (Contributed by AV, 28-Feb-2021.)
|- -. 2 || 3
Theorem	z4even 11875	4 is an even number. (Contributed by AV, 23-Jul-2020.) (Revised by AV, 4-Jul-2021.)
|- 2 || 4
Theorem	4dvdseven 11876	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 11877*	Lemma for divalg 11883. 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 11878	Lemma for divalg 11883. 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 11879	Lemma for divalg 11883. 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 11880*	Lemma for divalg 11883. 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 11881*	Lemma for divalg 11883. 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 11882*	Lemma for divalg 11883. 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 11883*	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 11884*	Express the division algorithm as stated in divalg 11883 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 11885*	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 11886	The result of the mod operator satisfies the requirements for the remainder R in the division algorithm for a positive divisor (compare divalg2 11885 and divalgb 11884). 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 11887	The result of the mod operator satisfies the requirements for the remainder R in the division algorithm for a positive divisor. Variant of divalgmod 11886. (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 11888*	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 11889	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 11890	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 11891	Special case of ndvdsadd 11890. 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 11892	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 11893	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 11894	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 11895	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 11896	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 11897	Extend the definition of a class to include the greatest common divisor operator.
class gcd
Definition	df-gcd 11898*	Define the gcd operator. For example, ( -u 6 gcd 9 ) = 3 (ex-gcd 13766). (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 11899	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 11900*	Lemma for zsupcl 11902. 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 ) ) ) ) )