P. 127 of Theorem List - Intuitionistic Logic Explorer

Theorem List for Intuitionistic Logic Explorer - 12601-12700   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	lcmcom 12601	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 12602	The value, by convention, of the lcm operator when either operand is 0. (Use lcmcom 12601 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 12603*	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 12604*	Lemma for lcmn0cl 12605 and dvdslcm 12606. (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 12605	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 12606	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 12607	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 12608	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 12609	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 12610	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 12611	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 12612	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 12613	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 12614	Lemma for lcmgcd 12615 and lcmdvds 12616. 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 12615	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 12547; see, e.g., https://proofwiki.org/wiki/Product_of_GCD_and_LCM 12547 and https://math.stackexchange.com/a/470827 12547. 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 12602 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 12616	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 12617	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 12618	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 12619	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 12620	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 12621	Biconditional form of lcmdvds 12616. (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 12622	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 12623	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 12624	The least common multiple of six and four is twelve. (Contributed by AV, 27-Aug-2020.)
|- ( 6 lcm 4 ) = ; 1 2
5.1.11  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 12625. The negation, i.e. two integers are not coprime, can be expressed either by ( A gcd B ) =/= 1, see ncoprmgcdne1b 12626, or equivalently by 1 < ( A gcd B ), see ncoprmgcdgt1b 12627. A proof of Euclid's lemma based on coprimality is provided in coprmdvds 12629 (as opposed to Euclid's lemma for primes).
Theorem	coprmgcdb 12625*	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 12626*	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 12627*	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 12628	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 12629	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 12630	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 12631	One half of rpmulgcd2 12632, 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 12632	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 12633	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 12634*	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 12635	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 12636	If K is relatively prime to N then it is also relatively prime to any divisor M of N. (Contributed by Mario Carneiro, 19-Jun-2015.)
|- ( ( ( K e. ZZ /\ M e. ZZ /\ N e. ZZ ) /\ ( ( K gcd N ) = 1 /\ M || N ) ) -> ( K gcd M ) = 1 )
5.1.12  Cancellability of congruences
Theorem	congr 12637*	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 12638	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 12639*	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 12640	One direction of the bicondition in cncongr 12642. 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 12641	The other direction of the bicondition in cncongr 12642. (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 12642	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 12643	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 3795.
Syntax	cprime 12644	Extend the definition of a class to include the set of prime numbers.
class Prime
Definition	df-prm 12645*	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 12646*	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 12647	A prime number is a positive integer. (Contributed by Paul Chapman, 22-Jun-2011.)
|- ( P e. Prime -> P e. NN )
Theorem	prmz 12648	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 12649	The prime numbers are a subset of the positive integers. (Contributed by AV, 22-Jul-2020.)
|- Prime C_ NN
Theorem	prmex 12650	The set of prime numbers exists. (Contributed by AV, 22-Jul-2020.)
|- Prime e. _V
Theorem	1nprm 12651	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 12652*	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 12653*	Lemma for isprm2 12654. (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 12654*	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 12655*	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 12656*	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 12657*	A variation on prmind 12658 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 12658*	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 12659	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 12660	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 12661	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 12662	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 12663	A prime number is either 2 or odd. (Contributed by AV, 19-Jun-2021.)
|- ( P e. Prime -> ( P = 2 \/ -. 2 || P ) )
Theorem	2prm 12664	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 12665	3 is a prime number. (Contributed by Paul Chapman, 22-Jun-2011.)
|- 3 e. Prime
Theorem	4nprm 12666	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 12667	Primality is decidable. (Contributed by Jim Kingdon, 30-Sep-2024.)
|- ( N e. NN -> DECID N e. Prime )
Theorem	prmuz2 12668	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 12669	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 12670	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 12671	An odd prime is greater than 2. (Contributed by AV, 20-Aug-2021.)
|- ( P e. ( Prime \ { 2 } ) -> 2 < P )
Theorem	oddprmge3 12672	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 12673	A square is never prime. (Contributed by Mario Carneiro, 20-Jun-2015.)
|- ( A e. ZZ -> -. ( A ^ 2 ) e. Prime )
Theorem	dvdsprm 12674	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 12675*	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 12676*	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 12677	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 12678*	Lemma for isprm5 12679. 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 12679*	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 12680	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 12683.
Theorem	coprm 12681	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 12682	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 12683	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 12684*	A number is prime iff it satisfies Euclid's lemma euclemma 12683. (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 12685	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 12686	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 12687	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 12688	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 12689	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 12690	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 12691	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 12692	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 12693	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 12694	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 12695	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 12696	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 12697	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 12698	Lemma for sqrt2irr 12699. 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 12699	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 12717 for the proof that the square root of two is irrational. The proof's core is proven in sqrt2irrlem 12698, which shows that if A / B = sqr ( 2 ), then A and B are even, so A / 2 and B / 2 are smaller representatives, which is absurd. (Contributed by NM, 8-Jan-2002.) (Proof shortened by Mario Carneiro, 12-Sep-2015.)
|- ( sqr ` 2 ) e/ QQ
Theorem	sqrt2re 12700	The square root of 2 exists and is a real number. (Contributed by NM, 3-Dec-2004.)
|- ( sqr ` 2 ) e. RR