P. 123 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 12201-12300   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	lcmval 12201*	Value of the lcm operator. ( M lcm N ) is the least common multiple of M and N. If either M or N is 0, the result is defined conventionally as 0. Contrast with df-gcd 12080 and gcdval 12096. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 16-Sep-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M lcm N ) = if ( ( M = 0 \/ N = 0 ) , 0 , inf ( { n e. NN | ( M || n /\ N || n ) } , RR , < ) ) )
Theorem	lcmcom 12202	The lcm operator is commutative. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M lcm N ) = ( N lcm M ) )
Theorem	lcm0val 12203	The value, by convention, of the lcm operator when either operand is 0. (Use lcmcom 12202 for a left-hand 0.) (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
|- ( M e. ZZ -> ( M lcm 0 ) = 0 )
Theorem	lcmn0val 12204*	The value of the lcm operator when both operands are nonzero. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 16-Sep-2020.)
|- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 \/ N = 0 ) ) -> ( M lcm N ) = inf ( { n e. NN | ( M || n /\ N || n ) } , RR , < ) )
Theorem	lcmcllem 12205*	Lemma for lcmn0cl 12206 and dvdslcm 12207. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
|- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 \/ N = 0 ) ) -> ( M lcm N ) e. { n e. NN | ( M || n /\ N || n ) } )
Theorem	lcmn0cl 12206	Closure of the lcm operator. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( ( M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 \/ N = 0 ) ) -> ( M lcm N ) e. NN )
Theorem	dvdslcm 12207	The lcm of two integers is divisible by each of them. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M || ( M lcm N ) /\ N || ( M lcm N ) ) )
Theorem	lcmledvds 12208	A positive integer which both operands of the lcm operator divide bounds it. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
|- ( ( ( K e. NN /\ M e. ZZ /\ N e. ZZ ) /\ -. ( M = 0 \/ N = 0 ) ) -> ( ( M || K /\ N || K ) -> ( M lcm N ) <_ K ) )
Theorem	lcmeq0 12209	The lcm of two integers is zero iff either is zero. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( M lcm N ) = 0 <-> ( M = 0 \/ N = 0 ) ) )
Theorem	lcmcl 12210	Closure of the lcm operator. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M lcm N ) e. NN0 )
Theorem	gcddvdslcm 12211	The greatest common divisor of two numbers divides their least common multiple. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M gcd N ) || ( M lcm N ) )
Theorem	lcmneg 12212	Negating one operand of the lcm operator does not alter the result. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M lcm -u N ) = ( M lcm N ) )
Theorem	neglcm 12213	Negating one operand of the lcm operator does not alter the result. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( -u M lcm N ) = ( M lcm N ) )
Theorem	lcmabs 12214	The lcm of two integers is the same as that of their absolute values. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( abs ` M ) lcm ( abs ` N ) ) = ( M lcm N ) )
Theorem	lcmgcdlem 12215	Lemma for lcmgcd 12216 and lcmdvds 12217. Prove them for positive M, N, and K. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
|- ( ( M e. NN /\ N e. NN ) -> ( ( ( M lcm N ) x. ( M gcd N ) ) = ( abs ` ( M x. N ) ) /\ ( ( K e. NN /\ ( M || K /\ N || K ) ) -> ( M lcm N ) || K ) ) )
Theorem	lcmgcd 12216	The product of two numbers' least common multiple and greatest common divisor is the absolute value of the product of the two numbers. In particular, that absolute value is the least common multiple of two coprime numbers, for which ( M gcd N ) = 1. Multiple methods exist for proving this, and it is often proven either as a consequence of the fundamental theorem of arithmetic or of Bézout's identity bezout 12148; see, e.g., https://proofwiki.org/wiki/Product_of_GCD_and_LCM 12148 and https://math.stackexchange.com/a/470827 12148. This proof uses the latter to first confirm it for positive integers M and N (the "Second Proof" in the above Stack Exchange page), then shows that implies it for all nonzero integer inputs, then finally uses lcm0val 12203 to show it applies when either or both inputs are zero. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( M lcm N ) x. ( M gcd N ) ) = ( abs ` ( M x. N ) ) )
Theorem	lcmdvds 12217	The lcm of two integers divides any integer the two divide. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) -> ( ( M || K /\ N || K ) -> ( M lcm N ) || K ) )
Theorem	lcmid 12218	The lcm of an integer and itself is its absolute value. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( M e. ZZ -> ( M lcm M ) = ( abs ` M ) )
Theorem	lcm1 12219	The lcm of an integer and 1 is the absolute value of the integer. (Contributed by AV, 23-Aug-2020.)
|- ( M e. ZZ -> ( M lcm 1 ) = ( abs ` M ) )
Theorem	lcmgcdnn 12220	The product of two positive integers' least common multiple and greatest common divisor is the product of the two integers. (Contributed by AV, 27-Aug-2020.)
|- ( ( M e. NN /\ N e. NN ) -> ( ( M lcm N ) x. ( M gcd N ) ) = ( M x. N ) )
Theorem	lcmgcdeq 12221	Two integers' absolute values are equal iff their least common multiple and greatest common divisor are equal. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( M e. ZZ /\ N e. ZZ ) -> ( ( M lcm N ) = ( M gcd N ) <-> ( abs ` M ) = ( abs ` N ) ) )
Theorem	lcmdvdsb 12222	Biconditional form of lcmdvds 12217. (Contributed by Steve Rodriguez, 20-Jan-2020.)
|- ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) -> ( ( M || K /\ N || K ) <-> ( M lcm N ) || K ) )
Theorem	lcmass 12223	Associative law for lcm operator. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
|- ( ( N e. ZZ /\ M e. ZZ /\ P e. ZZ ) -> ( ( N lcm M ) lcm P ) = ( N lcm ( M lcm P ) ) )
Theorem	3lcm2e6woprm 12224	The least common multiple of three and two is six. This proof does not use the property of 2 and 3 being prime. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 27-Aug-2020.)
|- ( 3 lcm 2 ) = 6
Theorem	6lcm4e12 12225	The least common multiple of six and four is twelve. (Contributed by AV, 27-Aug-2020.)
|- ( 6 lcm 4 ) = ; 1 2
5.1.10  Coprimality and Euclid's lemma According to Wikipedia "Coprime integers", see https://en.wikipedia.org/wiki/Coprime_integers (16-Aug-2020) "[...] two integers a and b are said to be relatively prime, mutually prime, or coprime [...] if the only positive integer (factor) that divides both of them is 1. Consequently, any prime number that divides one does not divide the other. This is equivalent to their greatest common divisor (gcd) being 1.". In the following, we use this equivalent characterization to say that A e. ZZ and B e. ZZ are coprime (or relatively prime) if ( A gcd B ) = 1. The equivalence of the definitions is shown by coprmgcdb 12226. The negation, i.e. two integers are not coprime, can be expressed either by ( A gcd B ) =/= 1, see ncoprmgcdne1b 12227, or equivalently by 1 < ( A gcd B ), see ncoprmgcdgt1b 12228. A proof of Euclid's lemma based on coprimality is provided in coprmdvds 12230 (as opposed to Euclid's lemma for primes).
Theorem	coprmgcdb 12226*	Two positive integers are coprime, i.e. the only positive integer that divides both of them is 1, iff their greatest common divisor is 1. (Contributed by AV, 9-Aug-2020.)
|- ( ( A e. NN /\ B e. NN ) -> ( A. i e. NN ( ( i || A /\ i || B ) -> i = 1 ) <-> ( A gcd B ) = 1 ) )
Theorem	ncoprmgcdne1b 12227*	Two positive integers are not coprime, i.e. there is an integer greater than 1 which divides both integers, iff their greatest common divisor is not 1. (Contributed by AV, 9-Aug-2020.)
|- ( ( A e. NN /\ B e. NN ) -> ( E. i e. ( ZZ>= ` 2 ) ( i || A /\ i || B ) <-> ( A gcd B ) =/= 1 ) )
Theorem	ncoprmgcdgt1b 12228*	Two positive integers are not coprime, i.e. there is an integer greater than 1 which divides both integers, iff their greatest common divisor is greater than 1. (Contributed by AV, 9-Aug-2020.)
|- ( ( A e. NN /\ B e. NN ) -> ( E. i e. ( ZZ>= ` 2 ) ( i || A /\ i || B ) <-> 1 < ( A gcd B ) ) )
Theorem	coprmdvds1 12229	If two positive integers are coprime, i.e. their greatest common divisor is 1, the only positive integer that divides both of them is 1. (Contributed by AV, 4-Aug-2021.)
|- ( ( F e. NN /\ G e. NN /\ ( F gcd G ) = 1 ) -> ( ( I e. NN /\ I || F /\ I || G ) -> I = 1 ) )
Theorem	coprmdvds 12230	Euclid's Lemma (see ProofWiki "Euclid's Lemma", 10-Jul-2021, https://proofwiki.org/wiki/Euclid's_Lemma): If an integer divides the product of two integers and is coprime to one of them, then it divides the other. See also theorem 1.5 in [ApostolNT] p. 16. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by AV, 10-Jul-2021.)
|- ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) -> ( ( K || ( M x. N ) /\ ( K gcd M ) = 1 ) -> K || N ) )
Theorem	coprmdvds2 12231	If an integer is divisible by two coprime integers, then it is divisible by their product. (Contributed by Mario Carneiro, 24-Feb-2014.)
|- ( ( ( M e. ZZ /\ N e. ZZ /\ K e. ZZ ) /\ ( M gcd N ) = 1 ) -> ( ( M || K /\ N || K ) -> ( M x. N ) || K ) )
Theorem	mulgcddvds 12232	One half of rpmulgcd2 12233, which does not need the coprimality assumption. (Contributed by Mario Carneiro, 2-Jul-2015.)
|- ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) -> ( K gcd ( M x. N ) ) || ( ( K gcd M ) x. ( K gcd N ) ) )
Theorem	rpmulgcd2 12233	If M is relatively prime to N, then the GCD of K with M x. N is the product of the GCDs with M and N respectively. (Contributed by Mario Carneiro, 2-Jul-2015.)
|- ( ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) /\ ( M gcd N ) = 1 ) -> ( K gcd ( M x. N ) ) = ( ( K gcd M ) x. ( K gcd N ) ) )
Theorem	qredeq 12234	Two equal reduced fractions have the same numerator and denominator. (Contributed by Jeff Hankins, 29-Sep-2013.)
|- ( ( ( M e. ZZ /\ N e. NN /\ ( M gcd N ) = 1 ) /\ ( P e. ZZ /\ Q e. NN /\ ( P gcd Q ) = 1 ) /\ ( M / N ) = ( P / Q ) ) -> ( M = P /\ N = Q ) )
Theorem	qredeu 12235*	Every rational number has a unique reduced form. (Contributed by Jeff Hankins, 29-Sep-2013.)
|- ( A e. QQ -> E! x e. ( ZZ X. NN ) ( ( ( 1st ` x ) gcd ( 2nd ` x ) ) = 1 /\ A = ( ( 1st ` x ) / ( 2nd ` x ) ) ) )
Theorem	rpmul 12236	If K is relatively prime to M and to N, it is also relatively prime to their product. (Contributed by Mario Carneiro, 24-Feb-2014.) (Proof shortened by Mario Carneiro, 2-Jul-2015.)
|- ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) -> ( ( ( K gcd M ) = 1 /\ ( K gcd N ) = 1 ) -> ( K gcd ( M x. N ) ) = 1 ) )
Theorem	rpdvds 12237	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.11  Cancellability of congruences
Theorem	congr 12238*	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 12239	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 12240*	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 12241	One direction of the bicondition in cncongr 12243. 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 12242	The other direction of the bicondition in cncongr 12243. (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 12243	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 12244	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 3745.
Syntax	cprime 12245	Extend the definition of a class to include the set of prime numbers.
class Prime
Definition	df-prm 12246*	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 12247*	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 12248	A prime number is a positive integer. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( P e. Prime -> P e. NN )
Theorem	prmz 12249	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 12250	The prime numbers are a subset of the positive integers. (Contributed by AV, 22-Jul-2020.)
|- Prime C_ NN
Theorem	prmex 12251	The set of prime numbers exists. (Contributed by AV, 22-Jul-2020.)
|- Prime e. _V
Theorem	1nprm 12252	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 12253*	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 12254*	Lemma for isprm2 12255. (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 12255*	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 12256*	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 12257*	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 12258*	A variation on prmind 12259 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 12259*	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 12260	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 12261	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 12262	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 12263	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 12264	A prime number is either 2 or odd. (Contributed by AV, 19-Jun-2021.)
|- ( P e. Prime -> ( P = 2 \/ -. 2 || P ) )
Theorem	2prm 12265	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 12266	3 is a prime number. (Contributed by Paul Chapman, 22-Jun-2011.)
|- 3 e. Prime
Theorem	4nprm 12267	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 12268	Primality is decidable. (Contributed by Jim Kingdon, 30-Sep-2024.)
|- ( N e. NN -> DECID N e. Prime )
Theorem	prmuz2 12269	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 12270	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 12271	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 12272	An odd prime is greater than 2. (Contributed by AV, 20-Aug-2021.)
|- ( P e. ( Prime \ { 2 } ) -> 2 < P )
Theorem	oddprmge3 12273	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 12274	A square is never prime. (Contributed by Mario Carneiro, 20-Jun-2015.)
|- ( A e. ZZ -> -. ( A ^ 2 ) e. Prime )
Theorem	dvdsprm 12275	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 12276*	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 12277*	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 12278	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 12279*	Lemma for isprm5 12280. 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 12280*	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 12281	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 12284.
Theorem	coprm 12282	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 12283	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 12284	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 12285*	A number is prime iff it satisfies Euclid's lemma euclemma 12284. (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 12286	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 12287	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 12288	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 12289	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 12290	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 12291	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 12292	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 12293	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 12294	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 12295	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 12296	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 12297	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 12298	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 12299	Lemma for sqrt2irr 12300. 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 12300	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 12318 for the proof that the square root of two is irrational. The proof's core is proven in sqrt2irrlem 12299, 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