P. 121 of Theorem List - Intuitionistic Logic Explorer

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

Type	Label	Description
Statement
Theorem	gcddvdslcm 12001	The greatest common divisor of two numbers divides their least common multiple. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) ∥ (𝑀 lcm 𝑁))
Theorem	lcmneg 12002	Negating one operand of the lcm operator does not alter the result. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 lcm -𝑁) = (𝑀 lcm 𝑁))
Theorem	neglcm 12003	Negating one operand of the lcm operator does not alter the result. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (-𝑀 lcm 𝑁) = (𝑀 lcm 𝑁))
Theorem	lcmabs 12004	The lcm of two integers is the same as that of their absolute values. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((abs‘𝑀) lcm (abs‘𝑁)) = (𝑀 lcm 𝑁))
Theorem	lcmgcdlem 12005	Lemma for lcmgcd 12006 and lcmdvds 12007. Prove them for positive 𝑀, 𝑁, and 𝐾. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → (((𝑀 lcm 𝑁) · (𝑀 gcd 𝑁)) = (abs‘(𝑀 · 𝑁)) ∧ ((𝐾 ∈ ℕ ∧ (𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾)) → (𝑀 lcm 𝑁) ∥ 𝐾)))
Theorem	lcmgcd 12006	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 (𝑀 gcd 𝑁) = 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 11940; see, e.g., https://proofwiki.org/wiki/Product_of_GCD_and_LCM 11940 and https://math.stackexchange.com/a/470827 11940. This proof uses the latter to first confirm it for positive integers 𝑀 and 𝑁 (the "Second Proof" in the above Stack Exchange page), then shows that implies it for all nonzero integer inputs, then finally uses lcm0val 11993 to show it applies when either or both inputs are zero. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 lcm 𝑁) · (𝑀 gcd 𝑁)) = (abs‘(𝑀 · 𝑁)))
Theorem	lcmdvds 12007	The lcm of two integers divides any integer the two divide. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾) → (𝑀 lcm 𝑁) ∥ 𝐾))
Theorem	lcmid 12008	The lcm of an integer and itself is its absolute value. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ (𝑀 ∈ ℤ → (𝑀 lcm 𝑀) = (abs‘𝑀))
Theorem	lcm1 12009	The lcm of an integer and 1 is the absolute value of the integer. (Contributed by AV, 23-Aug-2020.)
⊢ (𝑀 ∈ ℤ → (𝑀 lcm 1) = (abs‘𝑀))
Theorem	lcmgcdnn 12010	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.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((𝑀 lcm 𝑁) · (𝑀 gcd 𝑁)) = (𝑀 · 𝑁))
Theorem	lcmgcdeq 12011	Two integers' absolute values are equal iff their least common multiple and greatest common divisor are equal. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 lcm 𝑁) = (𝑀 gcd 𝑁) ↔ (abs‘𝑀) = (abs‘𝑁)))
Theorem	lcmdvdsb 12012	Biconditional form of lcmdvds 12007. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾) ↔ (𝑀 lcm 𝑁) ∥ 𝐾))
Theorem	lcmass 12013	Associative law for lcm operator. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑃 ∈ ℤ) → ((𝑁 lcm 𝑀) lcm 𝑃) = (𝑁 lcm (𝑀 lcm 𝑃)))
Theorem	3lcm2e6woprm 12014	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 12015	The least common multiple of six and four is twelve. (Contributed by AV, 27-Aug-2020.)
⊢ (6 lcm 4) = ;12
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 𝐴 ∈ ℤ and 𝐵 ∈ ℤ are coprime (or relatively prime) if (𝐴 gcd 𝐵) = 1. The equivalence of the definitions is shown by coprmgcdb 12016. The negation, i.e. two integers are not coprime, can be expressed either by (𝐴 gcd 𝐵) ≠ 1, see ncoprmgcdne1b 12017, or equivalently by 1 < (𝐴 gcd 𝐵), see ncoprmgcdgt1b 12018. A proof of Euclid's lemma based on coprimality is provided in coprmdvds 12020 (as opposed to Euclid's lemma for primes).
Theorem	coprmgcdb 12016*	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.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) → (∀𝑖 ∈ ℕ ((𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) → 𝑖 = 1) ↔ (𝐴 gcd 𝐵) = 1))
Theorem	ncoprmgcdne1b 12017*	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.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) → (∃𝑖 ∈ (ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) ↔ (𝐴 gcd 𝐵) ≠ 1))
Theorem	ncoprmgcdgt1b 12018*	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.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) → (∃𝑖 ∈ (ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) ↔ 1 < (𝐴 gcd 𝐵)))
Theorem	coprmdvds1 12019	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.)
⊢ ((𝐹 ∈ ℕ ∧ 𝐺 ∈ ℕ ∧ (𝐹 gcd 𝐺) = 1) → ((𝐼 ∈ ℕ ∧ 𝐼 ∥ 𝐹 ∧ 𝐼 ∥ 𝐺) → 𝐼 = 1))
Theorem	coprmdvds 12020	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.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝐾 ∥ (𝑀 · 𝑁) ∧ (𝐾 gcd 𝑀) = 1) → 𝐾 ∥ 𝑁))
Theorem	coprmdvds2 12021	If an integer is divisible by two coprime integers, then it is divisible by their product. (Contributed by Mario Carneiro, 24-Feb-2014.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝐾 ∈ ℤ) ∧ (𝑀 gcd 𝑁) = 1) → ((𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾) → (𝑀 · 𝑁) ∥ 𝐾))
Theorem	mulgcddvds 12022	One half of rpmulgcd2 12023, which does not need the coprimality assumption. (Contributed by Mario Carneiro, 2-Jul-2015.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝐾 gcd (𝑀 · 𝑁)) ∥ ((𝐾 gcd 𝑀) · (𝐾 gcd 𝑁)))
Theorem	rpmulgcd2 12023	If 𝑀 is relatively prime to 𝑁, then the GCD of 𝐾 with 𝑀 · 𝑁 is the product of the GCDs with 𝑀 and 𝑁 respectively. (Contributed by Mario Carneiro, 2-Jul-2015.)
⊢ (((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ (𝑀 gcd 𝑁) = 1) → (𝐾 gcd (𝑀 · 𝑁)) = ((𝐾 gcd 𝑀) · (𝐾 gcd 𝑁)))
Theorem	qredeq 12024	Two equal reduced fractions have the same numerator and denominator. (Contributed by Jeff Hankins, 29-Sep-2013.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ (𝑀 gcd 𝑁) = 1) ∧ (𝑃 ∈ ℤ ∧ 𝑄 ∈ ℕ ∧ (𝑃 gcd 𝑄) = 1) ∧ (𝑀 / 𝑁) = (𝑃 / 𝑄)) → (𝑀 = 𝑃 ∧ 𝑁 = 𝑄))
Theorem	qredeu 12025*	Every rational number has a unique reduced form. (Contributed by Jeff Hankins, 29-Sep-2013.)
⊢ (𝐴 ∈ ℚ → ∃!𝑥 ∈ (ℤ × ℕ)(((1st ‘𝑥) gcd (2nd ‘𝑥)) = 1 ∧ 𝐴 = ((1st ‘𝑥) / (2nd ‘𝑥))))
Theorem	rpmul 12026	If 𝐾 is relatively prime to 𝑀 and to 𝑁, it is also relatively prime to their product. (Contributed by Mario Carneiro, 24-Feb-2014.) (Proof shortened by Mario Carneiro, 2-Jul-2015.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (((𝐾 gcd 𝑀) = 1 ∧ (𝐾 gcd 𝑁) = 1) → (𝐾 gcd (𝑀 · 𝑁)) = 1))
Theorem	rpdvds 12027	If 𝐾 is relatively prime to 𝑁 then it is also relatively prime to any divisor 𝑀 of 𝑁. (Contributed by Mario Carneiro, 19-Jun-2015.)
⊢ (((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ((𝐾 gcd 𝑁) = 1 ∧ 𝑀 ∥ 𝑁)) → (𝐾 gcd 𝑀) = 1)
5.1.11  Cancellability of congruences
Theorem	congr 12028*	Definition of congruence by integer multiple (see ProofWiki "Congruence (Number Theory)", 11-Jul-2021, https://proofwiki.org/wiki/Definition:Congruence_(Number_Theory)): An integer 𝐴 is congruent to an integer 𝐵 modulo 𝑀 if their difference is a multiple of 𝑀. See also the definition in [ApostolNT] p. 104: "... 𝑎 is congruent to 𝑏 modulo 𝑚, and we write 𝑎≡𝑏 (mod 𝑚) if 𝑚 divides the difference 𝑎 − 𝑏", 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.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑀 ∈ ℕ) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) ↔ ∃𝑛 ∈ ℤ (𝑛 · 𝑀) = (𝐴 − 𝐵)))
Theorem	divgcdcoprm0 12029	Integers divided by gcd are coprime. (Contributed by AV, 12-Jul-2021.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐵 ≠ 0) → ((𝐴 / (𝐴 gcd 𝐵)) gcd (𝐵 / (𝐴 gcd 𝐵))) = 1)
Theorem	divgcdcoprmex 12030*	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.)
⊢ ((𝐴 ∈ ℤ ∧ (𝐵 ∈ ℤ ∧ 𝐵 ≠ 0) ∧ 𝑀 = (𝐴 gcd 𝐵)) → ∃𝑎 ∈ ℤ ∃𝑏 ∈ ℤ (𝐴 = (𝑀 · 𝑎) ∧ 𝐵 = (𝑀 · 𝑏) ∧ (𝑎 gcd 𝑏) = 1))
Theorem	cncongr1 12031	One direction of the bicondition in cncongr 12033. Theorem 5.4 in [ApostolNT] p. 109. (Contributed by AV, 13-Jul-2021.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) → (𝐴 mod 𝑀) = (𝐵 mod 𝑀)))
Theorem	cncongr2 12032	The other direction of the bicondition in cncongr 12033. (Contributed by AV, 11-Jul-2021.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → ((𝐴 mod 𝑀) = (𝐵 mod 𝑀) → ((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁)))
Theorem	cncongr 12033	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.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ 𝑀 = (𝑁 / (𝐶 gcd 𝑁)))) → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) ↔ (𝐴 mod 𝑀) = (𝐵 mod 𝑀)))
Theorem	cncongrcoprm 12034	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.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑁 ∈ ℕ ∧ (𝐶 gcd 𝑁) = 1)) → (((𝐴 · 𝐶) mod 𝑁) = ((𝐵 · 𝐶) mod 𝑁) ↔ (𝐴 mod 𝑁) = (𝐵 mod 𝑁)))
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 𝑃 ∈ (ℙ ∖ {2}) is used. It is a little bit shorter than (𝑃 ∈ ℙ ∧ 𝑃 ≠ 2). Both representations can be converted into each other by eldifsn 3702.
Syntax	cprime 12035	Extend the definition of a class to include the set of prime numbers.
class ℙ
Definition	df-prm 12036*	Define the set of prime numbers. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ ℙ = {𝑝 ∈ ℕ ∣ {𝑛 ∈ ℕ ∣ 𝑛 ∥ 𝑝} ≈ 2o}
Theorem	isprm 12037*	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.)
⊢ (𝑃 ∈ ℙ ↔ (𝑃 ∈ ℕ ∧ {𝑛 ∈ ℕ ∣ 𝑛 ∥ 𝑃} ≈ 2o))
Theorem	prmnn 12038	A prime number is a positive integer. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
Theorem	prmz 12039	A prime number is an integer. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Jonathan Yan, 16-Jul-2017.)
⊢ (𝑃 ∈ ℙ → 𝑃 ∈ ℤ)
Theorem	prmssnn 12040	The prime numbers are a subset of the positive integers. (Contributed by AV, 22-Jul-2020.)
⊢ ℙ ⊆ ℕ
Theorem	prmex 12041	The set of prime numbers exists. (Contributed by AV, 22-Jul-2020.)
⊢ ℙ ∈ V
Theorem	1nprm 12042	1 is not a prime number. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Fan Zheng, 3-Jul-2016.)
⊢ ¬ 1 ∈ ℙ
Theorem	1idssfct 12043*	The positive divisors of a positive integer include 1 and itself. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ (𝑁 ∈ ℕ → {1, 𝑁} ⊆ {𝑛 ∈ ℕ ∣ 𝑛 ∥ 𝑁})
Theorem	isprm2lem 12044*	Lemma for isprm2 12045. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ ((𝑃 ∈ ℕ ∧ 𝑃 ≠ 1) → ({𝑛 ∈ ℕ ∣ 𝑛 ∥ 𝑃} ≈ 2o ↔ {𝑛 ∈ ℕ ∣ 𝑛 ∥ 𝑃} = {1, 𝑃}))
Theorem	isprm2 12045*	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.)
⊢ (𝑃 ∈ ℙ ↔ (𝑃 ∈ (ℤ≥‘2) ∧ ∀𝑧 ∈ ℕ (𝑧 ∥ 𝑃 → (𝑧 = 1 ∨ 𝑧 = 𝑃))))
Theorem	isprm3 12046*	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.)
⊢ (𝑃 ∈ ℙ ↔ (𝑃 ∈ (ℤ≥‘2) ∧ ∀𝑧 ∈ (2...(𝑃 − 1)) ¬ 𝑧 ∥ 𝑃))
Theorem	isprm4 12047*	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.)
⊢ (𝑃 ∈ ℙ ↔ (𝑃 ∈ (ℤ≥‘2) ∧ ∀𝑧 ∈ (ℤ≥‘2)(𝑧 ∥ 𝑃 → 𝑧 = 𝑃)))
Theorem	prmind2 12048*	A variation on prmind 12049 assuming complete induction for primes. (Contributed by Mario Carneiro, 20-Jun-2015.)
⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓))    &   ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))    &   ⊢ (𝑥 = 𝑧 → (𝜑 ↔ 𝜃))    &   ⊢ (𝑥 = (𝑦 · 𝑧) → (𝜑 ↔ 𝜏))    &   ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜂))    &   ⊢ 𝜓    &   ⊢ ((𝑥 ∈ ℙ ∧ ∀𝑦 ∈ (1...(𝑥 − 1))𝜒) → 𝜑)    &   ⊢ ((𝑦 ∈ (ℤ≥‘2) ∧ 𝑧 ∈ (ℤ≥‘2)) → ((𝜒 ∧ 𝜃) → 𝜏))    ⇒   ⊢ (𝐴 ∈ ℕ → 𝜂)
Theorem	prmind 12049*	Perform induction over the multiplicative structure of ℕ. If a property 𝜑(𝑥) 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.)
⊢ (𝑥 = 1 → (𝜑 ↔ 𝜓))    &   ⊢ (𝑥 = 𝑦 → (𝜑 ↔ 𝜒))    &   ⊢ (𝑥 = 𝑧 → (𝜑 ↔ 𝜃))    &   ⊢ (𝑥 = (𝑦 · 𝑧) → (𝜑 ↔ 𝜏))    &   ⊢ (𝑥 = 𝐴 → (𝜑 ↔ 𝜂))    &   ⊢ 𝜓    &   ⊢ (𝑥 ∈ ℙ → 𝜑)    &   ⊢ ((𝑦 ∈ (ℤ≥‘2) ∧ 𝑧 ∈ (ℤ≥‘2)) → ((𝜒 ∧ 𝜃) → 𝜏))    ⇒   ⊢ (𝐴 ∈ ℕ → 𝜂)
Theorem	dvdsprime 12050	If 𝑀 divides a prime, then 𝑀 is either the prime or one. (Contributed by Scott Fenton, 8-Apr-2014.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑀 ∈ ℕ) → (𝑀 ∥ 𝑃 ↔ (𝑀 = 𝑃 ∨ 𝑀 = 1)))
Theorem	nprm 12051	A product of two integers greater than one is composite. (Contributed by Mario Carneiro, 20-Jun-2015.)
⊢ ((𝐴 ∈ (ℤ≥‘2) ∧ 𝐵 ∈ (ℤ≥‘2)) → ¬ (𝐴 · 𝐵) ∈ ℙ)
Theorem	nprmi 12052	An inference for compositeness. (Contributed by Mario Carneiro, 18-Feb-2014.) (Revised by Mario Carneiro, 20-Jun-2015.)
⊢ 𝐴 ∈ ℕ    &   ⊢ 𝐵 ∈ ℕ    &   ⊢ 1 < 𝐴    &   ⊢ 1 < 𝐵    &   ⊢ (𝐴 · 𝐵) = 𝑁    ⇒   ⊢ ¬ 𝑁 ∈ ℙ
Theorem	dvdsnprmd 12053	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.)
⊢ (𝜑 → 1 < 𝐴)    &   ⊢ (𝜑 → 𝐴 < 𝑁)    &   ⊢ (𝜑 → 𝐴 ∥ 𝑁)    ⇒   ⊢ (𝜑 → ¬ 𝑁 ∈ ℙ)
Theorem	prm2orodd 12054	A prime number is either 2 or odd. (Contributed by AV, 19-Jun-2021.)
⊢ (𝑃 ∈ ℙ → (𝑃 = 2 ∨ ¬ 2 ∥ 𝑃))
Theorem	2prm 12055	2 is a prime number. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Fan Zheng, 16-Jun-2016.)
⊢ 2 ∈ ℙ
Theorem	3prm 12056	3 is a prime number. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ 3 ∈ ℙ
Theorem	4nprm 12057	4 is not a prime number. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by Mario Carneiro, 18-Feb-2014.)
⊢ ¬ 4 ∈ ℙ
Theorem	prmdc 12058	Primality is decidable. (Contributed by Jim Kingdon, 30-Sep-2024.)
⊢ (𝑁 ∈ ℕ → DECID 𝑁 ∈ ℙ)
Theorem	prmuz2 12059	A prime number is an integer greater than or equal to 2. (Contributed by Paul Chapman, 17-Nov-2012.)
⊢ (𝑃 ∈ ℙ → 𝑃 ∈ (ℤ≥‘2))
Theorem	prmgt1 12060	A prime number is an integer greater than 1. (Contributed by Alexander van der Vekens, 17-May-2018.)
⊢ (𝑃 ∈ ℙ → 1 < 𝑃)
Theorem	prmm2nn0 12061	Subtracting 2 from a prime number results in a nonnegative integer. (Contributed by Alexander van der Vekens, 30-Aug-2018.)
⊢ (𝑃 ∈ ℙ → (𝑃 − 2) ∈ ℕ0)
Theorem	oddprmgt2 12062	An odd prime is greater than 2. (Contributed by AV, 20-Aug-2021.)
⊢ (𝑃 ∈ (ℙ ∖ {2}) → 2 < 𝑃)
Theorem	oddprmge3 12063	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.)
⊢ (𝑃 ∈ (ℙ ∖ {2}) → 𝑃 ∈ (ℤ≥‘3))
Theorem	sqnprm 12064	A square is never prime. (Contributed by Mario Carneiro, 20-Jun-2015.)
⊢ (𝐴 ∈ ℤ → ¬ (𝐴↑2) ∈ ℙ)
Theorem	dvdsprm 12065	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.)
⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ 𝑃 ∈ ℙ) → (𝑁 ∥ 𝑃 ↔ 𝑁 = 𝑃))
Theorem	exprmfct 12066*	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.)
⊢ (𝑁 ∈ (ℤ≥‘2) → ∃𝑝 ∈ ℙ 𝑝 ∥ 𝑁)
Theorem	prmdvdsfz 12067*	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.)
⊢ ((𝑁 ∈ ℕ ∧ 𝐼 ∈ (2...𝑁)) → ∃𝑝 ∈ ℙ (𝑝 ≤ 𝑁 ∧ 𝑝 ∥ 𝐼))
Theorem	nprmdvds1 12068	No prime number divides 1. (Contributed by Paul Chapman, 17-Nov-2012.) (Proof shortened by Mario Carneiro, 2-Jul-2015.)
⊢ (𝑃 ∈ ℙ → ¬ 𝑃 ∥ 1)
Theorem	isprm5lem 12069*	Lemma for isprm5 12070. The interesting direction (showing that one only needs to check prime divisors up to the square root of 𝑃). (Contributed by Jim Kingdon, 20-Oct-2024.)
⊢ (𝜑 → 𝑃 ∈ (ℤ≥‘2))    &   ⊢ (𝜑 → ∀𝑧 ∈ ℙ ((𝑧↑2) ≤ 𝑃 → ¬ 𝑧 ∥ 𝑃))    &   ⊢ (𝜑 → 𝑋 ∈ (2...(𝑃 − 1)))    ⇒   ⊢ (𝜑 → ¬ 𝑋 ∥ 𝑃)
Theorem	isprm5 12070*	One need only check prime divisors of 𝑃 up to √𝑃 in order to ensure primality. (Contributed by Mario Carneiro, 18-Feb-2014.)
⊢ (𝑃 ∈ ℙ ↔ (𝑃 ∈ (ℤ≥‘2) ∧ ∀𝑧 ∈ ℙ ((𝑧↑2) ≤ 𝑃 → ¬ 𝑧 ∥ 𝑃)))
Theorem	divgcdodd 12071	Either 𝐴 / (𝐴 gcd 𝐵) is odd or 𝐵 / (𝐴 gcd 𝐵) is odd. (Contributed by Scott Fenton, 19-Apr-2014.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) → (¬ 2 ∥ (𝐴 / (𝐴 gcd 𝐵)) ∨ ¬ 2 ∥ (𝐵 / (𝐴 gcd 𝐵))))
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 12074.
Theorem	coprm 12072	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.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑁 ∈ ℤ) → (¬ 𝑃 ∥ 𝑁 ↔ (𝑃 gcd 𝑁) = 1))
Theorem	prmrp 12073	Unequal prime numbers are relatively prime. (Contributed by Mario Carneiro, 23-Feb-2014.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑄 ∈ ℙ) → ((𝑃 gcd 𝑄) = 1 ↔ 𝑃 ≠ 𝑄))
Theorem	euclemma 12074	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.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑃 ∥ (𝑀 · 𝑁) ↔ (𝑃 ∥ 𝑀 ∨ 𝑃 ∥ 𝑁)))
Theorem	isprm6 12075*	A number is prime iff it satisfies Euclid's lemma euclemma 12074. (Contributed by Mario Carneiro, 6-Sep-2015.)
⊢ (𝑃 ∈ ℙ ↔ (𝑃 ∈ (ℤ≥‘2) ∧ ∀𝑥 ∈ ℤ ∀𝑦 ∈ ℤ (𝑃 ∥ (𝑥 · 𝑦) → (𝑃 ∥ 𝑥 ∨ 𝑃 ∥ 𝑦))))
Theorem	prmdvdsexp 12076	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.)
⊢ ((𝑃 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑃 ∥ (𝐴↑𝑁) ↔ 𝑃 ∥ 𝐴))
Theorem	prmdvdsexpb 12077	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.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑄 ∈ ℙ ∧ 𝑁 ∈ ℕ) → (𝑃 ∥ (𝑄↑𝑁) ↔ 𝑃 = 𝑄))
Theorem	prmdvdsexpr 12078	If a prime divides a nonnegative power of another, then they are equal. (Contributed by Mario Carneiro, 16-Jan-2015.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑄 ∈ ℙ ∧ 𝑁 ∈ ℕ0) → (𝑃 ∥ (𝑄↑𝑁) → 𝑃 = 𝑄))
Theorem	prmexpb 12079	Two positive prime powers are equal iff the primes and the powers are equal. (Contributed by Paul Chapman, 30-Nov-2012.)
⊢ (((𝑃 ∈ ℙ ∧ 𝑄 ∈ ℙ) ∧ (𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ)) → ((𝑃↑𝑀) = (𝑄↑𝑁) ↔ (𝑃 = 𝑄 ∧ 𝑀 = 𝑁)))
Theorem	prmfac1 12080	The factorial of a number only contains primes less than the base. (Contributed by Mario Carneiro, 6-Mar-2014.)
⊢ ((𝑁 ∈ ℕ0 ∧ 𝑃 ∈ ℙ ∧ 𝑃 ∥ (!‘𝑁)) → 𝑃 ≤ 𝑁)
Theorem	rpexp 12081	If two numbers 𝐴 and 𝐵 are relatively prime, then they are still relatively prime if raised to a power. (Contributed by Mario Carneiro, 24-Feb-2014.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (((𝐴↑𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1))
Theorem	rpexp1i 12082	Relative primality passes to asymmetric powers. (Contributed by Stefan O'Rear, 27-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑀 ∈ ℕ0) → ((𝐴 gcd 𝐵) = 1 → ((𝐴↑𝑀) gcd 𝐵) = 1))
Theorem	rpexp12i 12083	Relative primality passes to symmetric powers. (Contributed by Stefan O'Rear, 27-Sep-2014.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ (𝑀 ∈ ℕ0 ∧ 𝑁 ∈ ℕ0)) → ((𝐴 gcd 𝐵) = 1 → ((𝐴↑𝑀) gcd (𝐵↑𝑁)) = 1))
Theorem	prmndvdsfaclt 12084	A prime number does not divide the factorial of a nonnegative integer less than the prime number. (Contributed by AV, 13-Jul-2021.)
⊢ ((𝑃 ∈ ℙ ∧ 𝑁 ∈ ℕ0) → (𝑁 < 𝑃 → ¬ 𝑃 ∥ (!‘𝑁)))
Theorem	cncongrprm 12085	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.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) ∧ (𝑃 ∈ ℙ ∧ ¬ 𝑃 ∥ 𝐶)) → (((𝐴 · 𝐶) mod 𝑃) = ((𝐵 · 𝐶) mod 𝑃) ↔ (𝐴 mod 𝑃) = (𝐵 mod 𝑃)))
Theorem	isevengcd2 12086	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.)
⊢ (𝑍 ∈ ℤ → (2 ∥ 𝑍 ↔ (2 gcd 𝑍) = 2))
Theorem	isoddgcd1 12087	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.)
⊢ (𝑍 ∈ ℤ → (¬ 2 ∥ 𝑍 ↔ (2 gcd 𝑍) = 1))
Theorem	3lcm2e6 12088	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 12089	Lemma for sqrt2irr 12090. This is the core of the proof: - if 𝐴 / 𝐵 = √(2), then 𝐴 and 𝐵 are even, so 𝐴 / 2 and 𝐵 / 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.)
⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℕ)    &   ⊢ (𝜑 → (√‘2) = (𝐴 / 𝐵))    ⇒   ⊢ (𝜑 → ((𝐴 / 2) ∈ ℤ ∧ (𝐵 / 2) ∈ ℕ))
Theorem	sqrt2irr 12090	The square root of 2 is not rational. That is, for any rational number, (√‘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, (√‘2) is apart from it" (the two statements are equivalent given excluded middle). See sqrt2irrap 12108 for the proof that the square root of two is irrational. The proof's core is proven in sqrt2irrlem 12089, which shows that if 𝐴 / 𝐵 = √(2), then 𝐴 and 𝐵 are even, so 𝐴 / 2 and 𝐵 / 2 are smaller representatives, which is absurd. (Contributed by NM, 8-Jan-2002.) (Proof shortened by Mario Carneiro, 12-Sep-2015.)
⊢ (√‘2) ∉ ℚ
Theorem	sqrt2re 12091	The square root of 2 exists and is a real number. (Contributed by NM, 3-Dec-2004.)
⊢ (√‘2) ∈ ℝ
Theorem	sqrt2irr0 12092	The square root of 2 is not rational. (Contributed by AV, 23-Dec-2022.)
⊢ (√‘2) ∈ (ℝ ∖ ℚ)
Theorem	pw2dvdslemn 12093*	Lemma for pw2dvds 12094. If a natural number has some power of two which does not divide it, there is a highest power of two which does divide it. (Contributed by Jim Kingdon, 14-Nov-2021.)
⊢ ((𝑁 ∈ ℕ ∧ 𝐴 ∈ ℕ ∧ ¬ (2↑𝐴) ∥ 𝑁) → ∃𝑚 ∈ ℕ0 ((2↑𝑚) ∥ 𝑁 ∧ ¬ (2↑(𝑚 + 1)) ∥ 𝑁))
Theorem	pw2dvds 12094*	A natural number has a highest power of two which divides it. (Contributed by Jim Kingdon, 14-Nov-2021.)
⊢ (𝑁 ∈ ℕ → ∃𝑚 ∈ ℕ0 ((2↑𝑚) ∥ 𝑁 ∧ ¬ (2↑(𝑚 + 1)) ∥ 𝑁))
Theorem	pw2dvdseulemle 12095	Lemma for pw2dvdseu 12096. Powers of two which do and do not divide a natural number. (Contributed by Jim Kingdon, 17-Nov-2021.)
⊢ (𝜑 → 𝑁 ∈ ℕ)    &   ⊢ (𝜑 → 𝐴 ∈ ℕ0)    &   ⊢ (𝜑 → 𝐵 ∈ ℕ0)    &   ⊢ (𝜑 → (2↑𝐴) ∥ 𝑁)    &   ⊢ (𝜑 → ¬ (2↑(𝐵 + 1)) ∥ 𝑁)    ⇒   ⊢ (𝜑 → 𝐴 ≤ 𝐵)
Theorem	pw2dvdseu 12096*	A natural number has a unique highest power of two which divides it. (Contributed by Jim Kingdon, 16-Nov-2021.)
⊢ (𝑁 ∈ ℕ → ∃!𝑚 ∈ ℕ0 ((2↑𝑚) ∥ 𝑁 ∧ ¬ (2↑(𝑚 + 1)) ∥ 𝑁))
Theorem	oddpwdclemxy 12097*	Lemma for oddpwdc 12102. Another way of stating that decomposing a natural number into a power of two and an odd number is unique. (Contributed by Jim Kingdon, 16-Nov-2021.)
⊢ ((((𝑋 ∈ ℕ ∧ ¬ 2 ∥ 𝑋) ∧ 𝑌 ∈ ℕ0) ∧ 𝐴 = ((2↑𝑌) · 𝑋)) → (𝑋 = (𝐴 / (2↑(℩𝑧 ∈ ℕ0 ((2↑𝑧) ∥ 𝐴 ∧ ¬ (2↑(𝑧 + 1)) ∥ 𝐴)))) ∧ 𝑌 = (℩𝑧 ∈ ℕ0 ((2↑𝑧) ∥ 𝐴 ∧ ¬ (2↑(𝑧 + 1)) ∥ 𝐴))))
Theorem	oddpwdclemdvds 12098*	Lemma for oddpwdc 12102. A natural number is divisible by the highest power of two which divides it. (Contributed by Jim Kingdon, 17-Nov-2021.)
⊢ (𝐴 ∈ ℕ → (2↑(℩𝑧 ∈ ℕ0 ((2↑𝑧) ∥ 𝐴 ∧ ¬ (2↑(𝑧 + 1)) ∥ 𝐴))) ∥ 𝐴)
Theorem	oddpwdclemndvds 12099*	Lemma for oddpwdc 12102. A natural number is not divisible by one more than the highest power of two which divides it. (Contributed by Jim Kingdon, 17-Nov-2021.)
⊢ (𝐴 ∈ ℕ → ¬ (2↑((℩𝑧 ∈ ℕ0 ((2↑𝑧) ∥ 𝐴 ∧ ¬ (2↑(𝑧 + 1)) ∥ 𝐴)) + 1)) ∥ 𝐴)
Theorem	oddpwdclemodd 12100*	Lemma for oddpwdc 12102. Removing the powers of two from a natural number produces an odd number. (Contributed by Jim Kingdon, 16-Nov-2021.)
⊢ (𝐴 ∈ ℕ → ¬ 2 ∥ (𝐴 / (2↑(℩𝑧 ∈ ℕ0 ((2↑𝑧) ∥ 𝐴 ∧ ¬ (2↑(𝑧 + 1)) ∥ 𝐴)))))