MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  dvdsmulf1o Structured version   Visualization version   GIF version

Theorem dvdsmulf1o 24965
Description: If 𝑀 and 𝑁 are two coprime integers, multiplication forms a bijection from the set of pairs 𝑗, 𝑘 where 𝑗𝑀 and 𝑘𝑁, to the set of divisors of 𝑀 · 𝑁. (Contributed by Mario Carneiro, 2-Jul-2015.)
Hypotheses
Ref Expression
dvdsmulf1o.1 (𝜑𝑀 ∈ ℕ)
dvdsmulf1o.2 (𝜑𝑁 ∈ ℕ)
dvdsmulf1o.3 (𝜑 → (𝑀 gcd 𝑁) = 1)
dvdsmulf1o.x 𝑋 = {𝑥 ∈ ℕ ∣ 𝑥𝑀}
dvdsmulf1o.y 𝑌 = {𝑥 ∈ ℕ ∣ 𝑥𝑁}
dvdsmulf1o.z 𝑍 = {𝑥 ∈ ℕ ∣ 𝑥 ∥ (𝑀 · 𝑁)}
Assertion
Ref Expression
dvdsmulf1o (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1-onto𝑍)
Distinct variable groups:   𝑥,𝑀   𝑥,𝑁
Allowed substitution hints:   𝜑(𝑥)   𝑋(𝑥)   𝑌(𝑥)   𝑍(𝑥)

