HomeHome Intuitionistic Logic Explorer
Theorem List (p. 120 of 153)
< Previous  Next >
Browser slow? Try the
Unicode version.

Mirrors  >  Metamath Home Page  >  ILE Home Page  >  Theorem List Contents  >  Recent Proofs       This page: Page List

Theorem List for Intuitionistic Logic Explorer - 11901-12000   *Has distinct variable group(s)
TypeLabelDescription
Statement
 
Theoremmulmoddvds 11901 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 ) )
 
Theorem3dvdsdec 11902 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 )
 )
 
Theorem3dvds2dec 11903 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 11907. 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 11904) 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 9384, zeo 9388, zeo2 9389, etc. use different representations, which are equivalent with the representations using the divides relation, see evend2 11926 and oddp1d2 11927. The corresponding theorems are zeneo 11908, zeo3 11905 and zeo4 11907.

 
Theoremevenelz 11904 An even number is an integer. This follows immediately from the reverse closure of the divides relation, see dvdszrcl 11831. (Contributed by AV, 22-Jun-2021.)
 |-  ( 2  ||  N  ->  N  e.  ZZ )
 
Theoremzeo3 11905 An integer is even or odd. (Contributed by AV, 17-Jun-2021.)
 |-  ( N  e.  ZZ  ->  ( 2  ||  N  \/  -.  2  ||  N ) )
 
Theoremzeoxor 11906 An integer is even or odd but not both. (Contributed by Jim Kingdon, 10-Nov-2021.)
 |-  ( N  e.  ZZ  ->  ( 2  ||  N  \/_  -.  2  ||  N ) )
 
Theoremzeo4 11907 An integer is even or odd but not both. (Contributed by AV, 17-Jun-2021.)
 |-  ( N  e.  ZZ  ->  ( 2  ||  N  <->  -. 
 -.  2  ||  N ) )
 
Theoremzeneo 11908 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 9384 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 ) )
 
Theoremodd2np1lem 11909* Lemma for odd2np1 11910. (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 ) )
 
Theoremodd2np1 11910* 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 ) )
 
Theoremeven2n 11911* 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 )
 
Theoremoddm1even 11912 An integer is odd iff its predecessor is even. (Contributed by Mario Carneiro, 5-Sep-2016.)
 |-  ( N  e.  ZZ  ->  ( -.  2  ||  N 
 <->  2  ||  ( N  -  1 ) ) )
 
Theoremoddp1even 11913 An integer is odd iff its successor is even. (Contributed by Mario Carneiro, 5-Sep-2016.)
 |-  ( N  e.  ZZ  ->  ( -.  2  ||  N 
 <->  2  ||  ( N  +  1 ) ) )
 
Theoremoexpneg 11914 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 ) )
 
Theoremmod2eq0even 11915 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 ) )
 
Theoremmod2eq1n2dvds 11916 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 )
 )
 
Theoremoddnn02np1 11917* 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 ) )
 
Theoremoddge22np1 11918* 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 ) )
 
Theoremevennn02n 11919* 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 ) )
 
Theoremevennn2n 11920* 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 ) )
 
Theorem2tp1odd 11921 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 )
 
Theoremmulsucdiv2z 11922 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 )
 
Theoremsqoddm1div8z 11923 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 )
 
Theorem2teven 11924 A number which is twice an integer is even. (Contributed by AV, 16-Jul-2021.)
 |-  ( ( A  e.  ZZ  /\  B  =  ( 2  x.  A ) )  ->  2  ||  B )
 
Theoremzeo5 11925 An integer is either even or odd, version of zeo3 11905 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 ) ) )
 
Theoremevend2 11926 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 9388 and zeo2 9389. (Contributed by AV, 22-Jun-2021.)
 |-  ( N  e.  ZZ  ->  ( 2  ||  N  <->  ( N  /  2 )  e.  ZZ ) )
 
