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

Theorem dvdsmulf1o 24820
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 9960 . . . . . . 7 · :(ℂ × ℂ)⟶ℂ
2 ffn 6002 . . . . . . 7 ( · :(ℂ × ℂ)⟶ℂ → · Fn (ℂ × ℂ))
31, 2ax-mp 5 . . . . . 6 · Fn (ℂ × ℂ)
4 dvdsmulf1o.x . . . . . . . . 9 𝑋 = {𝑥 ∈ ℕ ∣ 𝑥𝑀}
5 ssrab2 3666 . . . . . . . . 9 {𝑥 ∈ ℕ ∣ 𝑥𝑀} ⊆ ℕ
64, 5eqsstri 3614 . . . . . . . 8 𝑋 ⊆ ℕ
7 nnsscn 10969 . . . . . . . 8 ℕ ⊆ ℂ
86, 7sstri 3592 . . . . . . 7 𝑋 ⊆ ℂ
9 dvdsmulf1o.y . . . . . . . . 9 𝑌 = {𝑥 ∈ ℕ ∣ 𝑥𝑁}
10 ssrab2 3666 . . . . . . . . 9 {𝑥 ∈ ℕ ∣ 𝑥𝑁} ⊆ ℕ
119, 10eqsstri 3614 . . . . . . . 8 𝑌 ⊆ ℕ
1211, 7sstri 3592 . . . . . . 7 𝑌 ⊆ ℂ
13 xpss12 5186 . . . . . . 7 ((𝑋 ⊆ ℂ ∧ 𝑌 ⊆ ℂ) → (𝑋 × 𝑌) ⊆ (ℂ × ℂ))
148, 12, 13mp2an 707 . . . . . 6 (𝑋 × 𝑌) ⊆ (ℂ × ℂ)
15 fnssres 5962 . . . . . 6 (( · Fn (ℂ × ℂ) ∧ (𝑋 × 𝑌) ⊆ (ℂ × ℂ)) → ( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌))
163, 14, 15mp2an 707 . . . . 5 ( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌)
1716a1i 11 . . . 4 (𝜑 → ( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌))
18 ovres 6753 . . . . . . 7 ((𝑖𝑋𝑗𝑌) → (𝑖( · ↾ (𝑋 × 𝑌))𝑗) = (𝑖 · 𝑗))
1918adantl 482 . . . . . 6 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖( · ↾ (𝑋 × 𝑌))𝑗) = (𝑖 · 𝑗))
20 breq1 4616 . . . . . . . . . . 11 (𝑥 = 𝑖 → (𝑥𝑀𝑖𝑀))
2120, 4elrab2 3348 . . . . . . . . . 10 (𝑖𝑋 ↔ (𝑖 ∈ ℕ ∧ 𝑖𝑀))
2221simplbi 476 . . . . . . . . 9 (𝑖𝑋𝑖 ∈ ℕ)
2322ad2antrl 763 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑖 ∈ ℕ)
24 breq1 4616 . . . . . . . . . . 11 (𝑥 = 𝑗 → (𝑥𝑁𝑗𝑁))
2524, 9elrab2 3348 . . . . . . . . . 10 (𝑗𝑌 ↔ (𝑗 ∈ ℕ ∧ 𝑗𝑁))
2625simplbi 476 . . . . . . . . 9 (𝑗𝑌𝑗 ∈ ℕ)
2726ad2antll 764 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑗 ∈ ℕ)
2823, 27nnmulcld 11012 . . . . . . 7 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∈ ℕ)
2925simprbi 480 . . . . . . . . 9 (𝑗𝑌𝑗𝑁)
3029ad2antll 764 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑗𝑁)
3121simprbi 480 . . . . . . . . 9 (𝑖𝑋𝑖𝑀)
3231ad2antrl 763 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑖𝑀)
3327nnzd 11425 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑗 ∈ ℤ)
34 dvdsmulf1o.2 . . . . . . . . . . . 12 (𝜑𝑁 ∈ ℕ)
3534adantr 481 . . . . . . . . . . 11 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑁 ∈ ℕ)
3635nnzd 11425 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑁 ∈ ℤ)
3723nnzd 11425 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑖 ∈ ℤ)
38 dvdscmul 14932 . . . . . . . . . 10 ((𝑗 ∈ ℤ ∧ 𝑁 ∈ ℤ ∧ 𝑖 ∈ ℤ) → (𝑗𝑁 → (𝑖 · 𝑗) ∥ (𝑖 · 𝑁)))
3933, 36, 37, 38syl3anc 1323 . . . . . . . . 9 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑗𝑁 → (𝑖 · 𝑗) ∥ (𝑖 · 𝑁)))
40 dvdsmulf1o.1 . . . . . . . . . . . 12 (𝜑𝑀 ∈ ℕ)
4140adantr 481 . . . . . . . . . . 11 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑀 ∈ ℕ)
4241nnzd 11425 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → 𝑀 ∈ ℤ)
43 dvdsmulc 14933 . . . . . . . . . 10 ((𝑖 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑖𝑀 → (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)))
4437, 42, 36, 43syl3anc 1323 . . . . . . . . 9 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖𝑀 → (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)))
4528nnzd 11425 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∈ ℤ)
4637, 36zmulcld 11432 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑁) ∈ ℤ)
4742, 36zmulcld 11432 . . . . . . . . . 10 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑀 · 𝑁) ∈ ℤ)
48 dvdstr 14942 . . . . . . . . . 10 (((𝑖 · 𝑗) ∈ ℤ ∧ (𝑖 · 𝑁) ∈ ℤ ∧ (𝑀 · 𝑁) ∈ ℤ) → (((𝑖 · 𝑗) ∥ (𝑖 · 𝑁) ∧ (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
4945, 46, 47, 48syl3anc 1323 . . . . . . . . 9 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (((𝑖 · 𝑗) ∥ (𝑖 · 𝑁) ∧ (𝑖 · 𝑁) ∥ (𝑀 · 𝑁)) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
5039, 44, 49syl2and 500 . . . . . . . 8 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → ((𝑗𝑁𝑖𝑀) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
5130, 32, 50mp2and 714 . . . . . . 7 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∥ (𝑀 · 𝑁))
52 breq1 4616 . . . . . . . 8 (𝑥 = (𝑖 · 𝑗) → (𝑥 ∥ (𝑀 · 𝑁) ↔ (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
53 dvdsmulf1o.z . . . . . . . 8 𝑍 = {𝑥 ∈ ℕ ∣ 𝑥 ∥ (𝑀 · 𝑁)}
5452, 53elrab2 3348 . . . . . . 7 ((𝑖 · 𝑗) ∈ 𝑍 ↔ ((𝑖 · 𝑗) ∈ ℕ ∧ (𝑖 · 𝑗) ∥ (𝑀 · 𝑁)))
5528, 51, 54sylanbrc 697 . . . . . 6 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖 · 𝑗) ∈ 𝑍)
5619, 55eqeltrd 2698 . . . . 5 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → (𝑖( · ↾ (𝑋 × 𝑌))𝑗) ∈ 𝑍)
5756ralrimivva 2965 . . . 4 (𝜑 → ∀𝑖𝑋𝑗𝑌 (𝑖( · ↾ (𝑋 × 𝑌))𝑗) ∈ 𝑍)
58 ffnov 6717 . . . 4 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍 ↔ (( · ↾ (𝑋 × 𝑌)) Fn (𝑋 × 𝑌) ∧ ∀𝑖𝑋𝑗𝑌 (𝑖( · ↾ (𝑋 × 𝑌))𝑗) ∈ 𝑍))
5917, 57, 58sylanbrc 697 . . 3 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍)
6023adantr 481 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℕ)
6160nnnn0d 11295 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℕ0)
62 simprll 801 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚𝑋)
63 breq1 4616 . . . . . . . . . . . . 13 (𝑥 = 𝑚 → (𝑥𝑀𝑚𝑀))
6463, 4elrab2 3348 . . . . . . . . . . . 12 (𝑚𝑋 ↔ (𝑚 ∈ ℕ ∧ 𝑚𝑀))
6564simplbi 476 . . . . . . . . . . 11 (𝑚𝑋𝑚 ∈ ℕ)
6662, 65syl 17 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℕ)
6766nnnn0d 11295 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℕ0)
6860nnzd 11425 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℤ)
6927adantr 481 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 ∈ ℕ)
7069nnzd 11425 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 ∈ ℤ)
71 dvdsmul1 14927 . . . . . . . . . . . 12 ((𝑖 ∈ ℤ ∧ 𝑗 ∈ ℤ) → 𝑖 ∥ (𝑖 · 𝑗))
7268, 70, 71syl2anc 692 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∥ (𝑖 · 𝑗))
73 simprr 795 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑚 · 𝑛))
748, 62sseldi 3581 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℂ)
75 simprlr 802 . . . . . . . . . . . . . . 15 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛𝑌)
76 breq1 4616 . . . . . . . . . . . . . . . . 17 (𝑥 = 𝑛 → (𝑥𝑁𝑛𝑁))
7776, 9elrab2 3348 . . . . . . . . . . . . . . . 16 (𝑛𝑌 ↔ (𝑛 ∈ ℕ ∧ 𝑛𝑁))
7877simplbi 476 . . . . . . . . . . . . . . 15 (𝑛𝑌𝑛 ∈ ℕ)
7975, 78syl 17 . . . . . . . . . . . . . 14 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛 ∈ ℕ)
8079nncnd 10980 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛 ∈ ℂ)
8174, 80mulcomd 10005 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 · 𝑛) = (𝑛 · 𝑚))
8273, 81eqtrd 2655 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑛 · 𝑚))
8372, 82breqtrd 4639 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∥ (𝑛 · 𝑚))
8479nnzd 11425 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛 ∈ ℤ)
8536adantr 481 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑁 ∈ ℤ)
86 gcdcom 15159 . . . . . . . . . . . . 13 ((𝑖 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑖 gcd 𝑁) = (𝑁 gcd 𝑖))
8768, 85, 86syl2anc 692 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 gcd 𝑁) = (𝑁 gcd 𝑖))
8842adantr 481 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑀 ∈ ℤ)
8934nnzd 11425 . . . . . . . . . . . . . . . 16 (𝜑𝑁 ∈ ℤ)
9040nnzd 11425 . . . . . . . . . . . . . . . 16 (𝜑𝑀 ∈ ℤ)
91 gcdcom 15159 . . . . . . . . . . . . . . . 16 ((𝑁 ∈ ℤ ∧ 𝑀 ∈ ℤ) → (𝑁 gcd 𝑀) = (𝑀 gcd 𝑁))
9289, 90, 91syl2anc 692 . . . . . . . . . . . . . . 15 (𝜑 → (𝑁 gcd 𝑀) = (𝑀 gcd 𝑁))
93 dvdsmulf1o.3 . . . . . . . . . . . . . . 15 (𝜑 → (𝑀 gcd 𝑁) = 1)
9492, 93eqtrd 2655 . . . . . . . . . . . . . 14 (𝜑 → (𝑁 gcd 𝑀) = 1)
9594ad2antrr 761 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑁 gcd 𝑀) = 1)
9632adantr 481 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖𝑀)
97 rpdvds 15298 . . . . . . . . . . . . 13 (((𝑁 ∈ ℤ ∧ 𝑖 ∈ ℤ ∧ 𝑀 ∈ ℤ) ∧ ((𝑁 gcd 𝑀) = 1 ∧ 𝑖𝑀)) → (𝑁 gcd 𝑖) = 1)
9885, 68, 88, 95, 96, 97syl32anc 1331 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑁 gcd 𝑖) = 1)
9987, 98eqtrd 2655 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 gcd 𝑁) = 1)
10077simprbi 480 . . . . . . . . . . . 12 (𝑛𝑌𝑛𝑁)
10175, 100syl 17 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑛𝑁)
102 rpdvds 15298 . . . . . . . . . . 11 (((𝑖 ∈ ℤ ∧ 𝑛 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ((𝑖 gcd 𝑁) = 1 ∧ 𝑛𝑁)) → (𝑖 gcd 𝑛) = 1)
10368, 84, 85, 99, 101, 102syl32anc 1331 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 gcd 𝑛) = 1)
10466nnzd 11425 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∈ ℤ)
105 coprmdvds 15290 . . . . . . . . . . 11 ((𝑖 ∈ ℤ ∧ 𝑛 ∈ ℤ ∧ 𝑚 ∈ ℤ) → ((𝑖 ∥ (𝑛 · 𝑚) ∧ (𝑖 gcd 𝑛) = 1) → 𝑖𝑚))
10668, 84, 104, 105syl3anc 1323 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → ((𝑖 ∥ (𝑛 · 𝑚) ∧ (𝑖 gcd 𝑛) = 1) → 𝑖𝑚))
10783, 103, 106mp2and 714 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖𝑚)
108 dvdsmul1 14927 . . . . . . . . . . . 12 ((𝑚 ∈ ℤ ∧ 𝑛 ∈ ℤ) → 𝑚 ∥ (𝑚 · 𝑛))
109104, 84, 108syl2anc 692 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∥ (𝑚 · 𝑛))
11060nncnd 10980 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ∈ ℂ)
11169nncnd 10980 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 ∈ ℂ)
112110, 111mulcomd 10005 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑗 · 𝑖))
11373, 112eqtr3d 2657 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 · 𝑛) = (𝑗 · 𝑖))
114109, 113breqtrd 4639 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚 ∥ (𝑗 · 𝑖))
115 gcdcom 15159 . . . . . . . . . . . . 13 ((𝑚 ∈ ℤ ∧ 𝑁 ∈ ℤ) → (𝑚 gcd 𝑁) = (𝑁 gcd 𝑚))
116104, 85, 115syl2anc 692 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 gcd 𝑁) = (𝑁 gcd 𝑚))
11764simprbi 480 . . . . . . . . . . . . . 14 (𝑚𝑋𝑚𝑀)
11862, 117syl 17 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚𝑀)
119 rpdvds 15298 . . . . . . . . . . . . 13 (((𝑁 ∈ ℤ ∧ 𝑚 ∈ ℤ ∧ 𝑀 ∈ ℤ) ∧ ((𝑁 gcd 𝑀) = 1 ∧ 𝑚𝑀)) → (𝑁 gcd 𝑚) = 1)
12085, 104, 88, 95, 118, 119syl32anc 1331 . . . . . . . . . . . 12 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑁 gcd 𝑚) = 1)
121116, 120eqtrd 2655 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 gcd 𝑁) = 1)
12230adantr 481 . . . . . . . . . . 11 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗𝑁)
123 rpdvds 15298 . . . . . . . . . . 11 (((𝑚 ∈ ℤ ∧ 𝑗 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ((𝑚 gcd 𝑁) = 1 ∧ 𝑗𝑁)) → (𝑚 gcd 𝑗) = 1)
124104, 70, 85, 121, 122, 123syl32anc 1331 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑚 gcd 𝑗) = 1)
125 coprmdvds 15290 . . . . . . . . . . 11 ((𝑚 ∈ ℤ ∧ 𝑗 ∈ ℤ ∧ 𝑖 ∈ ℤ) → ((𝑚 ∥ (𝑗 · 𝑖) ∧ (𝑚 gcd 𝑗) = 1) → 𝑚𝑖))
126104, 70, 68, 125syl3anc 1323 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → ((𝑚 ∥ (𝑗 · 𝑖) ∧ (𝑚 gcd 𝑗) = 1) → 𝑚𝑖))
127114, 124, 126mp2and 714 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑚𝑖)
128 dvdseq 14960 . . . . . . . . 9 (((𝑖 ∈ ℕ0𝑚 ∈ ℕ0) ∧ (𝑖𝑚𝑚𝑖)) → 𝑖 = 𝑚)
12961, 67, 107, 127, 128syl22anc 1324 . . . . . . . 8 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 = 𝑚)
13060nnne0d 11009 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑖 ≠ 0)
131129oveq1d 6619 . . . . . . . . . 10 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑛) = (𝑚 · 𝑛))
13273, 131eqtr4d 2658 . . . . . . . . 9 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → (𝑖 · 𝑗) = (𝑖 · 𝑛))
133111, 80, 110, 130, 132mulcanad 10606 . . . . . . . 8 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → 𝑗 = 𝑛)
134129, 133opeq12d 4378 . . . . . . 7 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ ((𝑚𝑋𝑛𝑌) ∧ (𝑖 · 𝑗) = (𝑚 · 𝑛))) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)
135134expr 642 . . . . . 6 (((𝜑 ∧ (𝑖𝑋𝑗𝑌)) ∧ (𝑚𝑋𝑛𝑌)) → ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
136135ralrimivva 2965 . . . . 5 ((𝜑 ∧ (𝑖𝑋𝑗𝑌)) → ∀𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
137136ralrimivva 2965 . . . 4 (𝜑 → ∀𝑖𝑋𝑗𝑌𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
138 fvres 6164 . . . . . . . . 9 (𝑢 ∈ (𝑋 × 𝑌) → (( · ↾ (𝑋 × 𝑌))‘𝑢) = ( · ‘𝑢))
139 fvres 6164 . . . . . . . . 9 (𝑣 ∈ (𝑋 × 𝑌) → (( · ↾ (𝑋 × 𝑌))‘𝑣) = ( · ‘𝑣))
140138, 139eqeqan12d 2637 . . . . . . . 8 ((𝑢 ∈ (𝑋 × 𝑌) ∧ 𝑣 ∈ (𝑋 × 𝑌)) → ((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) ↔ ( · ‘𝑢) = ( · ‘𝑣)))
141140imbi1d 331 . . . . . . 7 ((𝑢 ∈ (𝑋 × 𝑌) ∧ 𝑣 ∈ (𝑋 × 𝑌)) → (((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ (( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣)))
142141ralbidva 2979 . . . . . 6 (𝑢 ∈ (𝑋 × 𝑌) → (∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣)))
143142ralbiia 2973 . . . . 5 (∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣))
144 fveq2 6148 . . . . . . . . . . 11 (𝑣 = ⟨𝑚, 𝑛⟩ → ( · ‘𝑣) = ( · ‘⟨𝑚, 𝑛⟩))
145 df-ov 6607 . . . . . . . . . . 11 (𝑚 · 𝑛) = ( · ‘⟨𝑚, 𝑛⟩)
146144, 145syl6eqr 2673 . . . . . . . . . 10 (𝑣 = ⟨𝑚, 𝑛⟩ → ( · ‘𝑣) = (𝑚 · 𝑛))
147146eqeq2d 2631 . . . . . . . . 9 (𝑣 = ⟨𝑚, 𝑛⟩ → (( · ‘𝑢) = ( · ‘𝑣) ↔ ( · ‘𝑢) = (𝑚 · 𝑛)))
148 eqeq2 2632 . . . . . . . . 9 (𝑣 = ⟨𝑚, 𝑛⟩ → (𝑢 = 𝑣𝑢 = ⟨𝑚, 𝑛⟩))
149147, 148imbi12d 334 . . . . . . . 8 (𝑣 = ⟨𝑚, 𝑛⟩ → ((( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ (( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩)))
150149ralxp 5223 . . . . . . 7 (∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑚𝑋𝑛𝑌 (( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩))
151 fveq2 6148 . . . . . . . . . . 11 (𝑢 = ⟨𝑖, 𝑗⟩ → ( · ‘𝑢) = ( · ‘⟨𝑖, 𝑗⟩))
152 df-ov 6607 . . . . . . . . . . 11 (𝑖 · 𝑗) = ( · ‘⟨𝑖, 𝑗⟩)
153151, 152syl6eqr 2673 . . . . . . . . . 10 (𝑢 = ⟨𝑖, 𝑗⟩ → ( · ‘𝑢) = (𝑖 · 𝑗))
154153eqeq1d 2623 . . . . . . . . 9 (𝑢 = ⟨𝑖, 𝑗⟩ → (( · ‘𝑢) = (𝑚 · 𝑛) ↔ (𝑖 · 𝑗) = (𝑚 · 𝑛)))
155 eqeq1 2625 . . . . . . . . 9 (𝑢 = ⟨𝑖, 𝑗⟩ → (𝑢 = ⟨𝑚, 𝑛⟩ ↔ ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
156154, 155imbi12d 334 . . . . . . . 8 (𝑢 = ⟨𝑖, 𝑗⟩ → ((( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩) ↔ ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)))
1571562ralbidv 2983 . . . . . . 7 (𝑢 = ⟨𝑖, 𝑗⟩ → (∀𝑚𝑋𝑛𝑌 (( · ‘𝑢) = (𝑚 · 𝑛) → 𝑢 = ⟨𝑚, 𝑛⟩) ↔ ∀𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)))
158150, 157syl5bb 272 . . . . . 6 (𝑢 = ⟨𝑖, 𝑗⟩ → (∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩)))
159158ralxp 5223 . . . . 5 (∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)(( · ‘𝑢) = ( · ‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑖𝑋𝑗𝑌𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
160143, 159bitri 264 . . . 4 (∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣) ↔ ∀𝑖𝑋𝑗𝑌𝑚𝑋𝑛𝑌 ((𝑖 · 𝑗) = (𝑚 · 𝑛) → ⟨𝑖, 𝑗⟩ = ⟨𝑚, 𝑛⟩))
161137, 160sylibr 224 . . 3 (𝜑 → ∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣))
162 dff13 6466 . . 3 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1𝑍 ↔ (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍 ∧ ∀𝑢 ∈ (𝑋 × 𝑌)∀𝑣 ∈ (𝑋 × 𝑌)((( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘𝑣) → 𝑢 = 𝑣)))
16359, 161, 162sylanbrc 697 . 2 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1𝑍)
164 breq1 4616 . . . . . . . . . . . 12 (𝑥 = 𝑤 → (𝑥 ∥ (𝑀 · 𝑁) ↔ 𝑤 ∥ (𝑀 · 𝑁)))
165164, 53elrab2 3348 . . . . . . . . . . 11 (𝑤𝑍 ↔ (𝑤 ∈ ℕ ∧ 𝑤 ∥ (𝑀 · 𝑁)))
166165simplbi 476 . . . . . . . . . 10 (𝑤𝑍𝑤 ∈ ℕ)
167166adantl 482 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑤 ∈ ℕ)
168167nnzd 11425 . . . . . . . 8 ((𝜑𝑤𝑍) → 𝑤 ∈ ℤ)
16940adantr 481 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑀 ∈ ℕ)
170169nnzd 11425 . . . . . . . 8 ((𝜑𝑤𝑍) → 𝑀 ∈ ℤ)
171169nnne0d 11009 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑀 ≠ 0)
172 simpr 477 . . . . . . . . . 10 ((𝑤 = 0 ∧ 𝑀 = 0) → 𝑀 = 0)
173172necon3ai 2815 . . . . . . . . 9 (𝑀 ≠ 0 → ¬ (𝑤 = 0 ∧ 𝑀 = 0))
174171, 173syl 17 . . . . . . . 8 ((𝜑𝑤𝑍) → ¬ (𝑤 = 0 ∧ 𝑀 = 0))
175 gcdn0cl 15148 . . . . . . . 8 (((𝑤 ∈ ℤ ∧ 𝑀 ∈ ℤ) ∧ ¬ (𝑤 = 0 ∧ 𝑀 = 0)) → (𝑤 gcd 𝑀) ∈ ℕ)
176168, 170, 174, 175syl21anc 1322 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑀) ∈ ℕ)
177 gcddvds 15149 . . . . . . . . 9 ((𝑤 ∈ ℤ ∧ 𝑀 ∈ ℤ) → ((𝑤 gcd 𝑀) ∥ 𝑤 ∧ (𝑤 gcd 𝑀) ∥ 𝑀))
178168, 170, 177syl2anc 692 . . . . . . . 8 ((𝜑𝑤𝑍) → ((𝑤 gcd 𝑀) ∥ 𝑤 ∧ (𝑤 gcd 𝑀) ∥ 𝑀))
179178simprd 479 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑀) ∥ 𝑀)
180 breq1 4616 . . . . . . . 8 (𝑥 = (𝑤 gcd 𝑀) → (𝑥𝑀 ↔ (𝑤 gcd 𝑀) ∥ 𝑀))
181180, 4elrab2 3348 . . . . . . 7 ((𝑤 gcd 𝑀) ∈ 𝑋 ↔ ((𝑤 gcd 𝑀) ∈ ℕ ∧ (𝑤 gcd 𝑀) ∥ 𝑀))
182176, 179, 181sylanbrc 697 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑀) ∈ 𝑋)
18334adantr 481 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑁 ∈ ℕ)
184183nnzd 11425 . . . . . . . 8 ((𝜑𝑤𝑍) → 𝑁 ∈ ℤ)
185183nnne0d 11009 . . . . . . . . 9 ((𝜑𝑤𝑍) → 𝑁 ≠ 0)
186 simpr 477 . . . . . . . . . 10 ((𝑤 = 0 ∧ 𝑁 = 0) → 𝑁 = 0)
187186necon3ai 2815 . . . . . . . . 9 (𝑁 ≠ 0 → ¬ (𝑤 = 0 ∧ 𝑁 = 0))
188185, 187syl 17 . . . . . . . 8 ((𝜑𝑤𝑍) → ¬ (𝑤 = 0 ∧ 𝑁 = 0))
189 gcdn0cl 15148 . . . . . . . 8 (((𝑤 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ ¬ (𝑤 = 0 ∧ 𝑁 = 0)) → (𝑤 gcd 𝑁) ∈ ℕ)
190168, 184, 188, 189syl21anc 1322 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑁) ∈ ℕ)
191 gcddvds 15149 . . . . . . . . 9 ((𝑤 ∈ ℤ ∧ 𝑁 ∈ ℤ) → ((𝑤 gcd 𝑁) ∥ 𝑤 ∧ (𝑤 gcd 𝑁) ∥ 𝑁))
192168, 184, 191syl2anc 692 . . . . . . . 8 ((𝜑𝑤𝑍) → ((𝑤 gcd 𝑁) ∥ 𝑤 ∧ (𝑤 gcd 𝑁) ∥ 𝑁))
193192simprd 479 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑁) ∥ 𝑁)
194 breq1 4616 . . . . . . . 8 (𝑥 = (𝑤 gcd 𝑁) → (𝑥𝑁 ↔ (𝑤 gcd 𝑁) ∥ 𝑁))
195194, 9elrab2 3348 . . . . . . 7 ((𝑤 gcd 𝑁) ∈ 𝑌 ↔ ((𝑤 gcd 𝑁) ∈ ℕ ∧ (𝑤 gcd 𝑁) ∥ 𝑁))
196190, 193, 195sylanbrc 697 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd 𝑁) ∈ 𝑌)
197 opelxpi 5108 . . . . . 6 (((𝑤 gcd 𝑀) ∈ 𝑋 ∧ (𝑤 gcd 𝑁) ∈ 𝑌) → ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌))
198182, 196, 197syl2anc 692 . . . . 5 ((𝜑𝑤𝑍) → ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌))
199 fvres 6164 . . . . . . 7 (⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌) → (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
200198, 199syl 17 . . . . . 6 ((𝜑𝑤𝑍) → (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
20193adantr 481 . . . . . . . 8 ((𝜑𝑤𝑍) → (𝑀 gcd 𝑁) = 1)
202 rpmulgcd2 15294 . . . . . . . 8 (((𝑤 ∈ ℤ ∧ 𝑀 ∈ ℤ ∧ 𝑁 ∈ ℤ) ∧ (𝑀 gcd 𝑁) = 1) → (𝑤 gcd (𝑀 · 𝑁)) = ((𝑤 gcd 𝑀) · (𝑤 gcd 𝑁)))
203168, 170, 184, 201, 202syl31anc 1326 . . . . . . 7 ((𝜑𝑤𝑍) → (𝑤 gcd (𝑀 · 𝑁)) = ((𝑤 gcd 𝑀) · (𝑤 gcd 𝑁)))
204 df-ov 6607 . . . . . . 7 ((𝑤 gcd 𝑀) · (𝑤 gcd 𝑁)) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩)
205203, 204syl6eq 2671 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd (𝑀 · 𝑁)) = ( · ‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
206165simprbi 480 . . . . . . . 8 (𝑤𝑍𝑤 ∥ (𝑀 · 𝑁))
207206adantl 482 . . . . . . 7 ((𝜑𝑤𝑍) → 𝑤 ∥ (𝑀 · 𝑁))
20840, 34nnmulcld 11012 . . . . . . . 8 (𝜑 → (𝑀 · 𝑁) ∈ ℕ)
209 gcdeq 15196 . . . . . . . 8 ((𝑤 ∈ ℕ ∧ (𝑀 · 𝑁) ∈ ℕ) → ((𝑤 gcd (𝑀 · 𝑁)) = 𝑤𝑤 ∥ (𝑀 · 𝑁)))
210166, 208, 209syl2anr 495 . . . . . . 7 ((𝜑𝑤𝑍) → ((𝑤 gcd (𝑀 · 𝑁)) = 𝑤𝑤 ∥ (𝑀 · 𝑁)))
211207, 210mpbird 247 . . . . . 6 ((𝜑𝑤𝑍) → (𝑤 gcd (𝑀 · 𝑁)) = 𝑤)
212200, 205, 2113eqtr2rd 2662 . . . . 5 ((𝜑𝑤𝑍) → 𝑤 = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
213 fveq2 6148 . . . . . . 7 (𝑢 = ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ → (( · ↾ (𝑋 × 𝑌))‘𝑢) = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩))
214213eqeq2d 2631 . . . . . 6 (𝑢 = ⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ → (𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢) ↔ 𝑤 = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩)))
215214rspcev 3295 . . . . 5 ((⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩ ∈ (𝑋 × 𝑌) ∧ 𝑤 = (( · ↾ (𝑋 × 𝑌))‘⟨(𝑤 gcd 𝑀), (𝑤 gcd 𝑁)⟩)) → ∃𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢))
216198, 212, 215syl2anc 692 . . . 4 ((𝜑𝑤𝑍) → ∃𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢))
217216ralrimiva 2960 . . 3 (𝜑 → ∀𝑤𝑍𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢))
218 dffo3 6330 . . 3 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–onto𝑍 ↔ (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)⟶𝑍 ∧ ∀𝑤𝑍𝑢 ∈ (𝑋 × 𝑌)𝑤 = (( · ↾ (𝑋 × 𝑌))‘𝑢)))
21959, 217, 218sylanbrc 697 . 2 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–onto𝑍)
220 df-f1o 5854 . 2 (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1-onto𝑍 ↔ (( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1𝑍 ∧ ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–onto𝑍))
221163, 219, 220sylanbrc 697 1 (𝜑 → ( · ↾ (𝑋 × 𝑌)):(𝑋 × 𝑌)–1-1-onto𝑍)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 196  wa 384   = wceq 1480  wcel 1987  wne 2790  wral 2907  wrex 2908  {crab 2911  wss 3555  cop 4154   class class class wbr 4613   × cxp 5072  cres 5076   Fn wfn 5842  wf 5843  1-1wf1 5844  ontowfo 5845  1-1-ontowf1o 5846  cfv 5847  (class class class)co 6604  cc 9878  0cc0 9880  1c1 9881   · cmul 9885  cn 10964  0cn0 11236  cz 11321  cdvds 14907   gcd cgcd 15140
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1719  ax-4 1734  ax-5 1836  ax-6 1885  ax-7 1932  ax-8 1989  ax-9 1996  ax-10 2016  ax-11 2031  ax-12 2044  ax-13 2245  ax-ext 2601  ax-sep 4741  ax-nul 4749  ax-pow 4803  ax-pr 4867  ax-un 6902  ax-cnex 9936  ax-resscn 9937  ax-1cn 9938  ax-icn 9939  ax-addcl 9940  ax-addrcl 9941  ax-mulcl 9942  ax-mulrcl 9943  ax-mulcom 9944  ax-addass 9945  ax-mulass 9946  ax-distr 9947  ax-i2m1 9948  ax-1ne0 9949  ax-1rid 9950  ax-rnegex 9951  ax-rrecex 9952  ax-cnre 9953  ax-pre-lttri 9954  ax-pre-lttrn 9955  ax-pre-ltadd 9956  ax-pre-mulgt0 9957  ax-pre-sup 9958  ax-mulf 9960
This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1037  df-3an 1038  df-tru 1483  df-ex 1702  df-nf 1707  df-sb 1878  df-eu 2473  df-mo 2474  df-clab 2608  df-cleq 2614  df-clel 2617  df-nfc 2750  df-ne 2791  df-nel 2894  df-ral 2912  df-rex 2913  df-reu 2914  df-rmo 2915  df-rab 2916  df-v 3188  df-sbc 3418  df-csb 3515  df-dif 3558  df-un 3560  df-in 3562  df-ss 3569  df-pss 3571  df-nul 3892  df-if 4059  df-pw 4132  df-sn 4149  df-pr 4151  df-tp 4153  df-op 4155  df-uni 4403  df-iun 4487  df-br 4614  df-opab 4674  df-mpt 4675  df-tr 4713  df-eprel 4985  df-id 4989  df-po 4995  df-so 4996  df-fr 5033  df-we 5035  df-xp 5080  df-rel 5081  df-cnv 5082  df-co 5083  df-dm 5084  df-rn 5085  df-res 5086  df-ima 5087  df-pred 5639  df-ord 5685  df-on 5686  df-lim 5687  df-suc 5688  df-iota 5810  df-fun 5849  df-fn 5850  df-f 5851  df-f1 5852  df-fo 5853  df-f1o 5854  df-fv 5855  df-riota 6565  df-ov 6607  df-oprab 6608  df-mpt2 6609  df-om 7013  df-2nd 7114  df-wrecs 7352  df-recs 7413  df-rdg 7451  df-er 7687  df-en 7900  df-dom 7901  df-sdom 7902  df-sup 8292  df-inf 8293  df-pnf 10020  df-mnf 10021  df-xr 10022  df-ltxr 10023  df-le 10024  df-sub 10212  df-neg 10213  df-div 10629  df-nn 10965  df-2 11023  df-3 11024  df-n0 11237  df-z 11322  df-uz 11632  df-rp 11777  df-fl 12533  df-mod 12609  df-seq 12742  df-exp 12801  df-cj 13773  df-re 13774  df-im 13775  df-sqrt 13909  df-abs 13910  df-dvds 14908  df-gcd 15141
This theorem is referenced by:  fsumdvdsmul  24821
  Copyright terms: Public domain W3C validator