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

Theorem rpexp 16060
Description: If two numbers 𝐴 and 𝐵 are relatively prime, then they are still relatively prime if raised to a power. (Contributed by Mario Carneiro, 24-Feb-2014.)
Assertion
Ref Expression
rpexp ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1))

Proof of Theorem rpexp
Dummy variable 𝑝 is distinct from all other variables.
StepHypRef Expression
1 0exp 13467 . . . . . 6 (𝑁 ∈ ℕ → (0↑𝑁) = 0)
21oveq1d 7161 . . . . 5 (𝑁 ∈ ℕ → ((0↑𝑁) gcd 0) = (0 gcd 0))
32eqeq1d 2826 . . . 4 (𝑁 ∈ ℕ → (((0↑𝑁) gcd 0) = 1 ↔ (0 gcd 0) = 1))
4 oveq1 7153 . . . . . . 7 (𝐴 = 0 → (𝐴𝑁) = (0↑𝑁))
5 oveq12 7155 . . . . . . 7 (((𝐴𝑁) = (0↑𝑁) ∧ 𝐵 = 0) → ((𝐴𝑁) gcd 𝐵) = ((0↑𝑁) gcd 0))
64, 5sylan 583 . . . . . 6 ((𝐴 = 0 ∧ 𝐵 = 0) → ((𝐴𝑁) gcd 𝐵) = ((0↑𝑁) gcd 0))
76eqeq1d 2826 . . . . 5 ((𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ ((0↑𝑁) gcd 0) = 1))
8 oveq12 7155 . . . . . 6 ((𝐴 = 0 ∧ 𝐵 = 0) → (𝐴 gcd 𝐵) = (0 gcd 0))
98eqeq1d 2826 . . . . 5 ((𝐴 = 0 ∧ 𝐵 = 0) → ((𝐴 gcd 𝐵) = 1 ↔ (0 gcd 0) = 1))
107, 9bibi12d 349 . . . 4 ((𝐴 = 0 ∧ 𝐵 = 0) → ((((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1) ↔ (((0↑𝑁) gcd 0) = 1 ↔ (0 gcd 0) = 1)))
113, 10syl5ibrcom 250 . . 3 (𝑁 ∈ ℕ → ((𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1)))
12113ad2ant3 1132 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → ((𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1)))
13 exprmfct 16044 . . . . . . 7 (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) → ∃𝑝 ∈ ℙ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵))
14 simpl1 1188 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝐴 ∈ ℤ)
15 simpl3 1190 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝑁 ∈ ℕ)
1615nnnn0d 11950 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝑁 ∈ ℕ0)
17 zexpcl 13447 . . . . . . . . . . . . . . . . 17 ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ0) → (𝐴𝑁) ∈ ℤ)
1814, 16, 17syl2anc 587 . . . . . . . . . . . . . . . 16 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴𝑁) ∈ ℤ)
1918adantr 484 . . . . . . . . . . . . . . 15 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴𝑁) ∈ ℤ)
20 simpl2 1189 . . . . . . . . . . . . . . . 16 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝐵 ∈ ℤ)
2120adantr 484 . . . . . . . . . . . . . . 15 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝐵 ∈ ℤ)
22 gcddvds 15848 . . . . . . . . . . . . . . 15 (((𝐴𝑁) ∈ ℤ ∧ 𝐵 ∈ ℤ) → (((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵))
2319, 21, 22syl2anc 587 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵))
2423simpld 498 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁))
25 prmz 16015 . . . . . . . . . . . . . . 15 (𝑝 ∈ ℙ → 𝑝 ∈ ℤ)
2625adantl 485 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℤ)
27 simpr 488 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ¬ (𝐴 = 0 ∧ 𝐵 = 0))
2814zcnd 12083 . . . . . . . . . . . . . . . . . . . 20 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝐴 ∈ ℂ)
29 expeq0 13462 . . . . . . . . . . . . . . . . . . . 20 ((𝐴 ∈ ℂ ∧ 𝑁 ∈ ℕ) → ((𝐴𝑁) = 0 ↔ 𝐴 = 0))
3028, 15, 29syl2anc 587 . . . . . . . . . . . . . . . . . . 19 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) = 0 ↔ 𝐴 = 0))
3130anbi1d 632 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) = 0 ∧ 𝐵 = 0) ↔ (𝐴 = 0 ∧ 𝐵 = 0)))
3227, 31mtbird 328 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ¬ ((𝐴𝑁) = 0 ∧ 𝐵 = 0))
33 gcdn0cl 15847 . . . . . . . . . . . . . . . . 17 ((((𝐴𝑁) ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ ¬ ((𝐴𝑁) = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) gcd 𝐵) ∈ ℕ)
3418, 20, 32, 33syl21anc 836 . . . . . . . . . . . . . . . 16 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) gcd 𝐵) ∈ ℕ)
3534nnzd 12081 . . . . . . . . . . . . . . 15 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) gcd 𝐵) ∈ ℤ)
3635adantr 484 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴𝑁) gcd 𝐵) ∈ ℤ)
37 dvdstr 15644 . . . . . . . . . . . . . 14 ((𝑝 ∈ ℤ ∧ ((𝐴𝑁) gcd 𝐵) ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
3826, 36, 19, 37syl3anc 1368 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
3924, 38mpan2d 693 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → 𝑝 ∥ (𝐴𝑁)))
40 simpr 488 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℙ)
41 simpll1 1209 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝐴 ∈ ℤ)
4215adantr 484 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝑁 ∈ ℕ)
43 prmdvdsexp 16055 . . . . . . . . . . . . 13 ((𝑝 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑝 ∥ (𝐴𝑁) ↔ 𝑝𝐴))
4440, 41, 42, 43syl3anc 1368 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴𝑁) ↔ 𝑝𝐴))
4539, 44sylibd 242 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → 𝑝𝐴))
4623simprd 499 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴𝑁) gcd 𝐵) ∥ 𝐵)
47 dvdstr 15644 . . . . . . . . . . . . 13 ((𝑝 ∈ ℤ ∧ ((𝐴𝑁) gcd 𝐵) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
4826, 36, 21, 47syl3anc 1368 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
4946, 48mpan2d 693 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → 𝑝𝐵))
5045, 49jcad 516 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝑝𝐴𝑝𝐵)))
51 dvdsgcd 15888 . . . . . . . . . . 11 ((𝑝 ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝𝐴𝑝𝐵) → 𝑝 ∥ (𝐴 gcd 𝐵)))
5226, 41, 21, 51syl3anc 1368 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝𝐴𝑝𝐵) → 𝑝 ∥ (𝐴 gcd 𝐵)))
53 nprmdvds1 16046 . . . . . . . . . . . . 13 (𝑝 ∈ ℙ → ¬ 𝑝 ∥ 1)
54 breq2 5057 . . . . . . . . . . . . . 14 ((𝐴 gcd 𝐵) = 1 → (𝑝 ∥ (𝐴 gcd 𝐵) ↔ 𝑝 ∥ 1))
5554notbid 321 . . . . . . . . . . . . 13 ((𝐴 gcd 𝐵) = 1 → (¬ 𝑝 ∥ (𝐴 gcd 𝐵) ↔ ¬ 𝑝 ∥ 1))
5653, 55syl5ibrcom 250 . . . . . . . . . . . 12 (𝑝 ∈ ℙ → ((𝐴 gcd 𝐵) = 1 → ¬ 𝑝 ∥ (𝐴 gcd 𝐵)))
5756necon2ad 3029 . . . . . . . . . . 11 (𝑝 ∈ ℙ → (𝑝 ∥ (𝐴 gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
5857adantl 485 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
5950, 52, 583syld 60 . . . . . . . . 9 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
6059rexlimdva 3277 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
61 gcdn0cl 15847 . . . . . . . . . 10 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℕ)
62613adantl3 1165 . . . . . . . . 9 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℕ)
63 eluz2b3 12317 . . . . . . . . . 10 ((𝐴 gcd 𝐵) ∈ (ℤ‘2) ↔ ((𝐴 gcd 𝐵) ∈ ℕ ∧ (𝐴 gcd 𝐵) ≠ 1))
6463baib 539 . . . . . . . . 9 ((𝐴 gcd 𝐵) ∈ ℕ → ((𝐴 gcd 𝐵) ∈ (ℤ‘2) ↔ (𝐴 gcd 𝐵) ≠ 1))
6562, 64syl 17 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 gcd 𝐵) ∈ (ℤ‘2) ↔ (𝐴 gcd 𝐵) ≠ 1))
6660, 65sylibrd 262 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝐴 gcd 𝐵) ∈ (ℤ‘2)))
6713, 66syl5 34 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) → (𝐴 gcd 𝐵) ∈ (ℤ‘2)))
68 exprmfct 16044 . . . . . . 7 ((𝐴 gcd 𝐵) ∈ (ℤ‘2) → ∃𝑝 ∈ ℙ 𝑝 ∥ (𝐴 gcd 𝐵))
69 gcddvds 15848 . . . . . . . . . . . . . . 15 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝐴 gcd 𝐵) ∥ 𝐴 ∧ (𝐴 gcd 𝐵) ∥ 𝐵))
7041, 21, 69syl2anc 587 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴 gcd 𝐵) ∥ 𝐴 ∧ (𝐴 gcd 𝐵) ∥ 𝐵))
7170simpld 498 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∥ 𝐴)
72 iddvdsexp 15631 . . . . . . . . . . . . . 14 ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ) → 𝐴 ∥ (𝐴𝑁))
7341, 42, 72syl2anc 587 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝐴 ∥ (𝐴𝑁))
7462nnzd 12081 . . . . . . . . . . . . . . 15 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℤ)
7574adantr 484 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∈ ℤ)
76 dvdstr 15644 . . . . . . . . . . . . . 14 (((𝐴 gcd 𝐵) ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ) → (((𝐴 gcd 𝐵) ∥ 𝐴𝐴 ∥ (𝐴𝑁)) → (𝐴 gcd 𝐵) ∥ (𝐴𝑁)))
7775, 41, 19, 76syl3anc 1368 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (((𝐴 gcd 𝐵) ∥ 𝐴𝐴 ∥ (𝐴𝑁)) → (𝐴 gcd 𝐵) ∥ (𝐴𝑁)))
7871, 73, 77mp2and 698 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∥ (𝐴𝑁))
79 dvdstr 15644 . . . . . . . . . . . . 13 ((𝑝 ∈ ℤ ∧ (𝐴 gcd 𝐵) ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
8026, 75, 19, 79syl3anc 1368 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
8178, 80mpan2d 693 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → 𝑝 ∥ (𝐴𝑁)))
8270simprd 499 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∥ 𝐵)
83 dvdstr 15644 . . . . . . . . . . . . 13 ((𝑝 ∈ ℤ ∧ (𝐴 gcd 𝐵) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
8426, 75, 21, 83syl3anc 1368 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
8582, 84mpan2d 693 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → 𝑝𝐵))
8681, 85jcad 516 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → (𝑝 ∥ (𝐴𝑁) ∧ 𝑝𝐵)))
87 dvdsgcd 15888 . . . . . . . . . . 11 ((𝑝 ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝 ∥ (𝐴𝑁) ∧ 𝑝𝐵) → 𝑝 ∥ ((𝐴𝑁) gcd 𝐵)))
8826, 19, 21, 87syl3anc 1368 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (𝐴𝑁) ∧ 𝑝𝐵) → 𝑝 ∥ ((𝐴𝑁) gcd 𝐵)))
89 breq2 5057 . . . . . . . . . . . . . 14 (((𝐴𝑁) gcd 𝐵) = 1 → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ↔ 𝑝 ∥ 1))
9089notbid 321 . . . . . . . . . . . . 13 (((𝐴𝑁) gcd 𝐵) = 1 → (¬ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ↔ ¬ 𝑝 ∥ 1))
9153, 90syl5ibrcom 250 . . . . . . . . . . . 12 (𝑝 ∈ ℙ → (((𝐴𝑁) gcd 𝐵) = 1 → ¬ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵)))
9291necon2ad 3029 . . . . . . . . . . 11 (𝑝 ∈ ℙ → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
9392adantl 485 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
9486, 88, 933syld 60 . . . . . . . . 9 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
9594rexlimdva 3277 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ (𝐴 gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
96 eluz2b3 12317 . . . . . . . . . 10 (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ (((𝐴𝑁) gcd 𝐵) ∈ ℕ ∧ ((𝐴𝑁) gcd 𝐵) ≠ 1))
9796baib 539 . . . . . . . . 9 (((𝐴𝑁) gcd 𝐵) ∈ ℕ → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ ((𝐴𝑁) gcd 𝐵) ≠ 1))
9834, 97syl 17 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ ((𝐴𝑁) gcd 𝐵) ≠ 1))
9995, 98sylibrd 262 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ (𝐴 gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2)))
10068, 99syl5 34 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 gcd 𝐵) ∈ (ℤ‘2) → ((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2)))
10167, 100impbid 215 . . . . 5 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ (𝐴 gcd 𝐵) ∈ (ℤ‘2)))
102101, 98, 653bitr3d 312 . . . 4 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ≠ 1 ↔ (𝐴 gcd 𝐵) ≠ 1))
103102necon4bid 3059 . . 3 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1))
104103ex 416 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (¬ (𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1)))
10512, 104pm2.61d 182 1 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 209  wa 399  w3a 1084   = wceq 1538  wcel 2115  wne 3014  wrex 3134   class class class wbr 5053  cfv 6344  (class class class)co 7146  cc 10529  0cc0 10531  1c1 10532  cn 11632  2c2 11687  0cn0 11892  cz 11976  cuz 12238  cexp 13432  cdvds 15605   gcd cgcd 15839  cprime 16011
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1971  ax-7 2016  ax-8 2117  ax-9 2125  ax-10 2146  ax-11 2162  ax-12 2179  ax-ext 2796  ax-sep 5190  ax-nul 5197  ax-pow 5254  ax-pr 5318  ax-un 7452  ax-cnex 10587  ax-resscn 10588  ax-1cn 10589  ax-icn 10590  ax-addcl 10591  ax-addrcl 10592  ax-mulcl 10593  ax-mulrcl 10594  ax-mulcom 10595  ax-addass 10596  ax-mulass 10597  ax-distr 10598  ax-i2m1 10599  ax-1ne0 10600  ax-1rid 10601  ax-rnegex 10602  ax-rrecex 10603  ax-cnre 10604  ax-pre-lttri 10605  ax-pre-lttrn 10606  ax-pre-ltadd 10607  ax-pre-mulgt0 10608  ax-pre-sup 10609
This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2071  df-mo 2624  df-eu 2655  df-clab 2803  df-cleq 2817  df-clel 2896  df-nfc 2964  df-ne 3015  df-nel 3119  df-ral 3138  df-rex 3139  df-reu 3140  df-rmo 3141  df-rab 3142  df-v 3482  df-sbc 3759  df-csb 3867  df-dif 3922  df-un 3924  df-in 3926  df-ss 3936  df-pss 3938  df-nul 4277  df-if 4451  df-pw 4524  df-sn 4551  df-pr 4553  df-tp 4555  df-op 4557  df-uni 4826  df-iun 4908  df-br 5054  df-opab 5116  df-mpt 5134  df-tr 5160  df-id 5448  df-eprel 5453  df-po 5462  df-so 5463  df-fr 5502  df-we 5504  df-xp 5549  df-rel 5550  df-cnv 5551  df-co 5552  df-dm 5553  df-rn 5554  df-res 5555  df-ima 5556  df-pred 6136  df-ord 6182  df-on 6183  df-lim 6184  df-suc 6185  df-iota 6303  df-fun 6346  df-fn 6347  df-f 6348  df-f1 6349  df-fo 6350  df-f1o 6351  df-fv 6352  df-riota 7104  df-ov 7149  df-oprab 7150  df-mpo 7151  df-om 7572  df-1st 7681  df-2nd 7682  df-wrecs 7939  df-recs 8000  df-rdg 8038  df-1o 8094  df-2o 8095  df-er 8281  df-en 8502  df-dom 8503  df-sdom 8504  df-fin 8505  df-sup 8899  df-inf 8900  df-pnf 10671  df-mnf 10672  df-xr 10673  df-ltxr 10674  df-le 10675  df-sub 10866  df-neg 10867  df-div 11292  df-nn 11633  df-2 11695  df-3 11696  df-n0 11893  df-z 11977  df-uz 12239  df-rp 12385  df-fz 12893  df-fl 13164  df-mod 13240  df-seq 13372  df-exp 13433  df-cj 14456  df-re 14457  df-im 14458  df-sqrt 14592  df-abs 14593  df-dvds 15606  df-gcd 15840  df-prm 16012
This theorem is referenced by:  rpexp1i  16061  phiprmpw  16109  pockthlem  16237  logbgcd1irr  25378
  Copyright terms: Public domain W3C validator