Theoremoddp1d2 11927 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 9388 and zeo2 9389. (Contributed by AV, 22-Jun-2021.)
 |-  ( N  e.  ZZ  ->  ( -.  2  ||  N 
 <->  ( ( N  +  1 )  /  2
 )  e.  ZZ )
 )
 
Theoremzob 11928 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 ) )
 
Theoremoddm1d2 11929 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 )
 )
 
Theoremltoddhalfle 11930 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 ) ) )
 
Theoremhalfleoddlt 11931 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 )
 )
 
Theoremopoe 11932 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 ) )
 
Theoremomoe 11933 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 ) )
 
Theoremopeo 11934 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 ) )
 
Theoremomeo 11935 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 ) )
 
Theoremm1expe 11936 Exponentiation of -1 by an even power. Variant of m1expeven 10598. (Contributed by AV, 25-Jun-2021.)
 |-  ( 2  ||  N  ->  ( -u 1 ^ N )  =  1 )
 
Theoremm1expo 11937 Exponentiation of -1 by an odd power. (Contributed by AV, 26-Jun-2021.)
 |-  ( ( N  e.  ZZ  /\  -.  2  ||  N )  ->  ( -u 1 ^ N )  =  -u 1 )
 
Theoremm1exp1 11938 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 )
 )
 
Theoremnn0enne 11939 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 ) )
 
Theoremnn0ehalf 11940 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 )
 
Theoremnnehalf 11941 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 )
 
Theoremnn0o1gt2 11942 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 ) )
 
Theoremnno 11943 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 )
 
Theoremnn0o 11944 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 )
 
Theoremnn0ob 11945 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 ) )
 
Theoremnn0oddm1d2 11946 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 ) )
 
Theoremnnoddm1d2 11947 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 )
 )
 
Theoremz0even 11948 0 is even. (Contributed by AV, 11-Feb-2020.) (Revised by AV, 23-Jun-2021.)
 |-  2  ||  0
 
Theoremn2dvds1 11949 2 does not divide 1 (common case). That means 1 is odd. (Contributed by David A. Wheeler, 8-Dec-2018.)
 |- 
 -.  2  ||  1
 
Theoremn2dvdsm1 11950 2 does not divide -1. That means -1 is odd. (Contributed by AV, 15-Aug-2021.)
 |- 
 -.  2  ||  -u 1
 
Theoremz2even 11951 2 is even. (Contributed by AV, 12-Feb-2020.) (Revised by AV, 23-Jun-2021.)
 |-  2  ||  2
 
Theoremn2dvds3 11952 2 does not divide 3, i.e. 3 is an odd number. (Contributed by AV, 28-Feb-2021.)
 |- 
 -.  2  ||  3
 
Theoremz4even 11953 4 is an even number. (Contributed by AV, 23-Jul-2020.) (Revised by AV, 4-Jul-2021.)
 |-  2  ||  4
 
Theorem4dvdseven 11954 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
 
Theoremdivalglemnn 11955* Lemma for divalg 11961. 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 )
 ) )
 
Theoremdivalglemqt 11956 Lemma for divalg 11961. 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 )
 
Theoremdivalglemnqt 11957 Lemma for divalg 11961. 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 )
 
Theoremdivalglemeunn 11958* Lemma for divalg 11961. 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
 ) ) )
 
Theoremdivalglemex 11959* Lemma for divalg 11961. 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 )
 ) )
 
Theoremdivalglemeuneg 11960* Lemma for divalg 11961. 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 )
 ) )
 
Theoremdivalg 11961* 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 )
 ) )
 
Theoremdivalgb 11962* Express the division algorithm as stated in divalg 11961 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
 ) ) ) )
 
Theoremdivalg2 11963* 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 ) ) )
 
Theoremdivalgmod 11964 The result of the  mod operator satisfies the requirements for the remainder  R in the division algorithm for a positive divisor (compare divalg2 11963 and divalgb 11962). 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 ) ) ) ) )
 
Theoremdivalgmodcl 11965 The result of the  mod operator satisfies the requirements for the remainder  R in the division algorithm for a positive divisor. Variant of divalgmod 11964. (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 ) ) ) )
 
