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	bitsf1ocnv 16501*	The bits function restricted to nonnegative integers is a bijection from the integers to the finite sets of integers. It is in fact the inverse of the Ackermann bijection ackbijnn 15881. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ ((bits ↾ ℕ0):ℕ0–1-1-onto→(𝒫 ℕ0 ∩ Fin) ∧ ◡(bits ↾ ℕ0) = (𝑥 ∈ (𝒫 ℕ0 ∩ Fin) ↦ Σ𝑛 ∈ 𝑥 (2↑𝑛)))
Theorem	bitsf1o 16502	The bits function restricted to nonnegative integers is a bijection from the integers to the finite sets of integers. It is in fact the inverse of the Ackermann bijection ackbijnn 15881. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ (bits ↾ ℕ0):ℕ0–1-1-onto→(𝒫 ℕ0 ∩ Fin)
Theorem	bitsf1 16503	The bits function is an injection from ℤ to 𝒫 ℕ0. It is obviously not a bijection (by Cantor's theorem canth2 9117), and in fact its range is the set of finite and cofinite subsets of ℕ0. (Contributed by Mario Carneiro, 22-Sep-2016.)
⊢ bits:ℤ–1-1→𝒫 ℕ0
Theorem	2ebits 16504	The bits of a power of two. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ (𝑁 ∈ ℕ0 → (bits‘(2↑𝑁)) = {𝑁})
Theorem	bitsinv 16505*	The inverse of the bits function. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ 𝐾 = ◡(bits ↾ ℕ0)    ⇒   ⊢ (𝐴 ∈ (𝒫 ℕ0 ∩ Fin) → (𝐾‘𝐴) = Σ𝑘 ∈ 𝐴 (2↑𝑘))
Theorem	bitsinvp1 16506	Recursive definition of the inverse of the bits function. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ 𝐾 = ◡(bits ↾ ℕ0)    ⇒   ⊢ ((𝐴 ⊆ ℕ0 ∧ 𝑁 ∈ ℕ0) → (𝐾‘(𝐴 ∩ (0..^(𝑁 + 1)))) = ((𝐾‘(𝐴 ∩ (0..^𝑁))) + if(𝑁 ∈ 𝐴, (2↑𝑁), 0)))
Theorem	sadadd2lem2 16507	The core of the proof of sadadd2 16517. The intuitive justification for this is that cadd is true if at least two arguments are true, and hadd is true if an odd number of arguments are true, so altogether the result is 𝑛 · 𝐴 where 𝑛 is the number of true arguments, which is equivalently obtained by adding together one 𝐴 for each true argument, on the right side. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ (𝐴 ∈ ℂ → (if(hadd(𝜑, 𝜓, 𝜒), 𝐴, 0) + if(cadd(𝜑, 𝜓, 𝜒), (2 · 𝐴), 0)) = ((if(𝜑, 𝐴, 0) + if(𝜓, 𝐴, 0)) + if(𝜒, 𝐴, 0)))
Definition	df-sad 16508*	Define the addition of two bit sequences, using df-had 1622 and df-cad 1635 bit operations. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ sadd = (𝑥 ∈ 𝒫 ℕ0, 𝑦 ∈ 𝒫 ℕ0 ↦ {𝑘 ∈ ℕ0 ∣ hadd(𝑘 ∈ 𝑥, 𝑘 ∈ 𝑦, ∅ ∈ (seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝑥, 𝑚 ∈ 𝑦, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))‘𝑘))})
Theorem	sadfval 16509*	Define the addition of two bit sequences, using df-had 1622 and df-cad 1635 bit operations. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → (𝐴 sadd 𝐵) = {𝑘 ∈ ℕ0 ∣ hadd(𝑘 ∈ 𝐴, 𝑘 ∈ 𝐵, ∅ ∈ (𝐶‘𝑘))})
Theorem	sadcf 16510*	The carry sequence is a sequence of elements of 2o encoding a "sequence of wffs". (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → 𝐶:ℕ0⟶2o)
Theorem	sadc0 16511*	The initial element of the carry sequence is ⊥. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → ¬ ∅ ∈ (𝐶‘0))
Theorem	sadcp1 16512*	The carry sequence (which is a sequence of wffs, encoded as 1o and ∅) is defined recursively as the carry operation applied to the previous carry and the two current inputs. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (∅ ∈ (𝐶‘(𝑁 + 1)) ↔ cadd(𝑁 ∈ 𝐴, 𝑁 ∈ 𝐵, ∅ ∈ (𝐶‘𝑁))))
Theorem	sadval 16513*	The full adder sequence is the half adder function applied to the inputs and the carry sequence. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (𝑁 ∈ (𝐴 sadd 𝐵) ↔ hadd(𝑁 ∈ 𝐴, 𝑁 ∈ 𝐵, ∅ ∈ (𝐶‘𝑁))))
Theorem	sadcaddlem 16514*	Lemma for sadcadd 16515. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ 𝐾 = ◡(bits ↾ ℕ0)    &   ⊢ (𝜑 → (∅ ∈ (𝐶‘𝑁) ↔ (2↑𝑁) ≤ ((𝐾‘(𝐴 ∩ (0..^𝑁))) + (𝐾‘(𝐵 ∩ (0..^𝑁))))))    ⇒   ⊢ (𝜑 → (∅ ∈ (𝐶‘(𝑁 + 1)) ↔ (2↑(𝑁 + 1)) ≤ ((𝐾‘(𝐴 ∩ (0..^(𝑁 + 1)))) + (𝐾‘(𝐵 ∩ (0..^(𝑁 + 1)))))))
Theorem	sadcadd 16515*	Non-recursive definition of the carry sequence. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ 𝐾 = ◡(bits ↾ ℕ0)    ⇒   ⊢ (𝜑 → (∅ ∈ (𝐶‘𝑁) ↔ (2↑𝑁) ≤ ((𝐾‘(𝐴 ∩ (0..^𝑁))) + (𝐾‘(𝐵 ∩ (0..^𝑁))))))
Theorem	sadadd2lem 16516*	Lemma for sadadd2 16517. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ 𝐾 = ◡(bits ↾ ℕ0)    &   ⊢ (𝜑 → ((𝐾‘((𝐴 sadd 𝐵) ∩ (0..^𝑁))) + if(∅ ∈ (𝐶‘𝑁), (2↑𝑁), 0)) = ((𝐾‘(𝐴 ∩ (0..^𝑁))) + (𝐾‘(𝐵 ∩ (0..^𝑁)))))    ⇒   ⊢ (𝜑 → ((𝐾‘((𝐴 sadd 𝐵) ∩ (0..^(𝑁 + 1)))) + if(∅ ∈ (𝐶‘(𝑁 + 1)), (2↑(𝑁 + 1)), 0)) = ((𝐾‘(𝐴 ∩ (0..^(𝑁 + 1)))) + (𝐾‘(𝐵 ∩ (0..^(𝑁 + 1))))))
Theorem	sadadd2 16517*	Sum of initial segments of the sadd sequence. (Contributed by Mario Carneiro, 8-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ 𝐾 = ◡(bits ↾ ℕ0)    ⇒   ⊢ (𝜑 → ((𝐾‘((𝐴 sadd 𝐵) ∩ (0..^𝑁))) + if(∅ ∈ (𝐶‘𝑁), (2↑𝑁), 0)) = ((𝐾‘(𝐴 ∩ (0..^𝑁))) + (𝐾‘(𝐵 ∩ (0..^𝑁)))))
Theorem	sadadd3 16518*	Sum of initial segments of the sadd sequence. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ 𝐾 = ◡(bits ↾ ℕ0)    ⇒   ⊢ (𝜑 → ((𝐾‘((𝐴 sadd 𝐵) ∩ (0..^𝑁))) mod (2↑𝑁)) = (((𝐾‘(𝐴 ∩ (0..^𝑁))) + (𝐾‘(𝐵 ∩ (0..^𝑁)))) mod (2↑𝑁)))
Theorem	sadcl 16519	The sum of two sequences is a sequence. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ ((𝐴 ⊆ ℕ0 ∧ 𝐵 ⊆ ℕ0) → (𝐴 sadd 𝐵) ⊆ ℕ0)
Theorem	sadcom 16520	The adder sequence function is commutative. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ ((𝐴 ⊆ ℕ0 ∧ 𝐵 ⊆ ℕ0) → (𝐴 sadd 𝐵) = (𝐵 sadd 𝐴))
Theorem	saddisjlem 16521*	Lemma for sadadd 16524. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → (𝐴 ∩ 𝐵) = ∅)    &   ⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ 𝐴, 𝑚 ∈ 𝐵, ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (𝑁 ∈ (𝐴 sadd 𝐵) ↔ 𝑁 ∈ (𝐴 ∪ 𝐵)))
Theorem	saddisj 16522	The sum of disjoint sequences is the union of the sequences. (In this case, there are no carried bits.) (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → (𝐴 ∩ 𝐵) = ∅)    ⇒   ⊢ (𝜑 → (𝐴 sadd 𝐵) = (𝐴 ∪ 𝐵))
Theorem	sadaddlem 16523*	Lemma for sadadd 16524. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ 𝐶 = seq0((𝑐 ∈ 2o, 𝑚 ∈ ℕ0 ↦ if(cadd(𝑚 ∈ (bits‘𝐴), 𝑚 ∈ (bits‘𝐵), ∅ ∈ 𝑐), 1o, ∅)), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ 𝐾 = ◡(bits ↾ ℕ0)    &   ⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℤ)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (((bits‘𝐴) sadd (bits‘𝐵)) ∩ (0..^𝑁)) = (bits‘((𝐴 + 𝐵) mod (2↑𝑁))))
Theorem	sadadd 16524	For sequences that correspond to valid integers, the adder sequence function produces the sequence for the sum. This is effectively a proof of the correctness of the ripple carry adder, implemented with logic gates corresponding to df-had 1622 and df-cad 1635. It is interesting to consider in what sense the sadd function can be said to be "adding" things outside the range of the bits function, that is, when adding sequences that are not eventually constant and so do not denote any integer. The correct interpretation is that the sequences are representations of 2-adic integers, which have a natural ring structure. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((bits‘𝐴) sadd (bits‘𝐵)) = (bits‘(𝐴 + 𝐵)))
Theorem	sadid1 16525	The adder sequence function has a left identity, the empty set, which is the representation of the integer zero. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝐴 ⊆ ℕ0 → (𝐴 sadd ∅) = 𝐴)
Theorem	sadid2 16526	The adder sequence function has a right identity, the empty set, which is the representation of the integer zero. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝐴 ⊆ ℕ0 → (∅ sadd 𝐴) = 𝐴)
Theorem	sadasslem 16527	Lemma for sadass 16528. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐶 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (((𝐴 sadd 𝐵) sadd 𝐶) ∩ (0..^𝑁)) = ((𝐴 sadd (𝐵 sadd 𝐶)) ∩ (0..^𝑁)))
Theorem	sadass 16528	Sequence addition is associative. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ ((𝐴 ⊆ ℕ0 ∧ 𝐵 ⊆ ℕ0 ∧ 𝐶 ⊆ ℕ0) → ((𝐴 sadd 𝐵) sadd 𝐶) = (𝐴 sadd (𝐵 sadd 𝐶)))
Theorem	sadeq 16529	Any element of a sequence sum only depends on the values of the argument sequences up to and including that point. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → ((𝐴 sadd 𝐵) ∩ (0..^𝑁)) = (((𝐴 ∩ (0..^𝑁)) sadd (𝐵 ∩ (0..^𝑁))) ∩ (0..^𝑁)))
Theorem	bitsres 16530	Restrict the bits of a number to an upper integer set. (Contributed by Mario Carneiro, 5-Sep-2016.)
⊢ ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ0) → ((bits‘𝐴) ∩ (ℤ≥‘𝑁)) = (bits‘((⌊‘(𝐴 / (2↑𝑁))) · (2↑𝑁))))
Theorem	bitsuz 16531	The bits of a number are all at least 𝑁 iff the number is divisible by 2↑𝑁. (Contributed by Mario Carneiro, 21-Sep-2016.)
⊢ ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ0) → ((2↑𝑁) ∥ 𝐴 ↔ (bits‘𝐴) ⊆ (ℤ≥‘𝑁)))
Theorem	bitsshft 16532*	Shifting a bit sequence to the left (toward the more significant bits) causes the number to be multiplied by a power of two. (Contributed by Mario Carneiro, 22-Sep-2016.)
⊢ ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ0) → {𝑛 ∈ ℕ0 ∣ (𝑛 − 𝑁) ∈ (bits‘𝐴)} = (bits‘(𝐴 · (2↑𝑁))))
Definition	df-smu 16533*	Define the multiplication of two bit sequences, using repeated sequence addition. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ smul = (𝑥 ∈ 𝒫 ℕ0, 𝑦 ∈ 𝒫 ℕ0 ↦ {𝑘 ∈ ℕ0 ∣ 𝑘 ∈ (seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝑥 ∧ (𝑛 − 𝑚) ∈ 𝑦)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))‘(𝑘 + 1))})
Theorem	smufval 16534*	The multiplication of two bit sequences as repeated sequence addition. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → (𝐴 smul 𝐵) = {𝑘 ∈ ℕ0 ∣ 𝑘 ∈ (𝑃‘(𝑘 + 1))})
Theorem	smupf 16535*	The sequence of partial sums of the sequence multiplication. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → 𝑃:ℕ0⟶𝒫 ℕ0)
Theorem	smup0 16536*	The initial element of the partial sum sequence. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → (𝑃‘0) = ∅)
Theorem	smupp1 16537*	The initial element of the partial sum sequence. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (𝑃‘(𝑁 + 1)) = ((𝑃‘𝑁) sadd {𝑛 ∈ ℕ0 ∣ (𝑁 ∈ 𝐴 ∧ (𝑛 − 𝑁) ∈ 𝐵)}))
Theorem	smuval 16538*	Define the addition of two bit sequences, using df-had 1622 and df-cad 1635 bit operations. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (𝑁 ∈ (𝐴 smul 𝐵) ↔ 𝑁 ∈ (𝑃‘(𝑁 + 1))))
Theorem	smuval2 16539*	The partial sum sequence stabilizes at 𝑁 after the 𝑁 + 1-th element of the sequence; this stable value is the value of the sequence multiplication. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ (𝜑 → 𝑀 ∈ (ℤ≥‘(𝑁 + 1)))    ⇒   ⊢ (𝜑 → (𝑁 ∈ (𝐴 smul 𝐵) ↔ 𝑁 ∈ (𝑃‘𝑀)))
Theorem	smupvallem 16540*	If 𝐴 only has elements less than 𝑁, then all elements of the partial sum sequence past 𝑁 already equal the final value. (Contributed by Mario Carneiro, 20-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ (𝜑 → 𝐴 ⊆ (0..^𝑁))    &   ⊢ (𝜑 → 𝑀 ∈ (ℤ≥‘𝑁))    ⇒   ⊢ (𝜑 → (𝑃‘𝑀) = (𝐴 smul 𝐵))
Theorem	smucl 16541	The product of two sequences is a sequence. (Contributed by Mario Carneiro, 19-Sep-2016.)
⊢ ((𝐴 ⊆ ℕ0 ∧ 𝐵 ⊆ ℕ0) → (𝐴 smul 𝐵) ⊆ ℕ0)
Theorem	smu01lem 16542*	Lemma for smu01 16543 and smu02 16544. (Contributed by Mario Carneiro, 19-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ ((𝜑 ∧ (𝑘 ∈ ℕ0 ∧ 𝑛 ∈ ℕ0)) → ¬ (𝑘 ∈ 𝐴 ∧ (𝑛 − 𝑘) ∈ 𝐵))    ⇒   ⊢ (𝜑 → (𝐴 smul 𝐵) = ∅)
Theorem	smu01 16543	Multiplication of a sequence by 0 on the right. (Contributed by Mario Carneiro, 19-Sep-2016.)
⊢ (𝐴 ⊆ ℕ0 → (𝐴 smul ∅) = ∅)
Theorem	smu02 16544	Multiplication of a sequence by 0 on the left. (Contributed by Mario Carneiro, 9-Sep-2016.)
⊢ (𝐴 ⊆ ℕ0 → (∅ smul 𝐴) = ∅)
Theorem	smupval 16545*	Rewrite the elements of the partial sum sequence in terms of sequence multiplication. (Contributed by Mario Carneiro, 20-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (𝑃‘𝑁) = ((𝐴 ∩ (0..^𝑁)) smul 𝐵))
Theorem	smup1 16546*	Rewrite smupp1 16537 using only smul instead of the internal recursive function 𝑃. (Contributed by Mario Carneiro, 20-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → ((𝐴 ∩ (0..^(𝑁 + 1))) smul 𝐵) = (((𝐴 ∩ (0..^𝑁)) smul 𝐵) sadd {𝑛 ∈ ℕ0 ∣ (𝑁 ∈ 𝐴 ∧ (𝑛 − 𝑁) ∈ 𝐵)}))
Theorem	smueqlem 16547*	Any element of a sequence multiplication only depends on the values of the argument sequences up to and including that point. (Contributed by Mario Carneiro, 20-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    &   ⊢ 𝑃 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ 𝐵)})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    &   ⊢ 𝑄 = seq0((𝑝 ∈ 𝒫 ℕ0, 𝑚 ∈ ℕ0 ↦ (𝑝 sadd {𝑛 ∈ ℕ0 ∣ (𝑚 ∈ 𝐴 ∧ (𝑛 − 𝑚) ∈ (𝐵 ∩ (0..^𝑁)))})), (𝑛 ∈ ℕ0 ↦ if(𝑛 = 0, ∅, (𝑛 − 1))))    ⇒   ⊢ (𝜑 → ((𝐴 smul 𝐵) ∩ (0..^𝑁)) = (((𝐴 ∩ (0..^𝑁)) smul (𝐵 ∩ (0..^𝑁))) ∩ (0..^𝑁)))
Theorem	smueq 16548	Any element of a sequence multiplication only depends on the values of the argument sequences up to and including that point. (Contributed by Mario Carneiro, 20-Sep-2016.)
⊢ (𝜑 → 𝐴 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝐵 ⊆ ℕ0)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → ((𝐴 smul 𝐵) ∩ (0..^𝑁)) = (((𝐴 ∩ (0..^𝑁)) smul (𝐵 ∩ (0..^𝑁))) ∩ (0..^𝑁)))
Theorem	smumullem 16549	Lemma for smumul 16550. (Contributed by Mario Carneiro, 22-Sep-2016.)
⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℤ)    &   ⊢ (𝜑 → 𝑁 ∈ ℕ0)    ⇒   ⊢ (𝜑 → (((bits‘𝐴) ∩ (0..^𝑁)) smul (bits‘𝐵)) = (bits‘((𝐴 mod (2↑𝑁)) · 𝐵)))
Theorem	smumul 16550	For sequences that correspond to valid integers, the sequence multiplication function produces the sequence for the product. This is effectively a proof of the correctness of the multiplication process, implemented in terms of logic gates for df-sad 16508, whose correctness is verified in sadadd 16524. Outside this range, the sequences cannot be representing integers, but the smul function still "works". This extended function is best interpreted in terms of the ring structure of the 2-adic integers. (Contributed by Mario Carneiro, 22-Sep-2016.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((bits‘𝐴) smul (bits‘𝐵)) = (bits‘(𝐴 · 𝐵)))
6.1.7  The greatest common divisor operator
Syntax	cgcd 16551	Extend the definition of a class to include the greatest common divisor operator.
class gcd
Definition	df-gcd 16552*	Define the gcd operator. For example, (-6 gcd 9) = 3 (ex-gcd 30774). For an alternate definition, based on the definition in [ApostolNT] p. 15, see dfgcd2 16603. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ gcd = (𝑥 ∈ ℤ, 𝑦 ∈ ℤ ↦ if((𝑥 = 0 ∧ 𝑦 = 0), 0, sup({𝑛 ∈ ℤ ∣ (𝑛 ∥ 𝑥 ∧ 𝑛 ∥ 𝑦)}, ℝ, < )))
Theorem	gcdval 16553*	The value of the gcd operator. (𝑀 gcd 𝑁) is the greatest common divisor of 𝑀 and 𝑁. If 𝑀 and 𝑁 are both 0, the result is defined conventionally as 0. (Contributed by Paul Chapman, 21-Mar-2011.) (Revised by Mario Carneiro, 10-Nov-2013.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) = if((𝑀 = 0 ∧ 𝑁 = 0), 0, sup({𝑛 ∈ ℤ ∣ (𝑛 ∥ 𝑀 ∧ 𝑛 ∥ 𝑁)}, ℝ, < )))
Theorem	gcd0val 16554	The value, by convention, of the gcd operator when both operands are 0. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ (0 gcd 0) = 0
Theorem	gcdn0val 16555*	The value of the gcd operator when at least one operand is nonzero. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∧ 𝑁 = 0)) → (𝑀 gcd 𝑁) = sup({𝑛 ∈ ℤ ∣ (𝑛 ∥ 𝑀 ∧ 𝑛 ∥ 𝑁)}, ℝ, < ))
Theorem	gcdcllem1 16556*	Lemma for gcdn0cl 16559, gcddvds 16560 and dvdslegcd 16561. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ 𝑆 = {𝑧 ∈ ℤ ∣ ∀𝑛 ∈ 𝐴 𝑧 ∥ 𝑛}    ⇒   ⊢ ((𝐴 ⊆ ℤ ∧ ∃𝑛 ∈ 𝐴 𝑛 ≠ 0) → (𝑆 ≠ ∅ ∧ ∃𝑥 ∈ ℤ ∀𝑦 ∈ 𝑆 𝑦 ≤ 𝑥))
Theorem	gcdcllem2 16557*	Lemma for gcdn0cl 16559, gcddvds 16560 and dvdslegcd 16561. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ 𝑆 = {𝑧 ∈ ℤ ∣ ∀𝑛 ∈ {𝑀, 𝑁}𝑧 ∥ 𝑛}    &   ⊢ 𝑅 = {𝑧 ∈ ℤ ∣ (𝑧 ∥ 𝑀 ∧ 𝑧 ∥ 𝑁)}    ⇒   ⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → 𝑅 = 𝑆)
Theorem	gcdcllem3 16558*	Lemma for gcdn0cl 16559, gcddvds 16560 and dvdslegcd 16561. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ 𝑆 = {𝑧 ∈ ℤ ∣ ∀𝑛 ∈ {𝑀, 𝑁}𝑧 ∥ 𝑛}    &   ⊢ 𝑅 = {𝑧 ∈ ℤ ∣ (𝑧 ∥ 𝑀 ∧ 𝑧 ∥ 𝑁)}    ⇒   ⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∧ 𝑁 = 0)) → (sup(𝑅, ℝ, < ) ∈ ℕ ∧ (sup(𝑅, ℝ, < ) ∥ 𝑀 ∧ sup(𝑅, ℝ, < ) ∥ 𝑁) ∧ ((𝐾 ∈ ℤ ∧ 𝐾 ∥ 𝑀 ∧ 𝐾 ∥ 𝑁) → 𝐾 ≤ sup(𝑅, ℝ, < ))))
Theorem	gcdn0cl 16559	Closure of the gcd operator. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ (((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∧ 𝑁 = 0)) → (𝑀 gcd 𝑁) ∈ ℕ)
Theorem	gcddvds 16560	The gcd of two integers divides each of them. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 gcd 𝑁) ∥ 𝑀 ∧ (𝑀 gcd 𝑁) ∥ 𝑁))
Theorem	dvdslegcd 16561	An integer which divides both operands of the gcd operator is bounded by it. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ (((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑀 = 0 ∧ 𝑁 = 0)) → ((𝐾 ∥ 𝑀 ∧ 𝐾 ∥ 𝑁) → 𝐾 ≤ (𝑀 gcd 𝑁)))
Theorem	nndvdslegcd 16562	A positive integer which divides both positive operands of the gcd operator is bounded by it. (Contributed by AV, 9-Aug-2020.)
⊢ ((𝐾 ∈ ℕ ∧ 𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((𝐾 ∥ 𝑀 ∧ 𝐾 ∥ 𝑁) → 𝐾 ≤ (𝑀 gcd 𝑁)))
Theorem	gcdcl 16563	Closure of the gcd operator. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) ∈ ℕ0)
Theorem	gcdnncl 16564	Closure of the gcd operator. (Contributed by Thierry Arnoux, 2-Feb-2020.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → (𝑀 gcd 𝑁) ∈ ℕ)
Theorem	gcdcld 16565	Closure of the gcd operator. (Contributed by Mario Carneiro, 29-May-2016.)
⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝑁 ∈ ℤ)    ⇒   ⊢ (𝜑 → (𝑀 gcd 𝑁) ∈ ℕ0)
Theorem	gcd2n0cl 16566	Closure of the gcd operator if the second operand is not 0. (Contributed by AV, 10-Jul-2021.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝑁 ≠ 0) → (𝑀 gcd 𝑁) ∈ ℕ)
Theorem	zeqzmulgcd 16567*	An integer is the product of an integer and the gcd of it and another integer. (Contributed by AV, 11-Jul-2021.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ∃𝑛 ∈ ℤ 𝐴 = (𝑛 · (𝐴 gcd 𝐵)))
Theorem	divgcdz 16568	An integer divided by the gcd of it and a nonzero integer is an integer. (Contributed by AV, 11-Jul-2021.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝐵 ≠ 0) → (𝐴 / (𝐴 gcd 𝐵)) ∈ ℤ)
Theorem	gcdf 16569	Domain and codomain of the gcd operator. (Contributed by Paul Chapman, 31-Mar-2011.) (Revised by Mario Carneiro, 16-Nov-2013.)
⊢ gcd :(ℤ × ℤ)⟶ℕ0
Theorem	gcdcom 16570	The gcd operator is commutative. Theorem 1.4(a) in [ApostolNT] p. 16. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) = (𝑁 gcd 𝑀))
Theorem	gcdcomd 16571	The gcd operator is commutative, deduction version. (Contributed by SN, 24-Aug-2024.)
⊢ (𝜑 → 𝑀 ∈ ℤ)    &   ⊢ (𝜑 → 𝑁 ∈ ℤ)    ⇒   ⊢ (𝜑 → (𝑀 gcd 𝑁) = (𝑁 gcd 𝑀))
Theorem	divgcdnn 16572	A positive integer divided by the gcd of it and another integer is a positive integer. (Contributed by AV, 10-Jul-2021.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℤ) → (𝐴 / (𝐴 gcd 𝐵)) ∈ ℕ)
Theorem	divgcdnnr 16573	A positive integer divided by the gcd of it and another integer is a positive integer. (Contributed by AV, 10-Jul-2021.)
⊢ ((𝐴 ∈ ℕ ∧ 𝐵 ∈ ℤ) → (𝐴 / (𝐵 gcd 𝐴)) ∈ ℕ)
Theorem	gcdeq0 16574	The gcd of two integers is zero iff they are both zero. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑀 gcd 𝑁) = 0 ↔ (𝑀 = 0 ∧ 𝑁 = 0)))
Theorem	gcdn0gt0 16575	The gcd of two integers is positive (nonzero) iff they are not both zero. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (¬ (𝑀 = 0 ∧ 𝑁 = 0) ↔ 0 < (𝑀 gcd 𝑁)))
Theorem	gcd0id 16576	The gcd of 0 and an integer is the integer's absolute value. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ (𝑁 ∈ ℤ → (0 gcd 𝑁) = (abs‘𝑁))
Theorem	gcdid0 16577	The gcd of an integer and 0 is the integer's absolute value. Theorem 1.4(d)2 in [ApostolNT] p. 16. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ (𝑁 ∈ ℤ → (𝑁 gcd 0) = (abs‘𝑁))
Theorem	nn0gcdid0 16578	The gcd of a nonnegative integer with 0 is itself. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ (𝑁 ∈ ℕ0 → (𝑁 gcd 0) = 𝑁)
Theorem	gcdneg 16579	Negating one operand of the gcd operator does not alter the result. (Contributed by Paul Chapman, 21-Mar-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd -𝑁) = (𝑀 gcd 𝑁))
Theorem	neggcd 16580	Negating one operand of the gcd operator does not alter the result. (Contributed by Paul Chapman, 22-Jun-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (-𝑀 gcd 𝑁) = (𝑀 gcd 𝑁))
Theorem	gcdaddmlem 16581	Lemma for gcdaddm 16582. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ 𝐾 ∈ ℤ    &   ⊢ 𝑀 ∈ ℤ    &   ⊢ 𝑁 ∈ ℤ    ⇒   ⊢ (𝑀 gcd 𝑁) = (𝑀 gcd ((𝐾 · 𝑀) + 𝑁))
Theorem	gcdaddm 16582	Adding a multiple of one operand of the gcd operator to the other does not alter the result. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ ((𝐾 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) = (𝑀 gcd (𝑁 + (𝐾 · 𝑀))))
Theorem	gcdadd 16583	The GCD of two numbers is the same as the GCD of the left and their sum. (Contributed by Scott Fenton, 20-Apr-2014.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd 𝑁) = (𝑀 gcd (𝑁 + 𝑀)))
Theorem	gcdid 16584	The gcd of a number and itself is its absolute value. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ (𝑁 ∈ ℤ → (𝑁 gcd 𝑁) = (abs‘𝑁))
Theorem	gcd1 16585	The gcd of a number with 1 is 1. Theorem 1.4(d)1 in [ApostolNT] p. 16. (Contributed by Mario Carneiro, 19-Feb-2014.)
⊢ (𝑀 ∈ ℤ → (𝑀 gcd 1) = 1)
Theorem	gcdabs1 16586	gcd of the absolute value of the first operator. (Contributed by Scott Fenton, 2-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℤ) → ((abs‘𝑁) gcd 𝑀) = (𝑁 gcd 𝑀))
Theorem	gcdabs2 16587	gcd of the absolute value of the second operator. (Contributed by Scott Fenton, 2-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℤ) → (𝑁 gcd (abs‘𝑀)) = (𝑁 gcd 𝑀))
Theorem	gcdabs 16588	The gcd of two integers is the same as that of their absolute values. (Contributed by Paul Chapman, 31-Mar-2011.) (Proof shortened by SN, 15-Sep-2024.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((abs‘𝑀) gcd (abs‘𝑁)) = (𝑀 gcd 𝑁))
Theorem	modgcd 16589	The gcd remains unchanged if one operand is replaced with its remainder modulo the other. (Contributed by Paul Chapman, 31-Mar-2011.)
⊢ ((𝑀 ∈ ℤ ∧ 𝑁 ∈ ℕ) → ((𝑀 mod 𝑁) gcd 𝑁) = (𝑀 gcd 𝑁))
Theorem	1gcd 16590	The GCD of one and an integer is one. (Contributed by Scott Fenton, 17-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.)
⊢ (𝑀 ∈ ℤ → (1 gcd 𝑀) = 1)
Theorem	gcdmultipled 16591	The greatest common divisor of a nonnegative integer 𝑀 and a multiple of it is 𝑀 itself. (Contributed by Rohan Ridenour, 3-Aug-2023.)
⊢ (𝜑 → 𝑀 ∈ ℕ0)    &   ⊢ (𝜑 → 𝑁 ∈ ℤ)    ⇒   ⊢ (𝜑 → (𝑀 gcd (𝑁 · 𝑀)) = 𝑀)
Theorem	gcdmultiplez 16592	The GCD of a multiple of an integer is the integer itself. (Contributed by Scott Fenton, 18-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.) (Proof shortened by AV, 12-Jan-2023.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℤ) → (𝑀 gcd (𝑀 · 𝑁)) = 𝑀)
Theorem	gcdmultiple 16593	The GCD of a multiple of a positive integer is the positive integer itself. (Contributed by Scott Fenton, 12-Apr-2014.) (Revised by Mario Carneiro, 19-Apr-2014.) (Proof shortened by AV, 12-Jan-2023.)
⊢ ((𝑀 ∈ ℕ ∧ 𝑁 ∈ ℕ) → (𝑀 gcd (𝑀 · 𝑁)) = 𝑀)
Theorem	dvdsgcdidd 16594	The greatest common divisor of a positive integer and another integer it divides is itself. (Contributed by Rohan Ridenour, 3-Aug-2023.)
⊢ (𝜑 → 𝑀 ∈ ℕ)    &   ⊢ (𝜑 → 𝑁 ∈ ℤ)    &   ⊢ (𝜑 → 𝑀 ∥ 𝑁)    ⇒   ⊢ (𝜑 → (𝑀 gcd 𝑁) = 𝑀)
Theorem	6gcd4e2 16595	The greatest common divisor of six and four is two. To calculate this gcd, a simple form of Euclid's algorithm is used: (6 gcd 4) = ((4 + 2) gcd 4) = (2 gcd 4) and (2 gcd 4) = (2 gcd (2 + 2)) = (2 gcd 2) = 2. (Contributed by AV, 27-Aug-2020.)
⊢ (6 gcd 4) = 2
6.1.8  Bézout's identity
Theorem	bezoutlem1 16596*	Lemma for bezout 16600. (Contributed by Mario Carneiro, 15-Mar-2014.)
⊢ 𝑀 = {𝑧 ∈ ℕ ∣ ∃𝑥 ∈ ℤ ∃𝑦 ∈ ℤ 𝑧 = ((𝐴 · 𝑥) + (𝐵 · 𝑦))}    &   ⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℤ)    ⇒   ⊢ (𝜑 → (𝐴 ≠ 0 → (abs‘𝐴) ∈ 𝑀))
Theorem	bezoutlem2 16597*	Lemma for bezout 16600. (Contributed by Mario Carneiro, 15-Mar-2014.) ( Revised by AV, 30-Sep-2020.)
⊢ 𝑀 = {𝑧 ∈ ℕ ∣ ∃𝑥 ∈ ℤ ∃𝑦 ∈ ℤ 𝑧 = ((𝐴 · 𝑥) + (𝐵 · 𝑦))}    &   ⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℤ)    &   ⊢ 𝐺 = inf(𝑀, ℝ, < )    &   ⊢ (𝜑 → ¬ (𝐴 = 0 ∧ 𝐵 = 0))    ⇒   ⊢ (𝜑 → 𝐺 ∈ 𝑀)
Theorem	bezoutlem3 16598*	Lemma for bezout 16600. (Contributed by Mario Carneiro, 22-Feb-2014.) ( Revised by AV, 30-Sep-2020.)
⊢ 𝑀 = {𝑧 ∈ ℕ ∣ ∃𝑥 ∈ ℤ ∃𝑦 ∈ ℤ 𝑧 = ((𝐴 · 𝑥) + (𝐵 · 𝑦))}    &   ⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℤ)    &   ⊢ 𝐺 = inf(𝑀, ℝ, < )    &   ⊢ (𝜑 → ¬ (𝐴 = 0 ∧ 𝐵 = 0))    ⇒   ⊢ (𝜑 → (𝐶 ∈ 𝑀 → 𝐺 ∥ 𝐶))
Theorem	bezoutlem4 16599*	Lemma for bezout 16600. (Contributed by Mario Carneiro, 22-Feb-2014.)
⊢ 𝑀 = {𝑧 ∈ ℕ ∣ ∃𝑥 ∈ ℤ ∃𝑦 ∈ ℤ 𝑧 = ((𝐴 · 𝑥) + (𝐵 · 𝑦))}    &   ⊢ (𝜑 → 𝐴 ∈ ℤ)    &   ⊢ (𝜑 → 𝐵 ∈ ℤ)    &   ⊢ 𝐺 = inf(𝑀, ℝ, < )    &   ⊢ (𝜑 → ¬ (𝐴 = 0 ∧ 𝐵 = 0))    ⇒   ⊢ (𝜑 → (𝐴 gcd 𝐵) ∈ 𝑀)
Theorem	bezout 16600*	Bézout's identity: For any integers 𝐴 and 𝐵, there are integers 𝑥, 𝑦 such that (𝐴 gcd 𝐵) = 𝐴 · 𝑥 + 𝐵 · 𝑦. This is Metamath 100 proof #60. (Contributed by Mario Carneiro, 22-Feb-2014.)
⊢ ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ∃𝑥 ∈ ℤ ∃𝑦 ∈ ℤ (𝐴 gcd 𝐵) = ((𝐴 · 𝑥) + (𝐵 · 𝑦)))