P. 166 of Theorem List - Metamath Proof Explorer

Theorem List for Metamath Proof Explorer - 16501-16600   *Has distinct variable group(s)

Type	Label	Description
Statement
Theorem	dvdsmulgcd 16501	A divisibility equivalent for odmulg 19465. (Contributed by Stefan O'Rear, 6-Sep-2015.)
⊢ ((𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (𝐴 ∥ (𝐵 · 𝐶) ↔ 𝐴 ∥ (𝐵 · (𝐶 gcd 𝐴))))
Theorem	rpmulgcd 16502	If 𝐾 and 𝑀 are relatively prime, then the GCD of 𝐾 and 𝑀 · 𝑁 is the GCD of 𝐾 and 𝑁. (Contributed by Scott Fenton, 12-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ (((𝐾 ∈ ℕ ∧ 𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) ∧ (𝐾 gcd 𝑀) = 1) → (𝐾 gcd (𝑀 · 𝑁)) = (𝐾 gcd 𝑁))
Theorem	rplpwr 16503	If 𝐴 and 𝐵 are relatively prime, then so are 𝐴↑𝑁 and 𝐵. (Contributed by Scott Fenton, 12-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((𝐴 gcd 𝐵) = 1 → ((𝐴↑𝑁) gcd 𝐵) = 1))
Theorem	rprpwr 16504	If 𝐴 and 𝐵 are relatively prime, then so are 𝐴 and 𝐵↑𝑁. Originally a subproof of rppwr 16505. (Contributed by SN, 21-Aug-2024.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((𝐴 gcd 𝐵) = 1 → (𝐴 gcd (𝐵↑𝑁)) = 1))
Theorem	rppwr 16505	If 𝐴 and 𝐵 are relatively prime, then so are 𝐴↑𝑁 and 𝐵↑𝑁. (Contributed by Scott Fenton, 12-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((𝐴 gcd 𝐵) = 1 → ((𝐴↑𝑁) gcd (𝐵↑𝑁)) = 1))
Theorem	sqgcd 16506	Square distributes over gcd. (Contributed by Scott Fenton, 18-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((𝑀 gcd 𝑁)↑2) = ((𝑀↑2) gcd (𝑁↑2)))
Theorem	dvdssqlem 16507	Lemma for dvdssq 16508. (Contributed by Scott Fenton, 18-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → (𝑀 ∥ 𝑁 ↔ (𝑀↑2) ∥ (𝑁↑2)))
Theorem	dvdssq 16508	Two numbers are divisible iff their squares are. (Contributed by Scott Fenton, 18-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ 𝑁 ↔ (𝑀↑2) ∥ (𝑁↑2)))
Theorem	bezoutr 16509	Partial converse to bezout 16489. Existence of a linear combination does not set the GCD, but it does upper bound it. (Contributed by Stefan O'Rear, 23-Sep-2014.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) → (𝐴 gcd 𝐵) ∥ ((𝐴 · 𝑋) + (𝐵 · 𝑌)))
Theorem	bezoutr1 16510	Converse of bezout 16489 for when the greater common divisor is one (sufficient condition for relative primality). (Contributed by Stefan O'Rear, 23-Sep-2014.)
⊢ (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ (𝑋 ∈ ℤ ∧ 𝑌 ∈ ℤ)) → (((𝐴 · 𝑋) + (𝐵 · 𝑌)) = 1 → (𝐴 gcd 𝐵) = 1))
6.1.9  Algorithms
Theorem	nn0seqcvgd 16511*	A strictly-decreasing nonnegative integer sequence with initial term 𝑁 reaches zero by the 𝑁 th term. Deduction version. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ (𝜑 → 𝐹:ℕ0⟶ℕ0)    &   ⊢ (𝜑 → 𝑁 = (𝐹‘0))    &   ⊢ ((𝜑 ∧ 𝑘 ∈ ℕ0) → ((𝐹‘(𝑘 + 1)) ≠ 0 → (𝐹‘(𝑘 + 1)) < (𝐹‘𝑘)))    ⇒   ⊢ (𝜑 → (𝐹‘𝑁) = 0)
Theorem	seq1st 16512	A sequence whose iteration function ignores the second argument is only affected by the first point of the initial value function. (Contributed by Mario Carneiro, 11-Feb-2015.)
⊢ 𝑍 = (ℤ≥‘𝑀)    &   ⊢ 𝑅 = seq𝑀((𝐹 ∘ 1st ), (𝑍 × {𝐴}))    ⇒   ⊢ ((𝑀 ∈ ℤ ∧ 𝐴 ∈ 𝑉) → 𝑅 = seq𝑀((𝐹 ∘ 1st ), {⟨𝑀, 𝐴⟩}))
Theorem	algr0 16513	The value of the algorithm iterator 𝑅 at 0 is the initial state 𝐴. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 28-May-2014.)
⊢ 𝑍 = (ℤ≥‘𝑀)    &   ⊢ 𝑅 = seq𝑀((𝐹 ∘ 1st ), (𝑍 × {𝐴}))    &   ⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝐴 ∈ 𝑆)    ⇒   ⊢ (𝜑 → (𝑅‘𝑀) = 𝐴)
Theorem	algrf 16514	An algorithm is a step function 𝐹:𝑆⟶𝑆 on a state space 𝑆. An algorithm acts on an initial state 𝐴 ∈ 𝑆 by iteratively applying 𝐹 to give 𝐴, (𝐹‘𝐴), (𝐹‘(𝐹‘𝐴)) and so on. An algorithm is said to halt if a fixed point of 𝐹 is reached after a finite number of iterations. The algorithm iterator 𝑅:ℕ0⟶𝑆 "runs" the algorithm 𝐹 so that (𝑅‘𝑘) is the state after 𝑘 iterations of 𝐹 on the initial state 𝐴. Domain and codomain of the algorithm iterator 𝑅. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 28-May-2014.)
⊢ 𝑍 = (ℤ≥‘𝑀)    &   ⊢ 𝑅 = seq𝑀((𝐹 ∘ 1st ), (𝑍 × {𝐴}))    &   ⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝐴 ∈ 𝑆)    &   ⊢ (𝜑 → 𝐹:𝑆⟶𝑆)    ⇒   ⊢ (𝜑 → 𝑅:𝑍⟶𝑆)
Theorem	algrp1 16515	The value of the algorithm iterator 𝑅 at (𝐾 + 1). (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 27-Dec-2014.)
⊢ 𝑍 = (ℤ≥‘𝑀)    &   ⊢ 𝑅 = seq𝑀((𝐹 ∘ 1st ), (𝑍 × {𝐴}))    &   ⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝐴 ∈ 𝑆)    &   ⊢ (𝜑 → 𝐹:𝑆⟶𝑆)    ⇒   ⊢ ((𝜑 ∧ 𝐾 ∈ 𝑍) → (𝑅‘(𝐾 + 1)) = (𝐹‘(𝑅‘𝐾)))
Theorem	alginv 16516*	If 𝐼 is an invariant of 𝐹, then its value is unchanged after any number of iterations of 𝐹. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ 𝑅 = seq0((𝐹 ∘ 1st ), (ℕ0 × {𝐴}))    &   ⊢ 𝐹:𝑆⟶𝑆    &   ⊢ (𝑥 ∈ 𝑆 → (𝐼‘(𝐹‘𝑥)) = (𝐼‘𝑥))    ⇒   ⊢ ((𝐴 ∈ 𝑆 ∧ 𝐾 ∈ ℕ0) → (𝐼‘(𝑅‘𝐾)) = (𝐼‘(𝑅‘0)))
Theorem	algcvg 16517*	One way to prove that an algorithm halts is to construct a countdown function 𝐶:𝑆⟶ℕ0 whose value is guaranteed to decrease for each iteration of 𝐹 until it reaches 0. That is, if 𝑋 ∈ 𝑆 is not a fixed point of 𝐹, then (𝐶‘(𝐹‘𝑋)) < (𝐶‘𝑋). If 𝐶 is a countdown function for algorithm 𝐹, the sequence (𝐶‘(𝑅‘𝑘)) reaches 0 after at most 𝑁 steps, where 𝑁 is the value of 𝐶 for the initial state 𝐴. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ 𝐹:𝑆⟶𝑆    &   ⊢ 𝑅 = seq0((𝐹 ∘ 1st ), (ℕ0 × {𝐴}))    &   ⊢ 𝐶:𝑆⟶ℕ0    &   ⊢ (𝑧 ∈ 𝑆 → ((𝐶‘(𝐹‘𝑧)) ≠ 0 → (𝐶‘(𝐹‘𝑧)) < (𝐶‘𝑧)))    &   ⊢ 𝑁 = (𝐶‘𝐴)    ⇒   ⊢ (𝐴 ∈ 𝑆 → (𝐶‘(𝑅‘𝑁)) = 0)
Theorem	algcvgblem 16518	Lemma for algcvgb 16519. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ ((𝑀 ∈ ℕ0 ∧ 𝑁 ∈ ℕ0) → ((𝑁 ≠ 0 → 𝑁 < 𝑀) ↔ ((𝑀 ≠ 0 → 𝑁 < 𝑀) ∧ (𝑀 = 0 → 𝑁 = 0))))
Theorem	algcvgb 16519	Two ways of expressing that 𝐶 is a countdown function for algorithm 𝐹. The first is used in these theorems. The second states the condition more intuitively as a conjunction: if the countdown function's value is currently nonzero, it must decrease at the next step; if it has reached zero, it must remain zero at the next step. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ 𝐹:𝑆⟶𝑆    &   ⊢ 𝐶:𝑆⟶ℕ0    ⇒   ⊢ (𝑋 ∈ 𝑆 → (((𝐶‘(𝐹‘𝑋)) ≠ 0 → (𝐶‘(𝐹‘𝑋)) < (𝐶‘𝑋)) ↔ (((𝐶‘𝑋) ≠ 0 → (𝐶‘(𝐹‘𝑋)) < (𝐶‘𝑋)) ∧ ((𝐶‘𝑋) = 0 → (𝐶‘(𝐹‘𝑋)) = 0))))
Theorem	algcvga 16520*	The countdown function 𝐶 remains 0 after 𝑁 steps. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ 𝐹:𝑆⟶𝑆    &   ⊢ 𝑅 = seq0((𝐹 ∘ 1st ), (ℕ0 × {𝐴}))    &   ⊢ 𝐶:𝑆⟶ℕ0    &   ⊢ (𝑧 ∈ 𝑆 → ((𝐶‘(𝐹‘𝑧)) ≠ 0 → (𝐶‘(𝐹‘𝑧)) < (𝐶‘𝑧)))    &   ⊢ 𝑁 = (𝐶‘𝐴)    ⇒   ⊢ (𝐴 ∈ 𝑆 → (𝐾 ∈ (ℤ≥‘𝑁) → (𝐶‘(𝑅‘𝐾)) = 0))
Theorem	algfx 16521*	If 𝐹 reaches a fixed point when the countdown function 𝐶 reaches 0, 𝐹 remains fixed after 𝑁 steps. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ 𝐹:𝑆⟶𝑆    &   ⊢ 𝑅 = seq0((𝐹 ∘ 1st ), (ℕ0 × {𝐴}))    &   ⊢ 𝐶:𝑆⟶ℕ0    &   ⊢ (𝑧 ∈ 𝑆 → ((𝐶‘(𝐹‘𝑧)) ≠ 0 → (𝐶‘(𝐹‘𝑧)) < (𝐶‘𝑧)))    &   ⊢ 𝑁 = (𝐶‘𝐴)    &   ⊢ (𝑧 ∈ 𝑆 → ((𝐶‘𝑧) = 0 → (𝐹‘𝑧) = 𝑧))    ⇒   ⊢ (𝐴 ∈ 𝑆 → (𝐾 ∈ (ℤ≥‘𝑁) → (𝑅‘𝐾) = (𝑅‘𝑁)))
6.1.10  Euclid's Algorithm
Theorem	eucalgval2 16522*	The value of the step function 𝐸 for Euclid's Algorithm on an ordered pair. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 28-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    ⇒   ⊢ ((𝑀 ∈ ℕ0 ∧ 𝑁 ∈ ℕ0) → (𝑀𝐸𝑁) = if(𝑁 = 0, ⟨𝑀, 𝑁⟩, ⟨𝑁, (𝑀 mod 𝑁)⟩))
Theorem	eucalgval 16523*	Euclid's Algorithm eucalg 16528 computes the greatest common divisor of two nonnegative integers by repeatedly replacing the larger of them with its remainder modulo the smaller until the remainder is 0. The value of the step function 𝐸 for Euclid's Algorithm. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 28-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    ⇒   ⊢ (𝑋 ∈ (ℕ0 × ℕ0) → (𝐸‘𝑋) = if((2nd ‘𝑋) = 0, 𝑋, ⟨(2nd ‘𝑋), ( mod ‘𝑋)⟩))
Theorem	eucalgf 16524*	Domain and codomain of the step function 𝐸 for Euclid's Algorithm. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 28-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    ⇒   ⊢ 𝐸:(ℕ0 × ℕ0)⟶(ℕ0 × ℕ0)
Theorem	eucalginv 16525*	The invariant of the step function 𝐸 for Euclid's Algorithm is the gcd operator applied to the state. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 29-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    ⇒   ⊢ (𝑋 ∈ (ℕ0 × ℕ0) → ( gcd ‘(𝐸‘𝑋)) = ( gcd ‘𝑋))
Theorem	eucalglt 16526*	The second member of the state decreases with each iteration of the step function 𝐸 for Euclid's Algorithm. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 29-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    ⇒   ⊢ (𝑋 ∈ (ℕ0 × ℕ0) → ((2nd ‘(𝐸‘𝑋)) ≠ 0 → (2nd ‘(𝐸‘𝑋)) < (2nd ‘𝑋)))
Theorem	eucalgcvga 16527*	Once Euclid's Algorithm halts after 𝑁 steps, the second element of the state remains 0 . (Contributed by Paul Chapman, 22-Jun-2011.) (Revised by Mario Carneiro, 29-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    &   ⊢ 𝑅 = seq0((𝐸 ∘ 1st ), (ℕ0 × {𝐴}))    &   ⊢ 𝑁 = (2nd ‘𝐴)    ⇒   ⊢ (𝐴 ∈ (ℕ0 × ℕ0) → (𝐾 ∈ (ℤ≥‘𝑁) → (2nd ‘(𝑅‘𝐾)) = 0))
Theorem	eucalg 16528*	Euclid's Algorithm computes the greatest common divisor of two nonnegative integers by repeatedly replacing the larger of them with its remainder modulo the smaller until the remainder is 0. Theorem 1.15 in [ApostolNT] p. 20. Upon halting, the first member of the final state (𝑅‘𝑁) is equal to the gcd of the values comprising the input state ⟨𝑀, 𝑁⟩. This is Metamath 100 proof #69 (greatest common divisor algorithm). (Contributed by Paul Chapman, 31-Mar-2011.) (Proof shortened by Mario Carneiro, 29-May-2014.)
⊢ 𝐸 = (𝑥 ∈ ℕ0, 𝑦 ∈ ℕ0 ↦ if(𝑦 = 0, ⟨𝑥, 𝑦⟩, ⟨𝑦, (𝑥 mod 𝑦)⟩))    &   ⊢ 𝑅 = seq0((𝐸 ∘ 1st ), (ℕ0 × {𝐴}))    &   ⊢ 𝐴 = ⟨𝑀, 𝑁⟩    ⇒   ⊢ ((𝑀 ∈ ℕ0 ∧ 𝑁 ∈ ℕ0) → (1st ‘(𝑅‘𝑁)) = (𝑀 gcd 𝑁))
6.1.11  The least common multiple According to Wikipedia ("Least common multiple", 27-Aug-2020, https://en.wikipedia.org/wiki/Least_common_multiple): "In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a,0) as 0 for all a, which is the result of taking the lcm to be the least upper bound in the lattice of divisibility. ... The lcm of more than two integers is also well-defined: it is the smallest positive integer hat is divisible by each of them." In this section, an operation calculating the least common multiple of two integers (df-lcm 16531) as well as a function mapping a set of integers to their least common multiple (df-lcmf 16532) are provided. Both definitions are valid for all integers, including negative integers and 0, obeying the above mentioned convention. It is shown by lcmfpr 16568 that the two definitions are compatible.
Syntax	clcm 16529	Extend the definition of a class to include the least common multiple operator.
class lcm
Syntax	clcmf 16530	Extend the definition of a class to include the least common multiple function.
class lcm
Definition	df-lcm 16531*	Define the lcm operator. For example, (6 lcm 9) = 18 (ex-lcm 29978). (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 16-Sep-2020.)
⊢ lcm = (𝑥 ∈ ℤ, 𝑦 ∈ ℤ ↦ if((𝑥 = 0 ∨ 𝑦 = 0), 0, inf({𝑛 ∈ ℕ ∣ (𝑥 ∥ 𝑛 ∧ 𝑦 ∥ 𝑛)}, ℝ, < )))
Definition	df-lcmf 16532*	Define the lcm function on a set of integers. (Contributed by AV, 21-Aug-2020.) (Revised by AV, 16-Sep-2020.)
⊢ lcm = (𝑧 ∈ 𝒫 ℤ ↦ if(0 ∈ 𝑧, 0, inf({𝑛 ∈ ℕ ∣ ∀𝑚 ∈ 𝑧 𝑚 ∥ 𝑛}, ℝ, < )))
Theorem	lcmval 16533*	Value of the lcm operator. (𝑀 lcm 𝑁) is the least common multiple of 𝑀 and 𝑁. If either 𝑀 or 𝑁 is 0, the result is defined conventionally as 0. Contrast with df-gcd 16440 and gcdval 16441. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 16-Sep-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 lcm 𝑁) = if((𝑀 = 0 ∨ 𝑁 = 0), 0, inf({𝑛 ∈ ℕ ∣ (𝑀 ∥ 𝑛 ∧ 𝑁 ∥ 𝑛)}, ℝ, < )))
Theorem	lcmcom 16534	The lcm operator is commutative. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 lcm 𝑁) = (𝑁 lcm 𝑀))
Theorem	lcm0val 16535	The value, by convention, of the lcm operator when either operand is 0. (Use lcmcom 16534 for a left-hand 0.) (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ (𝑀 ∈ ℤ → (𝑀 lcm 0) = 0)
Theorem	lcmn0val 16536*	The value of the lcm operator when both operands are nonzero. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 16-Sep-2020.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∨ 𝑁 = 0)) → (𝑀 lcm 𝑁) = inf({𝑛 ∈ ℕ ∣ (𝑀 ∥ 𝑛 ∧ 𝑁 ∥ 𝑛)}, ℝ, < ))
Theorem	lcmcllem 16537*	Lemma for lcmn0cl 16538 and dvdslcm 16539. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∨ 𝑁 = 0)) → (𝑀 lcm 𝑁) ∈ {𝑛 ∈ ℕ ∣ (𝑀 ∥ 𝑛 ∧ 𝑁 ∥ 𝑛)})
Theorem	lcmn0cl 16538	Closure of the lcm operator. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∨ 𝑁 = 0)) → (𝑀 lcm 𝑁) ∈ ℕ)
Theorem	dvdslcm 16539	The lcm of two integers is divisible by each of them. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 ∥ (𝑀 lcm 𝑁) ∧ 𝑁 ∥ (𝑀 lcm 𝑁)))
Theorem	lcmledvds 16540	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.)
⊢ (((𝐾 ∈ ℕ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∨ 𝑁 = 0)) → ((𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾) → (𝑀 lcm 𝑁) ≤ 𝐾))
Theorem	lcmeq0 16541	The lcm of two integers is zero iff either is zero. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 lcm 𝑁) = 0 ↔ (𝑀 = 0 ∨ 𝑁 = 0)))
Theorem	lcmcl 16542	Closure of the lcm operator. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 lcm 𝑁) ∈ ℕ0)
Theorem	gcddvdslcm 16543	The greatest common divisor of two numbers divides their least common multiple. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) ∥ (𝑀 lcm 𝑁))
Theorem	lcmneg 16544	Negating one operand of the lcm operator does not alter the result. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 lcm -𝑁) = (𝑀 lcm 𝑁))
Theorem	neglcm 16545	Negating one operand of the lcm operator does not alter the result. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (-𝑀 lcm 𝑁) = (𝑀 lcm 𝑁))
Theorem	lcmabs 16546	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 16547	Lemma for lcmgcd 16548 and lcmdvds 16549. 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 16548	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 1arith 16864 or of Bézout's identity bezout 16489; see e.g., https://proofwiki.org/wiki/Product_of_GCD_and_LCM 16489 and https://math.stackexchange.com/a/470827 16489. 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 16535 to show it applies when either or both inputs are zero. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 lcm 𝑁) · (𝑀 gcd 𝑁)) = (abs‘(𝑀 · 𝑁)))
Theorem	lcmdvds 16549	The lcm of two integers divides any integer the two divide. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾) → (𝑀 lcm 𝑁) ∥ 𝐾))
Theorem	lcmid 16550	The lcm of an integer and itself is its absolute value. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ (𝑀 ∈ ℤ → (𝑀 lcm 𝑀) = (abs‘𝑀))
Theorem	lcm1 16551	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 16552	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 16553	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 16554	Biconditional form of lcmdvds 16549. (Contributed by Steve Rodriguez, 20-Jan-2020.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 ∥ 𝐾 ∧ 𝑁 ∥ 𝐾) ↔ (𝑀 lcm 𝑁) ∥ 𝐾))
Theorem	lcmass 16555	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 16556	The least common multiple of three and two is six. In contrast to 3lcm2e6 16672, this proof does not use the property of 2 and 3 being prime, therefore it is much longer. (Contributed by Steve Rodriguez, 20-Jan-2020.) (Revised by AV, 27-Aug-2020.) (Proof modification is discouraged.) (New usage is discouraged.)
⊢ (3 lcm 2) = 6
Theorem	6lcm4e12 16557	The least common multiple of six and four is twelve. (Contributed by AV, 27-Aug-2020.)
⊢ (6 lcm 4) = ;12
Theorem	absproddvds 16558*	The absolute value of the product of the elements of a finite subset of the integers is divisible by each element of this subset. (Contributed by AV, 21-Aug-2020.)
⊢ (𝜑 → 𝑍 ⊆ ℤ)    &   ⊢ (𝜑 → 𝑍 ∈ Fin)    &   ⊢ 𝑃 = (abs‘∏𝑧 ∈ 𝑍 𝑧)    ⇒   ⊢ (𝜑 → ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑃)
Theorem	absprodnn 16559*	The absolute value of the product of the elements of a finite subset of the integers not containing 0 is a poitive integer. (Contributed by AV, 21-Aug-2020.)
⊢ (𝜑 → 𝑍 ⊆ ℤ)    &   ⊢ (𝜑 → 𝑍 ∈ Fin)    &   ⊢ 𝑃 = (abs‘∏𝑧 ∈ 𝑍 𝑧)    &   ⊢ (𝜑 → 0 ∉ 𝑍)    ⇒   ⊢ (𝜑 → 𝑃 ∈ ℕ)
Theorem	fissn0dvds 16560*	For each finite subset of the integers not containing 0 there is a positive integer which is divisible by each element of this subset. (Contributed by AV, 21-Aug-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → ∃𝑛 ∈ ℕ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑛)
Theorem	fissn0dvdsn0 16561*	For each finite subset of the integers not containing 0 there is a positive integer which is divisible by each element of this subset. (Contributed by AV, 21-Aug-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → {𝑛 ∈ ℕ ∣ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑛} ≠ ∅)
Theorem	lcmfval 16562*	Value of the lcm function. (lcm‘𝑍) is the least common multiple of the integers contained in the finite subset of integers 𝑍. If at least one of the elements of 𝑍 is 0, the result is defined conventionally as 0. (Contributed by AV, 21-Apr-2020.) (Revised by AV, 16-Sep-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → (lcm‘𝑍) = if(0 ∈ 𝑍, 0, inf({𝑛 ∈ ℕ ∣ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑛}, ℝ, < )))
Theorem	lcmf0val 16563	The value, by convention, of the least common multiple for a set containing 0 is 0. (Contributed by AV, 21-Apr-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 0 ∈ 𝑍) → (lcm‘𝑍) = 0)
Theorem	lcmfn0val 16564*	The value of the lcm function for a set without 0. (Contributed by AV, 21-Aug-2020.) (Revised by AV, 16-Sep-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (lcm‘𝑍) = inf({𝑛 ∈ ℕ ∣ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑛}, ℝ, < ))
Theorem	lcmfnnval 16565*	The value of the lcm function for a subset of the positive integers. (Contributed by AV, 21-Aug-2020.) (Revised by AV, 16-Sep-2020.)
⊢ ((𝑍 ⊆ ℕ ∧ 𝑍 ∈ Fin) → (lcm‘𝑍) = inf({𝑛 ∈ ℕ ∣ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑛}, ℝ, < ))
Theorem	lcmfcllem 16566*	Lemma for lcmfn0cl 16567 and dvdslcmf 16572. (Contributed by AV, 21-Aug-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (lcm‘𝑍) ∈ {𝑛 ∈ ℕ ∣ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑛})
Theorem	lcmfn0cl 16567	Closure of the lcm function. (Contributed by AV, 21-Aug-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → (lcm‘𝑍) ∈ ℕ)
Theorem	lcmfpr 16568	The value of the lcm function for an unordered pair is the value of the lcm operator for both elements. (Contributed by AV, 22-Aug-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (lcm‘{𝑀, 𝑁}) = (𝑀 lcm 𝑁))
Theorem	lcmfcl 16569	Closure of the lcm function. (Contributed by AV, 21-Aug-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → (lcm‘𝑍) ∈ ℕ0)
Theorem	lcmfnncl 16570	Closure of the lcm function. (Contributed by AV, 20-Apr-2020.)
⊢ ((𝑍 ⊆ ℕ ∧ 𝑍 ∈ Fin) → (lcm‘𝑍) ∈ ℕ)
Theorem	lcmfeq0b 16571	The least common multiple of a set of integers is 0 iff at least one of its element is 0. (Contributed by AV, 21-Aug-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → ((lcm‘𝑍) = 0 ↔ 0 ∈ 𝑍))
Theorem	dvdslcmf 16572*	The least common multiple of a set of integers is divisible by each of its elements. (Contributed by AV, 22-Aug-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → ∀𝑥 ∈ 𝑍 𝑥 ∥ (lcm‘𝑍))
Theorem	lcmfledvds 16573*	A positive integer which is divisible by all elements of a set of integers bounds the least common multiple of the set. (Contributed by AV, 22-Aug-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ ((𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍) → ((𝐾 ∈ ℕ ∧ ∀𝑚 ∈ 𝑍 𝑚 ∥ 𝐾) → (lcm‘𝑍) ≤ 𝐾))
Theorem	lcmf 16574*	Characterization of the least common multiple of a set of integers (without 0): A positiven integer is the least common multiple of a set of integers iff it divides each of the elements of the set and every integer which divides each of the elements of the set is greater than or equal to this integer. (Contributed by AV, 22-Aug-2020.)
⊢ ((𝐾 ∈ ℕ ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin ∧ 0 ∉ 𝑍)) → (𝐾 = (lcm‘𝑍) ↔ (∀𝑚 ∈ 𝑍 𝑚 ∥ 𝐾 ∧ ∀𝑘 ∈ ℕ (∀𝑚 ∈ 𝑍 𝑚 ∥ 𝑘 → 𝐾 ≤ 𝑘))))
Theorem	lcmf0 16575	The least common multiple of the empty set is 1. (Contributed by AV, 22-Aug-2020.) (Proof shortened by AV, 16-Sep-2020.)
⊢ (lcm‘∅) = 1
Theorem	lcmfsn 16576	The least common multiple of a singleton is its absolute value. (Contributed by AV, 22-Aug-2020.)
⊢ (𝑀 ∈ ℤ → (lcm‘{𝑀}) = (abs‘𝑀))
Theorem	lcmftp 16577	The least common multiple of a triple of integers is the least common multiple of the third integer and the least common multiple of the first two integers. Although there would be a shorter proof using lcmfunsn 16585, this explicit proof (not based on induction) should be kept. (Proof modification is discouraged.) (Contributed by AV, 23-Aug-2020.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐶 ∈ ℤ) → (lcm‘{𝐴, 𝐵, 𝐶}) = ((𝐴 lcm 𝐵) lcm 𝐶))
Theorem	lcmfunsnlem1 16578*	Lemma for lcmfdvds 16583 and lcmfunsnlem 16582 (Induction step part 1). (Contributed by AV, 25-Aug-2020.)
⊢ (((𝑧 ∈ ℤ ∧ 𝑦 ⊆ ℤ ∧ 𝑦 ∈ Fin) ∧ (∀𝑘 ∈ ℤ (∀𝑚 ∈ 𝑦 𝑚 ∥ 𝑘 → (lcm‘𝑦) ∥ 𝑘) ∧ ∀𝑛 ∈ ℤ (lcm‘(𝑦 ∪ {𝑛})) = ((lcm‘𝑦) lcm 𝑛))) → ∀𝑘 ∈ ℤ (∀𝑚 ∈ (𝑦 ∪ {𝑧})𝑚 ∥ 𝑘 → (lcm‘(𝑦 ∪ {𝑧})) ∥ 𝑘))
Theorem	lcmfunsnlem2lem1 16579*	Lemma 1 for lcmfunsnlem2 16581. (Contributed by AV, 26-Aug-2020.)
⊢ (((0 ∉ 𝑦 ∧ 𝑧 ≠ 0 ∧ 𝑛 ≠ 0) ∧ (𝑛 ∈ ℤ ∧ ((𝑧 ∈ ℤ ∧ 𝑦 ⊆ ℤ ∧ 𝑦 ∈ Fin) ∧ (∀𝑘 ∈ ℤ (∀𝑚 ∈ 𝑦 𝑚 ∥ 𝑘 → (lcm‘𝑦) ∥ 𝑘) ∧ ∀𝑛 ∈ ℤ (lcm‘(𝑦 ∪ {𝑛})) = ((lcm‘𝑦) lcm 𝑛))))) → ∀𝑘 ∈ ℕ (∀𝑖 ∈ ((𝑦 ∪ {𝑧}) ∪ {𝑛})𝑖 ∥ 𝑘 → ((lcm‘(𝑦 ∪ {𝑧})) lcm 𝑛) ≤ 𝑘))
Theorem	lcmfunsnlem2lem2 16580*	Lemma 2 for lcmfunsnlem2 16581. (Contributed by AV, 26-Aug-2020.)
⊢ (((0 ∉ 𝑦 ∧ 𝑧 ≠ 0 ∧ 𝑛 ≠ 0) ∧ (𝑛 ∈ ℤ ∧ ((𝑧 ∈ ℤ ∧ 𝑦 ⊆ ℤ ∧ 𝑦 ∈ Fin) ∧ (∀𝑘 ∈ ℤ (∀𝑚 ∈ 𝑦 𝑚 ∥ 𝑘 → (lcm‘𝑦) ∥ 𝑘) ∧ ∀𝑛 ∈ ℤ (lcm‘(𝑦 ∪ {𝑛})) = ((lcm‘𝑦) lcm 𝑛))))) → (lcm‘((𝑦 ∪ {𝑧}) ∪ {𝑛})) = ((lcm‘(𝑦 ∪ {𝑧})) lcm 𝑛))
Theorem	lcmfunsnlem2 16581*	Lemma for lcmfunsn 16585 and lcmfunsnlem 16582 (Induction step part 2). (Contributed by AV, 26-Aug-2020.)
⊢ (((𝑧 ∈ ℤ ∧ 𝑦 ⊆ ℤ ∧ 𝑦 ∈ Fin) ∧ (∀𝑘 ∈ ℤ (∀𝑚 ∈ 𝑦 𝑚 ∥ 𝑘 → (lcm‘𝑦) ∥ 𝑘) ∧ ∀𝑛 ∈ ℤ (lcm‘(𝑦 ∪ {𝑛})) = ((lcm‘𝑦) lcm 𝑛))) → ∀𝑛 ∈ ℤ (lcm‘((𝑦 ∪ {𝑧}) ∪ {𝑛})) = ((lcm‘(𝑦 ∪ {𝑧})) lcm 𝑛))
Theorem	lcmfunsnlem 16582*	Lemma for lcmfdvds 16583 and lcmfunsn 16585. These two theorems must be proven simultaneously by induction on the cardinality of a finite set 𝑌, because they depend on each other. This can be seen by the two parts lcmfunsnlem1 16578 and lcmfunsnlem2 16581 of the induction step, each of them using both induction hypotheses. (Contributed by AV, 26-Aug-2020.)
⊢ ((𝑌 ⊆ ℤ ∧ 𝑌 ∈ Fin) → (∀𝑘 ∈ ℤ (∀𝑚 ∈ 𝑌 𝑚 ∥ 𝑘 → (lcm‘𝑌) ∥ 𝑘) ∧ ∀𝑛 ∈ ℤ (lcm‘(𝑌 ∪ {𝑛})) = ((lcm‘𝑌) lcm 𝑛)))
Theorem	lcmfdvds 16583*	The least common multiple of a set of integers divides any integer which is divisible by all elements of the set. (Contributed by AV, 26-Aug-2020.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → (∀𝑚 ∈ 𝑍 𝑚 ∥ 𝐾 → (lcm‘𝑍) ∥ 𝐾))
Theorem	lcmfdvdsb 16584*	Biconditional form of lcmfdvds 16583. (Contributed by AV, 26-Aug-2020.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin) → (∀𝑚 ∈ 𝑍 𝑚 ∥ 𝐾 ↔ (lcm‘𝑍) ∥ 𝐾))
Theorem	lcmfunsn 16585	The lcm function for a union of a set of integer and a singleton. (Contributed by AV, 26-Aug-2020.)
⊢ ((𝑌 ⊆ ℤ ∧ 𝑌 ∈ Fin ∧ 𝑁 ∈ ℤ) → (lcm‘(𝑌 ∪ {𝑁})) = ((lcm‘𝑌) lcm 𝑁))
Theorem	lcmfun 16586	The lcm function for a union of sets of integers. (Contributed by AV, 27-Aug-2020.)
⊢ (((𝑌 ⊆ ℤ ∧ 𝑌 ∈ Fin) ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin)) → (lcm‘(𝑌 ∪ 𝑍)) = ((lcm‘𝑌) lcm (lcm‘𝑍)))
Theorem	lcmfass 16587	Associative law for the lcm function. (Contributed by AV, 27-Aug-2020.)
⊢ (((𝑌 ⊆ ℤ ∧ 𝑌 ∈ Fin) ∧ (𝑍 ⊆ ℤ ∧ 𝑍 ∈ Fin)) → (lcm‘({(lcm‘𝑌)} ∪ 𝑍)) = (lcm‘(𝑌 ∪ {(lcm‘𝑍)})))
Theorem	lcmf2a3a4e12 16588	The least common multiple of 2 , 3 and 4 is 12. (Contributed by AV, 27-Aug-2020.)
⊢ (lcm‘{2, 3, 4}) = ;12
Theorem	lcmflefac 16589	The least common multiple of all positive integers less than or equal to an integer is less than or equal to the factorial of the integer. (Contributed by AV, 16-Aug-2020.) (Revised by AV, 27-Aug-2020.)
⊢ (𝑁 ∈ ℕ → (lcm‘(1...𝑁)) ≤ (!‘𝑁))
6.1.12  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 16590. The negation, i.e. two integers are not coprime, can be expressed either by (𝐴 gcd 𝐵) ≠ 1, see ncoprmgcdne1b 16591, or equivalently by 1 < (𝐴 gcd 𝐵), see ncoprmgcdgt1b 16592. A proof of Euclid's lemma based on coprimality is provided in coprmdvds 16594 (see euclemma 16654 for a version of Euclid's lemma for primes).
Theorem	coprmgcdb 16590*	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 16591*	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. See prmdvdsncoprmbd 16667 for a version where the existential quantifier is restricted to primes. (Contributed by AV, 9-Aug-2020.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℕ) → (∃𝑖 ∈ (ℤ≥‘2)(𝑖 ∥ 𝐴 ∧ 𝑖 ∥ 𝐵) ↔ (𝐴 gcd 𝐵) ≠ 1))
Theorem	ncoprmgcdgt1b 16592*	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 16593	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 16594	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. Generalization of euclemma 16654. (Contributed by Paul Chapman, 22-Jun-2011.) (Proof shortened by AV, 10-Jul-2021.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝐾 ∥ (𝑀 · 𝑁) ∧ (𝐾 gcd 𝑀) = 1) → 𝐾 ∥ 𝑁))
Theorem	coprmdvds2 16595	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 16596	One half of rpmulgcd2 16597, which does not need the coprimality assumption. (Contributed by Mario Carneiro, 2-Jul-2015.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝐾 gcd (𝑀 · 𝑁)) ∥ ((𝐾 gcd 𝑀) · (𝐾 gcd 𝑁)))
Theorem	rpmulgcd2 16597	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 16598	Two equal reduced fractions have the same numerator and denominator. (Contributed by Jeff Hankins, 29-Sep-2013.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ ∧ (𝑀 gcd 𝑁) = 1) ∧ (𝑃 ∈ ℤ ∧ 𝑄 ∈ ℕ ∧ (𝑃 gcd 𝑄) = 1) ∧ (𝑀 / 𝑁) = (𝑃 / 𝑄)) → (𝑀 = 𝑃 ∧ 𝑁 = 𝑄))
Theorem	qredeu 16599*	Every rational number has a unique reduced form. (Contributed by Jeff Hankins, 29-Sep-2013.)
⊢ (𝐴 ∈ ℚ → ∃!𝑥 ∈ (ℤ × ℕ)(((1st ‘𝑥) gcd (2nd ‘𝑥)) = 1 ∧ 𝐴 = ((1st ‘𝑥) / (2nd ‘𝑥))))
Theorem	rpmul 16600	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))