Theoremmodremain 11966* 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 )
 )
 
Theoremndvdssub 11967 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 ) ) )
 
Theoremndvdsadd 11968 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 ) ) )
 
Theoremndvdsp1 11969 Special case of ndvdsadd 11968. 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 )
 ) )
 
Theoremndvdsi 11970 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
 
Theoremflodddiv4 11971 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 ) ) )
 
Theoremfldivndvdslt 11972 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 ) )
 
Theoremflodddiv4lt 11973 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 ) )
 
Theoremflodddiv4t2lthalf 11974 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
 
Syntaxcgcd 11975 Extend the definition of a class to include the greatest common divisor operator.
 class  gcd
 
Definitiondf-gcd 11976* Define the  gcd operator. For example,  ( -u 6  gcd  9 )  =  3 (ex-gcd 14944). (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 ,  <  ) ) )
 
Theoremgcdmndc 11977 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 ) )
 
Theoremzsupcllemstep 11978* Lemma for zsupcl 11980. 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 )
 ) ) ) )
 
Theoremzsupcllemex 11979* Lemma for zsupcl 11980. 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 ) ) )
 
Theoremzsupcl 11980* 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 ) )
 
Theoremzssinfcl 11981* 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 )
 
Theoreminfssuzex 11982* 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
 ) ) )
 
Theoreminfssuzledc 11983* 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 )
 
Theoreminfssuzcldc 11984* 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 )
 
Theoremsuprzubdc 11985* 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 ,  <  ) )
 
Theoremnninfdcex 11986* 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
 ) ) )
 
Theoremzsupssdc 11987* An inhabited decidable bounded subset of integers has a supremum in the set. (The proof does not use ax-pre-suploc 7962.) (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
 ) ) )
 
Theoremsuprzcl2dc 11988* The supremum of a bounded-above decidable set of integers is a member of the set. (This theorem avoids ax-pre-suploc 7962.) (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 )
 
Theoremdvdsbnd 11989* 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 )
 
Theoremgcdsupex 11990* 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
 ) ) )
 
Theoremgcdsupcl 11991* Closure of the supremum used in defining  gcd. A lemma for gcdval 11992 and gcdn0cl 11995. (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 )
 
Theoremgcdval 11992* 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 ,  <  ) ) )
 
Theoremgcd0val 11993 The value, by convention, of the 
gcd operator when both operands are 0. (Contributed by Paul Chapman, 21-Mar-2011.)
 |-  ( 0  gcd  0
 )  =  0
 
Theoremgcdn0val 11994* The value of the  gcd operator when at least one operand is nonzero. (Contributed by Paul Chapman, 21-Mar-2011.)
 |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  /\  N  =  0 ) )  ->  ( M  gcd  N )  =  sup ( { n  e.  ZZ  |  ( n  ||  M  /\  n  ||  N ) } ,  RR ,  <  ) )
 
Theoremgcdn0cl 11995 Closure of the  gcd operator. (Contributed by Paul Chapman, 21-Mar-2011.)
 |-  ( ( ( M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  /\  N  =  0 ) )  ->  ( M  gcd  N )  e.  NN )
 
Theoremgcddvds 11996 The gcd of two integers divides each of them. (Contributed by Paul Chapman, 21-Mar-2011.)
 |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( ( M 
 gcd  N )  ||  M  /\  ( M  gcd  N )  ||  N ) )
 
Theoremdvdslegcd 11997 An integer which divides both operands of the  gcd operator is bounded by it. (Contributed by Paul Chapman, 21-Mar-2011.)
 |-  ( ( ( K  e.  ZZ  /\  M  e.  ZZ  /\  N  e.  ZZ )  /\  -.  ( M  =  0  /\  N  =  0 )
 )  ->  ( ( K  ||  M  /\  K  ||  N )  ->  K  <_  ( M  gcd  N ) ) )
 