Proof of Theorem dvdsmulf1o
Dummy variables 𝑖 𝑢 𝑗 𝑚 𝑛 𝑣 𝑤 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 ax-mulf 10054 . . . . . . 7 · :(ℂ × ℂ)⟶ℂ
2 ffn 6083 . . . . . . 7 ( · :(ℂ × ℂ)⟶ℂ → · Fn (ℂ × ℂ))
31, 2ax-mp 5 . . . . . 6 · Fn (ℂ × ℂ)
4 dvdsmulf1o.x . . . . . . . . 9 𝑋 = {𝑥 ∈ ℕ ∣ 𝑥𝑀}
5 ssrab2 3720 . . . . . . . . 9 {𝑥 ∈ ℕ ∣ 𝑥𝑀} ⊆ ℕ
64, 5eqsstri 3668 . . . . . . . 8 𝑋 ⊆ ℕ
7 nnsscn 11063 . . . . . . . 8 ℕ ⊆ ℂ
86, 7sstri 3645 . . . . . . 7 𝑋 ⊆ ℂ
9 dvdsmulf1o.y . . . . . . . . 9 𝑌 = {𝑥 ∈ ℕ ∣ 𝑥𝑁}
10 ssrab2 3720 . . . . . . . . 9 {𝑥 ∈ ℕ ∣ 𝑥𝑁} ⊆ ℕ
119, 10eqsstri 3668 . . . . . . . 8 𝑌 ⊆ ℕ
1211, 7sstri 3645 . . . . . . 7 𝑌 ⊆ ℂ
13 xpss12 5158 . . . . . . 7 ((𝑋 ⊆ ℂ ∧ 𝑌 ⊆ ℂ) → (𝑋 × 𝑌) ⊆ (ℂ × ℂ))
148, 12, 13mp2an 708 . . . . . 6 (𝑋 × 𝑌) ⊆ (ℂ × ℂ)
15 fnssres 6042 . . . . . 6 (( · Fn (ℂ × ℂ) ∧ (𝑋 × 𝑌) ⊆ (ℂ × ℂ)) → ( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌))
163, 14, 15mp2an 708 . . . . 5 ( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌)
1716a1i 11 . . . 4 (𝜑 → ( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌))
18 ovres 6842 . . . . . . 7 ((𝑖𝑋𝑗𝑌) → (𝑖( · ↾ (𝑋 × 𝑌))𝑗) = (𝑖 · 𝑗))
1918adantl 481 . . . . . 6 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖( · ↾ (𝑋 × 𝑌))𝑗) = (𝑖 · 𝑗))
20 breq1 4688 . . . . . . . . . . 11 (𝑥 = 𝑖 → (𝑥𝑀𝑖𝑀))
2120, 4elrab2 3399 . . . . . . . . . 10 (𝑖𝑋 ↔ (𝑖 ∈ ℕ ∧ 𝑖𝑀))
2221simplbi 475 . . . . . . . . 9 (𝑖𝑋𝑖 ∈ ℕ)
2322ad2antrl 764 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑖 ∈ ℕ)
24 breq1 4688 . . . . . . . . . . 11 (𝑥 = 𝑗 → (𝑥𝑁𝑗𝑁))
2524, 9elrab2 3399 . . . . . . . . . 10 (𝑗𝑌 ↔ (𝑗 ∈ ℕ ∧ 𝑗𝑁))
2625simplbi 475 . . . . . . . . 9 (𝑗𝑌𝑗 ∈ ℕ)
2726ad2antll 765 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑗 ∈ ℕ)
2823, 27nnmulcld 11106 . . . . . . 7 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∈ ℕ)
2925simprbi 479 . . . . . . . . 9 (𝑗𝑌𝑗𝑁)
3029ad2antll 765 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑗𝑁)
3121simprbi 479 . . . . . . . . 9 (𝑖𝑋𝑖𝑀)
3231ad2antrl 764 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑖𝑀)
3327nnzd 11519 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑗 ∈ ℤ)
34 dvdsmulf1o.2 . . . . . . . . . . . 12 (𝜑𝑁 ∈ ℕ)
3534adantr 480 . . . . . . . . . . 11 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑁 ∈ ℕ)
3635nnzd 11519 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑁 ∈ ℤ)
3723nnzd 11519 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑖 ∈ ℤ)
38 dvdscmul 15055 . . . . . . . . . 10 ((𝑗 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝑖 ∈ ℤ) → (𝑗𝑁 → (𝑖 · 𝑗) ∥ (𝑖 · 𝑁)))
3933, 36, 37, 38syl3anc 1366 . . . . . . . . 9 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑗𝑁 → (𝑖 · 𝑗) ∥ (𝑖 · 𝑁)))
40 dvdsmulf1o.1 . . . . . . . . . . . 12 (𝜑𝑀 ∈ ℕ)
4140adantr 480 . . . . . . . . . . 11 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑀 ∈ ℕ)
4241nnzd 11519 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑀 ∈ ℤ)
43 dvdsmulc 15056 . . . . . . . . . 10 ((𝑖 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑖𝑀 → (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)))
4437, 42, 36, 43syl3anc 1366 . . . . . . . . 9 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖𝑀 → (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)))
4528nnzd 11519 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∈ ℤ)
4637, 36zmulcld 11526 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑁) ∈ ℤ)
4742, 36zmulcld 11526 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑀 · 𝑁) ∈ ℤ)
48 dvdstr 15065 . . . . . . . . . 10 (((𝑖 · 𝑗) ∈ ℤ ∧ (𝑖 · 𝑁) ∈ ℤ ∧ (𝑀 · 𝑁) ∈ ℤ) → (((𝑖 · 𝑗) ∥ (𝑖 · 𝑁) ∧ (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
4945, 46, 47, 48syl3anc 1366 . . . . . . . . 9 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (((𝑖 · 𝑗) ∥ (𝑖 · 𝑁) ∧ (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
5039, 44, 49syl2and 499 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → ((𝑗𝑁𝑖𝑀) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
5130, 32, 50mp2and 715 . . . . . . 7 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁))
52 breq1 4688 . . . . . . . 8 (𝑥 = (𝑖 · 𝑗) → (𝑥 ∥ (𝑀 · 𝑁) ↔ (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
53 dvdsmulf1o.z . . . . . . . 8 𝑍 = {𝑥 ∈ ℕ ∣ 𝑥 ∥ (𝑀 · 𝑁)}
5452, 53elrab2 3399 . . . . . . 7 ((𝑖 · 𝑗) ∈ 𝑍 ↔ ((𝑖 · 𝑗) ∈ ℕ ∧ (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
5528, 51, 54sylanbrc 699 . . . . . 6 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∈ 𝑍)
5619, 55eqeltrd 2730 . . . . 5 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖( · ↾ (𝑋 × 𝑌))𝑗) ∈ 𝑍)
5756ralrimivva 3000 . . . 4 (𝜑 → ∀𝑖𝑋𝑗𝑌 (𝑖( · ↾ (𝑋 × 𝑌))𝑗) ∈ 𝑍)
58 ffnov 6806 . . . 4 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍 ↔ (( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌) ∧ ∀𝑖𝑋𝑗𝑌 (𝑖( · ↾ (𝑋 × 𝑌))𝑗) ∈ 𝑍))
5917, 57, 58sylanbrc 699 . . 3 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍)
6023adantr 480 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℕ)
6160nnnn0d 11389 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℕ0)
62 simprll 819 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚𝑋)
63 breq1 4688 . . . . . . . . . . . . 13 (𝑥 = 𝑚 → (𝑥𝑀𝑚𝑀))
6463, 4elrab2 3399 . . . . . . . . . . . 12 (𝑚𝑋 ↔ (𝑚 ∈ ℕ ∧ 𝑚𝑀))
6564simplbi 475 . . . . . . . . . . 11 (𝑚𝑋𝑚 ∈ ℕ)
6662, 65syl 17 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℕ)
6766nnnn0d 11389 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℕ0)
6860nnzd 11519 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℤ)
6927adantr 480 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 ∈ ℕ)
7069nnzd 11519 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 ∈ ℤ)
71 dvdsmul1 15050 . . . . . . . . . . . 12 ((𝑖 ∈ ℤ ∧ 𝑗 ∈ ℤ) → 𝑖 ∥ (𝑖 · 𝑗))
7268, 70, 71syl2anc 694 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∥ (𝑖 · 𝑗))
73 simprr 811 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑚 · 𝑛))
748, 62sseldi 3634 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℂ)
75 simprlr 820 . . . . . . . . . . . . . . 15 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛𝑌)
76 breq1 4688 . . . . . . . . . . . . . . . . 17 (𝑥 = 𝑛 → (𝑥𝑁𝑛𝑁))
7776, 9elrab2 3399 . . . . . . . . . . . . . . . 16 (𝑛𝑌 ↔ (𝑛 ∈ ℕ ∧ 𝑛𝑁))
7877simplbi 475 . . . . . . . . . . . . . . 15 (𝑛𝑌𝑛 ∈ ℕ)
7975, 78syl 17 . . . . . . . . . . . . . 14 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛 ∈ ℕ)
8079nncnd 11074 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛 ∈ ℂ)
8174, 80mulcomd 10099 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 · 𝑛) = (𝑛 · 𝑚))
8273, 81eqtrd 2685 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑛 · 𝑚))
8372, 82breqtrd 4711 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∥ (𝑛 · 𝑚))
8479nnzd 11519 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛 ∈ ℤ)
8536adantr 480 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑁 ∈ ℤ)
86 gcdcom 15282 . . . . . . . . . . . . 13 ((𝑖 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑖 gcd 𝑁) = (𝑁 gcd 𝑖))
8768, 85, 86syl2anc 694 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 gcd 𝑁) = (𝑁 gcd 𝑖))
8842adantr 480 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑀 ∈ ℤ)
8934nnzd 11519 . . . . . . . . . . . . . . . 16 (𝜑𝑁 ∈ ℤ)
9040nnzd 11519 . . . . . . . . . . . . . . . 16 (𝜑𝑀 ∈ ℤ)
91 gcdcom 15282 . . . . . . . . . . . . . . . 16 ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℤ) → (𝑁 gcd 𝑀) = (𝑀 gcd 𝑁))
9289, 90, 91syl2anc 694 . . . . . . . . . . . . . . 15 (𝜑 → (𝑁 gcd 𝑀) = (𝑀 gcd 𝑁))
93 dvdsmulf1o.3 . . . . . . . . . . . . . . 15 (𝜑 → (𝑀 gcd 𝑁) = 1)
9492, 93eqtrd 2685 . . . . . . . . . . . . . 14 (𝜑 → (𝑁 gcd 𝑀) = 1)
9594ad2antrr 762 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑁 gcd 𝑀) = 1)
9632adantr 480 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖𝑀)
97 rpdvds 15421 . . . . . . . . . . . . 13 (((𝑁 ∈ ℤ ∧ 𝑖 ∈ ℤ ∧ 𝑀 ∈ ℤ) ∧ ((𝑁 gcd 𝑀) = 1 ∧ 𝑖𝑀)) → (𝑁 gcd 𝑖) = 1)
9885, 68, 88, 95, 96, 97syl32anc 1374 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑁 gcd 𝑖) = 1)
9987, 98eqtrd 2685 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 gcd 𝑁) = 1)
10077simprbi 479 . . . . . . . . . . . 12 (𝑛𝑌𝑛𝑁)
10175, 100syl 17 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛𝑁)
102 rpdvds 15421 . . . . . . . . . . 11 (((𝑖 ∈ ℤ ∧ 𝑛 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ((𝑖 gcd 𝑁) = 1 ∧ 𝑛𝑁)) → (𝑖 gcd 𝑛) = 1)
10368, 84, 85, 99, 101, 102syl32anc 1374 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 gcd 𝑛) = 1)
10466nnzd 11519 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℤ)
105 coprmdvds 15413 . . . . . . . . . . 11 ((𝑖 ∈ ℤ ∧ 𝑛 ∈ ℤ ∧ 𝑚 ∈ ℤ) → ((𝑖 ∥ (𝑛 · 𝑚) ∧ (𝑖 gcd 𝑛) = 1) → 𝑖𝑚))
10668, 84, 104, 105syl3anc 1366 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → ((𝑖 ∥ (𝑛 · 𝑚) ∧ (𝑖 gcd 𝑛) = 1) → 𝑖𝑚))
10783, 103, 106mp2and 715 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖𝑚)
108 dvdsmul1 15050 . . . . . . . . . . . 12 ((𝑚 ∈ ℤ ∧ 𝑛 ∈ ℤ) → 𝑚 ∥ (𝑚 · 𝑛))
109104, 84, 108syl2anc 694 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∥ (𝑚 · 𝑛))
11060nncnd 11074 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℂ)
11169nncnd 11074 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 ∈ ℂ)
112110, 111mulcomd 10099 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑗 · 𝑖))
11373, 112eqtr3d 2687 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 · 𝑛) = (𝑗 · 𝑖))
114109, 113breqtrd 4711 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∥ (𝑗 · 𝑖))
115 gcdcom 15282 . . . . . . . . . . . . 13 ((𝑚 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑚 gcd 𝑁) = (𝑁 gcd 𝑚))
116104, 85, 115syl2anc 694 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 gcd 𝑁) = (𝑁 gcd 𝑚))
11764simprbi 479 . . . . . . . . . . . . . 14 (𝑚𝑋𝑚𝑀)
11862, 117syl 17 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚𝑀)
119 rpdvds 15421 . . . . . . . . . . . . 13 (((𝑁 ∈ ℤ ∧ 𝑚 ∈ ℤ ∧ 𝑀 ∈ ℤ) ∧ ((𝑁 gcd 𝑀) = 1 ∧ 𝑚𝑀)) → (𝑁 gcd 𝑚) = 1)
12085, 104, 88, 95, 118, 119syl32anc 1374 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑁 gcd 𝑚) = 1)
121116, 120eqtrd 2685 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 gcd 𝑁) = 1)
12230adantr 480 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗𝑁)
123 rpdvds 15421 . . . . . . . . . . 11 (((𝑚 ∈ ℤ ∧ 𝑗 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ((𝑚 gcd 𝑁) = 1 ∧ 𝑗𝑁)) → (𝑚 gcd 𝑗) = 1)
124104, 70, 85, 121, 122, 123syl32anc 1374 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 gcd 𝑗) = 1)
125 coprmdvds 15413 . . . . . . . . . . 11 ((𝑚 ∈ ℤ ∧ 𝑗 ∈ ℤ ∧ 𝑖 ∈ ℤ) → ((𝑚 ∥ (𝑗 · 𝑖) ∧ (𝑚 gcd 𝑗) = 1) → 𝑚𝑖))
126104, 70, 68, 125syl3anc 1366 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → ((𝑚 ∥ (𝑗 · 𝑖) ∧ (𝑚 gcd 𝑗) = 1) → 𝑚𝑖))
127114, 124, 126mp2and 715 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚𝑖)
128 dvdseq 15083 . . . . . . . . 9 (((𝑖 ∈ ℕ0𝑚 ∈ ℕ0) ∧ (𝑖𝑚𝑚𝑖)) → 𝑖 = 𝑚)
12961, 67, 107, 127, 128syl22anc 1367 . . . . . . . 8 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 = 𝑚)
13060nnne0d 11103 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ≠ 0)
131129oveq1d 6705 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑛) = (𝑚 · 𝑛))
13273, 131eqtr4d 2688 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑖 · 𝑛))
133111, 80, 110, 130, 132mulcanad 10700 . . . . . . . 8 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 = 𝑛)
134129, 133opeq12d 4441 . . . . . . 7 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)
135134expr 642 . . . . . 6 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ (𝑚𝑋𝑛𝑌)) → ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
136135ralrimivva 3000 . . . . 5 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → ∀𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
137136ralrimivva 3000 . . . 4 (𝜑 → ∀𝑖𝑋𝑗𝑌𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
138 fvres 6245 . . . . . . . . 9 (𝑢 ∈ (𝑋 × 𝑌) → (( · ↾ (𝑋 × 𝑌))‘𝑢) = ( · ‘𝑢))
139 fvres 6245 . . . . . . . . 9 (𝑣 ∈ (𝑋 × 𝑌) → (( · ↾ (𝑋 × 𝑌))‘𝑣) = ( · ‘𝑣))
140138, 139eqeqan12d 2667 . . . . . . . 8 ((𝑢 ∈ (𝑋 × 𝑌) ∧ 𝑣 ∈ (𝑋 × 𝑌)) → ((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) ↔ ( · ‘𝑢) = ( · ‘𝑣)))
141140imbi1d 330 . . . . . . 7 ((𝑢 ∈ (𝑋 × 𝑌) ∧ 𝑣 ∈ (𝑋 × 𝑌)) → (((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ (( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣)))
142141ralbidva 3014 . . . . . 6 (𝑢 ∈ (𝑋 × 𝑌) → (∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣)))
143142ralbiia 3008 . . . . 5 (∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣))
144 fveq2 6229 . . . . . . . . . . 11 (𝑣 = ⟨𝑚, 𝑛⟩ → ( · ‘𝑣) = ( · ‘⟨𝑚, 𝑛⟩))
145 df-ov 6693 . . . . . . . . . . 11 (𝑚 · 𝑛) = ( · ‘⟨𝑚, 𝑛⟩)
146144, 145syl6eqr 2703 . . . . . . . . . 10 (𝑣 = ⟨𝑚, 𝑛⟩ → ( · ‘𝑣) = (𝑚 · 𝑛))
147146eqeq2d 2661 . . . . . . . . 9 (𝑣 = ⟨𝑚, 𝑛⟩ → (( · ‘𝑢) = ( · ‘𝑣) ↔ ( · ‘𝑢) = (𝑚 · 𝑛)))
148 eqeq2 2662 . . . . . . . . 9 (𝑣 = ⟨𝑚, 𝑛⟩ → (𝑢 = 𝑣𝑢 = ⟨𝑚, 𝑛⟩))
149147, 148imbi12d 333 . . . . . . . 8 (𝑣 = ⟨𝑚, 𝑛⟩ → ((( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ (( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩)))
150149ralxp 5296 . . . . . . 7 (∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑚𝑋𝑛𝑌 (( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩))
151 fveq2 6229 . . . . . . . . . . 11 (𝑢 = ⟨𝑖, 𝑗⟩ → ( · ‘𝑢) = ( · ‘⟨𝑖, 𝑗⟩))
152 df-ov 6693 . . . . . . . . . . 11 (𝑖 · 𝑗) = ( · ‘⟨𝑖, 𝑗⟩)
153151, 152syl6eqr 2703 . . . . . . . . . 10 (𝑢 = ⟨𝑖, 𝑗⟩ → ( · ‘𝑢) = (𝑖 · 𝑗))
154153eqeq1d 2653 . . . . . . . . 9 (𝑢 = ⟨𝑖, 𝑗⟩ → (( · ‘𝑢) = (𝑚 · 𝑛) ↔ (𝑖 · 𝑗) = (𝑚 · 𝑛)))
155 eqeq1 2655 . . . . . . . . 9 (𝑢 = ⟨𝑖, 𝑗⟩ → (𝑢 = ⟨𝑚, 𝑛⟩ ↔ ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
156154, 155imbi12d 333 . . . . . . . 8 (𝑢 = ⟨𝑖, 𝑗⟩ → ((( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩) ↔ ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)))
1571562ralbidv 3018 . . . . . . 7 (𝑢 = ⟨𝑖, 𝑗⟩ → (∀𝑚𝑋𝑛𝑌 (( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩) ↔ ∀𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)))
158150, 157syl5bb 272 . . . . . 6 (𝑢 = ⟨𝑖, 𝑗⟩ → (∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)))
159158ralxp 5296 . . . . 5 (∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑖𝑋𝑗𝑌𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
160143, 159bitri 264 . . . 4 (∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑖𝑋𝑗𝑌𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
161137, 160sylibr 224 . . 3 (𝜑 → ∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣))
162 dff13 6552 . . 3 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1𝑍 ↔ (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍 ∧ ∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣)))
16359, 161, 162sylanbrc 699 . 2 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1𝑍)
164 breq1 4688 . . . . . . . . . . . 12 (𝑥 = 𝑤 → (𝑥 ∥ (𝑀 · 𝑁) ↔ 𝑤 ∥ (𝑀 · 𝑁)))
165164, 53elrab2 3399 . . . . . . . . . . 11 (𝑤𝑍 ↔ (𝑤 ∈ ℕ ∧ 𝑤 ∥ (𝑀 · 𝑁)))
166165simplbi 475 . . . . . . . . . 10 (𝑤𝑍𝑤 ∈ ℕ)
167166adantl 481 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑤 ∈ ℕ)
168167nnzd 11519 . . . . . . . 8 ((𝜑𝑤𝑍) → 𝑤 ∈ ℤ)
16940adantr 480 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑀 ∈ ℕ)
170169nnzd 11519 . . . . . . . 8 ((𝜑𝑤𝑍) → 𝑀 ∈ ℤ)
171169nnne0d 11103 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑀 ≠ 0)
172 simpr 476 . . . . . . . . . 10 ((𝑤 = 0 ∧ 𝑀 = 0) → 𝑀 = 0)
173172necon3ai 2848 . . . . . . . . 9 (𝑀 ≠ 0 → ¬ (𝑤 = 0 ∧ 𝑀 = 0))
174171, 173syl 17 . . . . . . . 8 ((𝜑𝑤𝑍) → ¬ (𝑤 = 0 ∧ 𝑀 = 0))
175 gcdn0cl 15271 . . . . . . . 8 (((𝑤 ∈ ℤ ∧ 𝑀 ∈ ℤ) ∧ ¬ (𝑤 = 0 ∧ 𝑀 = 0)) → (𝑤 gcd 𝑀) ∈ ℕ)
176168, 170, 174, 175syl21anc 1365 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑀) ∈ ℕ)
177 gcddvds 15272 . . . . . . . . 9 ((𝑤 ∈ ℤ ∧ 𝑀 ∈ ℤ) → ((𝑤 gcd 𝑀) ∥ 𝑤 ∧ (𝑤 gcd 𝑀) ∥ 𝑀))
178168, 170, 177syl2anc 694 . . . . . . . 8 ((𝜑𝑤𝑍) → ((𝑤 gcd 𝑀) ∥ 𝑤 ∧ (𝑤 gcd 𝑀) ∥ 𝑀))
179178simprd 478 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑀) ∥ 𝑀)
180 breq1 4688 . . . . . . . 8 (𝑥 = (𝑤 gcd 𝑀) → (𝑥𝑀 ↔ (𝑤 gcd 𝑀) ∥ 𝑀))
181180, 4elrab2 3399 . . . . . . 7 ((𝑤 gcd 𝑀) ∈ 𝑋 ↔ ((𝑤 gcd 𝑀) ∈ ℕ ∧ (𝑤 gcd 𝑀) ∥ 𝑀))
182176, 179, 181sylanbrc 699 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑀) ∈ 𝑋)
18334adantr 480 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑁 ∈ ℕ)
184183nnzd 11519 . . . . . . . 8 ((𝜑𝑤𝑍) → 𝑁 ∈ ℤ)
185183nnne0d 11103 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑁 ≠ 0)
186 simpr 476 . . . . . . . . . 10 ((𝑤 = 0 ∧ 𝑁 = 0) → 𝑁 = 0)
187186necon3ai 2848 . . . . . . . . 9 (𝑁 ≠ 0 → ¬ (𝑤 = 0 ∧ 𝑁 = 0))
188185, 187syl 17 . . . . . . . 8 ((𝜑𝑤𝑍) → ¬ (𝑤 = 0 ∧ 𝑁 = 0))
189 gcdn0cl 15271 . . . . . . . 8 (((𝑤 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑤 = 0 ∧ 𝑁 = 0)) → (𝑤 gcd 𝑁) ∈ ℕ)
190168, 184, 188, 189syl21anc 1365 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑁) ∈ ℕ)
191 gcddvds 15272 . . . . . . . . 9 ((𝑤 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑤 gcd 𝑁) ∥ 𝑤 ∧ (𝑤 gcd 𝑁) ∥ 𝑁))
192168, 184, 191syl2anc 694 . . . . . . . 8 ((𝜑𝑤𝑍) → ((𝑤 gcd 𝑁) ∥ 𝑤 ∧ (𝑤 gcd 𝑁) ∥ 𝑁))
193192simprd 478 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑁) ∥ 𝑁)
194 breq1 4688 . . . . . . . 8 (𝑥 = (𝑤 gcd 𝑁) → (𝑥𝑁 ↔ (𝑤 gcd 𝑁) ∥ 𝑁))
195194, 9elrab2 3399 . . . . . . 7 ((𝑤 gcd 𝑁) ∈ 𝑌 ↔ ((𝑤 gcd 𝑁) ∈ ℕ ∧ (𝑤 gcd 𝑁) ∥ 𝑁))
196190, 193, 195sylanbrc 699 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑁) ∈ 𝑌)
197 opelxpi 5182 . . . . . 6 (((𝑤 gcd 𝑀) ∈ 𝑋 ∧ (𝑤 gcd 𝑁) ∈ 𝑌) → ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌))
198182, 196, 197syl2anc 694 . . . . 5 ((𝜑𝑤𝑍) → ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌))
199 fvres 6245 . . . . . . 7 (⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌) → (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
200198, 199syl 17 . . . . . 6 ((𝜑𝑤𝑍) → (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
20193adantr 480 . . . . . . . 8 ((𝜑𝑤𝑍) → (𝑀 gcd 𝑁) = 1)
202 rpmulgcd2 15417 . . . . . . . 8 (((𝑤 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ (𝑀 gcd 𝑁) = 1) → (𝑤 gcd (𝑀 · 𝑁)) = ((𝑤 gcd 𝑀) · (𝑤 gcd 𝑁)))
203168, 170, 184, 201, 202syl31anc 1369 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd (𝑀 · 𝑁)) = ((𝑤 gcd 𝑀) · (𝑤 gcd 𝑁)))
204 df-ov 6693 . . . . . . 7 ((𝑤 gcd 𝑀) · (𝑤 gcd 𝑁)) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩)
205203, 204syl6eq 2701 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd (𝑀 · 𝑁)) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
206165simprbi 479 . . . . . . . 8 (𝑤𝑍𝑤 ∥ (𝑀 · 𝑁))
207206adantl 481 . . . . . . 7 ((𝜑𝑤𝑍) → 𝑤 ∥ (𝑀 · 𝑁))
20840, 34nnmulcld 11106 . . . . . . . 8 (𝜑 → (𝑀 · 𝑁) ∈ ℕ)
209 gcdeq 15319 . . . . . . . 8 ((𝑤 ∈ ℕ ∧ (𝑀 · 𝑁) ∈ ℕ) → ((𝑤 gcd (𝑀 · 𝑁)) = 𝑤𝑤 ∥ (𝑀 · 𝑁)))
210166, 208, 209syl2anr 494 . . . . . . 7 ((𝜑𝑤𝑍) → ((𝑤 gcd (𝑀 · 𝑁)) = 𝑤𝑤 ∥ (𝑀 · 𝑁)))
211207, 210mpbird 247 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd (𝑀 · 𝑁)) = 𝑤)
212200, 205, 2113eqtr2rd 2692 . . . . 5 ((𝜑𝑤𝑍) → 𝑤 = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
213 fveq2 6229 . . . . . . 7 (𝑢 = ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ → (( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
214213eqeq2d 2661 . . . . . 6 (𝑢 = ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ → (𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢) ↔ 𝑤 = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩)))
215214rspcev 3340 . . . . 5 ((⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌) ∧ 𝑤 = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩)) → ∃𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢))
216198, 212, 215syl2anc 694 . . . 4 ((𝜑𝑤𝑍) → ∃𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢))
217216ralrimiva 2995 . . 3 (𝜑 → ∀𝑤𝑍𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢))
218 dffo3 6414 . . 3 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–onto𝑍 ↔ (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍 ∧ ∀𝑤𝑍𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢)))
21959, 217, 218sylanbrc 699 . 2 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–onto𝑍)
220 df-f1o 5933 . 2 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1-onto𝑍 ↔ (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1𝑍 ∧ ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–onto𝑍))
221163, 219, 220sylanbrc 699 1 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1-onto𝑍)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 196  wa 383   = wceq 1523  wcel 2030  wne 2823  wral 2941  wrex 2942  {crab 2945  wss 3607  cop 4216   class class class wbr 4685   × cxp 5141  cres 5145   Fn wfn 5921  wf 5922  1-1wf1 5923  ontowfo 5924  1-1-ontowf1o 5925  cfv 5926  (class class class)co 6690  cc 9972  0cc0 9974  1c1 9975   · cmul 9979  cn 11058  0cn0 11330  cz 11415  cdvds 15027   gcd cgcd 15263
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1762  ax-4 1777  ax-5 1879  ax-6 1945  ax-7 1981  ax-8 2032  ax-9 2039  ax-10 2059  ax-11 2074  ax-12 2087  ax-13 2282  ax-ext 2631  ax-sep 4814  ax-nul 4822  ax-pow 4873  ax-pr 4936  ax-un 6991  ax-cnex 10030  ax-resscn 10031  ax-1cn 10032  ax-icn 10033  ax-addcl 10034  ax-addrcl 10035  ax-mulcl 10036  ax-mulrcl 10037  ax-mulcom 10038  ax-addass 10039  ax-mulass 10040  ax-distr 10041  ax-i2m1 10042  ax-1ne0 10043  ax-1rid 10044  ax-rnegex 10045  ax-rrecex 10046  ax-cnre 10047  ax-pre-lttri 10048  ax-pre-lttrn 10049  ax-pre-ltadd 10050  ax-pre-mulgt0 10051  ax-pre-sup 10052  ax-mulf 10054
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1055  df-3an 1056  df-tru 1526  df-ex 1745  df-nf 1750  df-sb 1938  df-eu 2502  df-mo 2503  df-clab 2638  df-cleq 2644  df-clel 2647  df-nfc 2782  df-ne 2824  df-nel 2927  df-ral 2946  df-rex 2947  df-reu 2948  df-rmo 2949  df-rab 2950  df-v 3233  df-sbc 3469  df-csb 3567  df-dif 3610  df-un 3612  df-in 3614  df-ss 3621  df-pss 3623  df-nul 3949  df-if 4120  df-pw 4193  df-sn 4211  df-pr 4213  df-tp 4215  df-op 4217  df-uni 4469  df-iun 4554  df-br 4686  df-opab 4746  df-mpt 4763  df-tr 4786  df-id 5053  df-eprel 5058  df-po 5064  df-so 5065  df-fr 5102  df-we 5104  df-xp 5149  df-rel 5150  df-cnv 5151  df-co 5152  df-dm 5153  df-rn 5154  df-res 5155  df-ima 5156  df-pred 5718  df-ord 5764  df-on 5765  df-lim 5766  df-suc 5767  df-iota 5889  df-fun 5928  df-fn 5929  df-f 5930  df-f1 5931  df-fo 5932  df-f1o 5933  df-fv 5934  df-riota 6651  df-ov 6693  df-oprab 6694  df-mpt2 6695  df-om 7108  df-2nd 7211  df-wrecs 7452  df-recs 7513  df-rdg 7551  df-er 7787  df-en 7998  df-dom 7999  df-sdom 8000  df-sup 8389  df-inf 8390  df-pnf 10114  df-mnf 10115  df-xr 10116  df-ltxr 10117  df-le 10118  df-sub 10306  df-neg 10307  df-div 10723  df-nn 11059  df-2 11117  df-3 11118  df-n0 11331  df-z 11416  df-uz 11726  df-rp 11871  df-fl 12633  df-mod 12709  df-seq 12842  df-exp 12901  df-cj 13883  df-re 13884  df-im 13885  df-sqrt 14019  df-abs 14020  df-dvds 15028  df-gcd 15264
This theorem is referenced by:  fsumdvdsmul  24966
  Copyright terms: Public domain W3C validator