lcmgcd

Description: 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 valueis 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 1arith or of Bézout's identity bezout ; see e.g., https://proofwiki.org/wiki/Product_of_GCD_and_LCM and https://math.stackexchange.com/a/470827 . 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 to show it applies when either or both inputs are zero. (Contributed by Steve Rodriguez, 20-Jan-2020)

		Ref	Expression
	Assertion	lcmgcd	$⊢ (M \in ℤ \land N \in ℤ) \to (M lcm N) (M \gcd N) = \|M \cdot N\|$

Proof

Step	Hyp	Ref	Expression
1		gcdcl	$⊢ (M \in ℤ \land N \in ℤ) \to M \gcd N \in ℕ_{0}$
2	1	nn0cnd	$⊢ (M \in ℤ \land N \in ℤ) \to M \gcd N \in ℂ$
3	2	mul02d	$⊢ (M \in ℤ \land N \in ℤ) \to 0 \cdot (M \gcd N) = 0$
4		0z	$⊢ 0 \in ℤ$
5		lcmcom	$⊢ (N \in ℤ \land 0 \in ℤ) \to N lcm 0 = 0 lcm N$
6	4 5	mpan2	$⊢ N \in ℤ \to N lcm 0 = 0 lcm N$
7		lcm0val	$⊢ N \in ℤ \to N lcm 0 = 0$
8	6 7	eqtr3d	$⊢ N \in ℤ \to 0 lcm N = 0$
9	8	adantl	$⊢ (M \in ℤ \land N \in ℤ) \to 0 lcm N = 0$
10	9	oveq1d	$⊢ (M \in ℤ \land N \in ℤ) \to (0 lcm N) (M \gcd N) = 0 \cdot (M \gcd N)$
11		zcn	$⊢ N \in ℤ \to N \in ℂ$
12	11	adantl	$⊢ (M \in ℤ \land N \in ℤ) \to N \in ℂ$
13	12	mul02d	$⊢ (M \in ℤ \land N \in ℤ) \to 0 \cdot N = 0$
14	13	abs00bd	$⊢ (M \in ℤ \land N \in ℤ) \to \|0 \cdot N\| = 0$
15	3 10 14	3eqtr4d	$⊢ (M \in ℤ \land N \in ℤ) \to (0 lcm N) (M \gcd N) = \|0 \cdot N\|$
16	15	adantr	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to (0 lcm N) (M \gcd N) = \|0 \cdot N\|$
17		simpr	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to M = 0$
18	17	oveq1d	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to M lcm N = 0 lcm N$
19	18	oveq1d	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to (M lcm N) (M \gcd N) = (0 lcm N) (M \gcd N)$
20	17	oveq1d	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to M \cdot N = 0 \cdot N$
21	20	fveq2d	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to \|M \cdot N\| = \|0 \cdot N\|$
22	16 19 21	3eqtr4d	$⊢ ((M \in ℤ \land N \in ℤ) \land M = 0) \to (M lcm N) (M \gcd N) = \|M \cdot N\|$
23		lcm0val	$⊢ M \in ℤ \to M lcm 0 = 0$
24	23	adantr	$⊢ (M \in ℤ \land N \in ℤ) \to M lcm 0 = 0$
25	24	oveq1d	$⊢ (M \in ℤ \land N \in ℤ) \to (M lcm 0) (M \gcd N) = 0 \cdot (M \gcd N)$
26		zcn	$⊢ M \in ℤ \to M \in ℂ$
27	26	adantr	$⊢ (M \in ℤ \land N \in ℤ) \to M \in ℂ$
28	27	mul01d	$⊢ (M \in ℤ \land N \in ℤ) \to M \cdot 0 = 0$
29	28	abs00bd	$⊢ (M \in ℤ \land N \in ℤ) \to \|M \cdot 0\| = 0$
30	3 25 29	3eqtr4d	$⊢ (M \in ℤ \land N \in ℤ) \to (M lcm 0) (M \gcd N) = \|M \cdot 0\|$
31	30	adantr	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to (M lcm 0) (M \gcd N) = \|M \cdot 0\|$
32		simpr	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to N = 0$
33	32	oveq2d	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to M lcm N = M lcm 0$
34	33	oveq1d	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to (M lcm N) (M \gcd N) = (M lcm 0) (M \gcd N)$
35	32	oveq2d	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to M \cdot N = M \cdot 0$
36	35	fveq2d	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to \|M \cdot N\| = \|M \cdot 0\|$
37	31 34 36	3eqtr4d	$⊢ ((M \in ℤ \land N \in ℤ) \land N = 0) \to (M lcm N) (M \gcd N) = \|M \cdot N\|$
38	22 37	jaodan	$⊢ ((M \in ℤ \land N \in ℤ) \land (M = 0 \lor N = 0)) \to (M lcm N) (M \gcd N) = \|M \cdot N\|$
39		neanior	$⊢ (M \neq 0 \land N \neq 0) \leftrightarrow \neg (M = 0 \lor N = 0)$
40		nnabscl	$⊢ (M \in ℤ \land M \neq 0) \to \|M\| \in ℕ$
41		nnabscl	$⊢ (N \in ℤ \land N \neq 0) \to \|N\| \in ℕ$
42	40 41	anim12i	$⊢ ((M \in ℤ \land M \neq 0) \land (N \in ℤ \land N \neq 0)) \to (\|M\| \in ℕ \land \|N\| \in ℕ)$
43	42	an4s	$⊢ ((M \in ℤ \land N \in ℤ) \land (M \neq 0 \land N \neq 0)) \to (\|M\| \in ℕ \land \|N\| \in ℕ)$
44	39 43	sylan2br	$⊢ ((M \in ℤ \land N \in ℤ) \land \neg (M = 0 \lor N = 0)) \to (\|M\| \in ℕ \land \|N\| \in ℕ)$
45		lcmgcdlem	$⊢ (\|M\| \in ℕ \land \|N\| \in ℕ) \to ((\|M\| lcm \|N\|) (\|M\| \gcd \|N\|) = \|\|M\| \|N\|\| \land ((0 \in ℕ \land (\|M\| ∥ 0 \land \|N\| ∥ 0)) \to (\|M\| lcm \|N\|) ∥ 0))$
46	45	simpld	$⊢ (\|M\| \in ℕ \land \|N\| \in ℕ) \to (\|M\| lcm \|N\|) (\|M\| \gcd \|N\|) = \|\|M\| \|N\|\|$
47	44 46	syl	$⊢ ((M \in ℤ \land N \in ℤ) \land \neg (M = 0 \lor N = 0)) \to (\|M\| lcm \|N\|) (\|M\| \gcd \|N\|) = \|\|M\| \|N\|\|$
48		lcmabs	$⊢ (M \in ℤ \land N \in ℤ) \to \|M\| lcm \|N\| = M lcm N$
49		gcdabs	$⊢ (M \in ℤ \land N \in ℤ) \to \|M\| \gcd \|N\| = M \gcd N$
50	48 49	oveq12d	$⊢ (M \in ℤ \land N \in ℤ) \to (\|M\| lcm \|N\|) (\|M\| \gcd \|N\|) = (M lcm N) (M \gcd N)$
51	50	adantr	$⊢ ((M \in ℤ \land N \in ℤ) \land \neg (M = 0 \lor N = 0)) \to (\|M\| lcm \|N\|) (\|M\| \gcd \|N\|) = (M lcm N) (M \gcd N)$
52		absidm	$⊢ M \in ℂ \to \|\|M\|\| = \|M\|$
53		absidm	$⊢ N \in ℂ \to \|\|N\|\| = \|N\|$
54	52 53	oveqan12d	$⊢ (M \in ℂ \land N \in ℂ) \to \|\|M\|\| \|\|N\|\| = \|M\| \|N\|$
55	26 11 54	syl2an	$⊢ (M \in ℤ \land N \in ℤ) \to \|\|M\|\| \|\|N\|\| = \|M\| \|N\|$
56		nn0abscl	$⊢ M \in ℤ \to \|M\| \in ℕ_{0}$
57	56	nn0cnd	$⊢ M \in ℤ \to \|M\| \in ℂ$
58	57	adantr	$⊢ (M \in ℤ \land N \in ℤ) \to \|M\| \in ℂ$
59		nn0abscl	$⊢ N \in ℤ \to \|N\| \in ℕ_{0}$
60	59	nn0cnd	$⊢ N \in ℤ \to \|N\| \in ℂ$
61	60	adantl	$⊢ (M \in ℤ \land N \in ℤ) \to \|N\| \in ℂ$
62	58 61	absmuld	$⊢ (M \in ℤ \land N \in ℤ) \to \|\|M\| \|N\|\| = \|\|M\|\| \|\|N\|\|$
63	27 12	absmuld	$⊢ (M \in ℤ \land N \in ℤ) \to \|M \cdot N\| = \|M\| \|N\|$
64	55 62 63	3eqtr4d	$⊢ (M \in ℤ \land N \in ℤ) \to \|\|M\| \|N\|\| = \|M \cdot N\|$
65	64	adantr	$⊢ ((M \in ℤ \land N \in ℤ) \land \neg (M = 0 \lor N = 0)) \to \|\|M\| \|N\|\| = \|M \cdot N\|$
66	47 51 65	3eqtr3d	$⊢ ((M \in ℤ \land N \in ℤ) \land \neg (M = 0 \lor N = 0)) \to (M lcm N) (M \gcd N) = \|M \cdot N\|$
67	38 66	pm2.61dan	$⊢ (M \in ℤ \land N \in ℤ) \to (M lcm N) (M \gcd N) = \|M \cdot N\|$

Metamath Proof Explorer

Theorem lcmgcd

Proof