Theoremnndvdslegcd 11998 A positive integer which divides both positive operands of the  gcd operator is bounded by it. (Contributed by AV, 9-Aug-2020.)
 |-  ( ( K  e.  NN  /\  M  e.  NN  /\  N  e.  NN )  ->  ( ( K  ||  M  /\  K  ||  N )  ->  K  <_  ( M  gcd  N ) ) )
 
Theoremgcdcl 11999 Closure of the  gcd operator. (Contributed by Paul Chapman, 21-Mar-2011.)
 |-  ( ( M  e.  ZZ  /\  N  e.  ZZ )  ->  ( M  gcd  N )  e.  NN0 )
 
Theoremgcdnncl 12000 Closure of the  gcd operator. (Contributed by Thierry Arnoux, 2-Feb-2020.)
 |-  ( ( M  e.  NN  /\  N  e.  NN )  ->  ( M  gcd  N )  e.  NN )
    < Previous  Next >

Page List
Jump to page: Contents  1 1-100 2 101-200 3 201-300 4 301-400 5 401-500 6 501-600 7 601-700 8 701-800 9 801-900 10 901-1000 11 1001-1100 12 1101-1200 13 1201-1300 14 1301-1400 15 1401-1500 16 1501-1600 17 1601-1700 18 1701-1800 19 1801-1900 20 1901-2000 21 2001-2100 22 2101-2200 23 2201-2300 24 2301-2400 25 2401-2500 26 2501-2600 27 2601-2700 28 2701-2800 29 2801-2900 30 2901-3000 31 3001-3100 32 3101-3200 33 3201-3300 34 3301-3400 35 3401-3500 36 3501-3600 37 3601-3700 38 3701-3800 39 3801-3900 40 3901-4000 41 4001-4100 42 4101-4200 43 4201-4300 44 4301-4400 45 4401-4500 46 4501-4600 47 4601-4700 48 4701-4800 49 4801-4900 50 4901-5000 51 5001-5100 52 5101-5200 53 5201-5300 54 5301-5400 55 5401-5500 56 5501-5600 57 5601-5700 58 5701-5800 59 5801-5900 60 5901-6000 61 6001-6100 62 6101-6200 63 6201-6300 64 6301-6400 65 6401-6500 66 6501-6600 67 6601-6700 68 6701-6800 69 6801-6900 70 6901-7000 71 7001-7100 72 7101-7200 73 7201-7300 74 7301-7400 75 7401-7500 76 7501-7600 77 7601-7700 78 7701-7800 79 7801-7900 80 7901-8000 81 8001-8100 82 8101-8200 83 8201-8300 84 8301-8400 85 8401-8500 86 8501-8600 87 8601-8700 88 8701-8800 89 8801-8900 90 8901-9000 91 9001-9100 92 9101-9200 93 9201-9300 94 9301-9400 95 9401-9500 96 9501-9600 97 9601-9700 98 9701-9800 99 9801-9900 100 9901-10000 101 10001-10100 102 10101-10200 103 10201-10300 104 10301-10400 105 10401-10500 106 10501-10600 107 10601-10700 108 10701-10800 109 10801-10900 110 10901-11000 111 11001-11100 112 11101-11200 113 11201-11300 114 11301-11400 115 11401-11500 116 11501-11600 117 11601-11700 118 11701-11800 119 11801-11900 120 11901-12000 121 12001-12100 122 12101-12200 123 12201-12300 124 12301-12400 125 12401-12500 126 12501-12600 127 12601-12700 128 12701-12800 129 12801-12900 130 12901-13000 131 13001-13100 132 13101-13200 133 13201-13300 134 13301-13400 135 13401-13500 136 13501-13600 137 13601-13700 138 13701-13800 139 13801-13900 140 13901-14000 141 14001-14100 142 14101-14200 143 14201-14300 144 14301-14400 145 14401-14500 146 14501-14600 147 14601-14700 148 14701-14800 149 14801-14900 150 14901-15000 151 15001-15100 152 15101-15200 153 15201-15294
  Copyright terms: Public domain < Previous  Next >