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

Theorem rpexp 16425
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 13816 . . . . . 6 (𝑁 ∈ ℕ → (0↑𝑁) = 0)
21oveq1d 7292 . . . . 5 (𝑁 ∈ ℕ → ((0↑𝑁) gcd 0) = (0 gcd 0))
32eqeq1d 2740 . . . 4 (𝑁 ∈ ℕ → (((0↑𝑁) gcd 0) = 1 ↔ (0 gcd 0) = 1))
4 oveq1 7284 . . . . . . 7 (𝐴 = 0 → (𝐴𝑁) = (0↑𝑁))
5 oveq12 7286 . . . . . . 7 (((𝐴𝑁) = (0↑𝑁) ∧ 𝐵 = 0) → ((𝐴𝑁) gcd 𝐵) = ((0↑𝑁) gcd 0))
64, 5sylan 580 . . . . . 6 ((𝐴 = 0 ∧ 𝐵 = 0) → ((𝐴𝑁) gcd 𝐵) = ((0↑𝑁) gcd 0))
76eqeq1d 2740 . . . . 5 ((𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ ((0↑𝑁) gcd 0) = 1))
8 oveq12 7286 . . . . . 6 ((𝐴 = 0 ∧ 𝐵 = 0) → (𝐴 gcd 𝐵) = (0 gcd 0))
98eqeq1d 2740 . . . . 5 ((𝐴 = 0 ∧ 𝐵 = 0) → ((𝐴 gcd 𝐵) = 1 ↔ (0 gcd 0) = 1))
107, 9bibi12d 346 . . . 4 ((𝐴 = 0 ∧ 𝐵 = 0) → ((((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1) ↔ (((0↑𝑁) gcd 0) = 1 ↔ (0 gcd 0) = 1)))
113, 10syl5ibrcom 246 . . 3 (𝑁 ∈ ℕ → ((𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1)))
12113ad2ant3 1134 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → ((𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1)))
13 exprmfct 16407 . . . . . . 7 (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) → ∃𝑝 ∈ ℙ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵))
14 simpl1 1190 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝐴 ∈ ℤ)
15 simpl3 1192 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝑁 ∈ ℕ)
1615nnnn0d 12291 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝑁 ∈ ℕ0)
17 zexpcl 13795 . . . . . . . . . . . . . . . . 17 ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ0) → (𝐴𝑁) ∈ ℤ)
1814, 16, 17syl2anc 584 . . . . . . . . . . . . . . . 16 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴𝑁) ∈ ℤ)
1918adantr 481 . . . . . . . . . . . . . . 15 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴𝑁) ∈ ℤ)
20 simpl2 1191 . . . . . . . . . . . . . . . 16 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝐵 ∈ ℤ)
2120adantr 481 . . . . . . . . . . . . . . 15 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝐵 ∈ ℤ)
22 gcddvds 16208 . . . . . . . . . . . . . . 15 (((𝐴𝑁) ∈ ℤ ∧ 𝐵 ∈ ℤ) → (((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵))
2319, 21, 22syl2anc 584 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵))
2423simpld 495 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁))
25 prmz 16378 . . . . . . . . . . . . . . 15 (𝑝 ∈ ℙ → 𝑝 ∈ ℤ)
2625adantl 482 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℤ)
27 simpr 485 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ¬ (𝐴 = 0 ∧ 𝐵 = 0))
2814zcnd 12425 . . . . . . . . . . . . . . . . . . . 20 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → 𝐴 ∈ ℂ)
29 expeq0 13811 . . . . . . . . . . . . . . . . . . . 20 ((𝐴 ∈ ℂ ∧ 𝑁 ∈ ℕ) → ((𝐴𝑁) = 0 ↔ 𝐴 = 0))
3028, 15, 29syl2anc 584 . . . . . . . . . . . . . . . . . . 19 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) = 0 ↔ 𝐴 = 0))
3130anbi1d 630 . . . . . . . . . . . . . . . . . 18 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) = 0 ∧ 𝐵 = 0) ↔ (𝐴 = 0 ∧ 𝐵 = 0)))
3227, 31mtbird 325 . . . . . . . . . . . . . . . . 17 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ¬ ((𝐴𝑁) = 0 ∧ 𝐵 = 0))
33 gcdn0cl 16207 . . . . . . . . . . . . . . . . 17 ((((𝐴𝑁) ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ ¬ ((𝐴𝑁) = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) gcd 𝐵) ∈ ℕ)
3418, 20, 32, 33syl21anc 835 . . . . . . . . . . . . . . . 16 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) gcd 𝐵) ∈ ℕ)
3534nnzd 12423 . . . . . . . . . . . . . . 15 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴𝑁) gcd 𝐵) ∈ ℤ)
3635adantr 481 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴𝑁) gcd 𝐵) ∈ ℤ)
37 dvdstr 16001 . . . . . . . . . . . . . 14 ((𝑝 ∈ ℤ ∧ ((𝐴𝑁) gcd 𝐵) ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
3826, 36, 19, 37syl3anc 1370 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
3924, 38mpan2d 691 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → 𝑝 ∥ (𝐴𝑁)))
40 simpr 485 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℙ)
41 simpll1 1211 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝐴 ∈ ℤ)
4215adantr 481 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝑁 ∈ ℕ)
43 prmdvdsexp 16418 . . . . . . . . . . . . 13 ((𝑝 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (𝑝 ∥ (𝐴𝑁) ↔ 𝑝𝐴))
4440, 41, 42, 43syl3anc 1370 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴𝑁) ↔ 𝑝𝐴))
4539, 44sylibd 238 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → 𝑝𝐴))
4623simprd 496 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴𝑁) gcd 𝐵) ∥ 𝐵)
47 dvdstr 16001 . . . . . . . . . . . . 13 ((𝑝 ∈ ℤ ∧ ((𝐴𝑁) gcd 𝐵) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
4826, 36, 21, 47syl3anc 1370 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ∧ ((𝐴𝑁) gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
4946, 48mpan2d 691 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → 𝑝𝐵))
5045, 49jcad 513 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝑝𝐴𝑝𝐵)))
51 dvdsgcd 16250 . . . . . . . . . . 11 ((𝑝 ∈ ℤ ∧ 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝𝐴𝑝𝐵) → 𝑝 ∥ (𝐴 gcd 𝐵)))
5226, 41, 21, 51syl3anc 1370 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝𝐴𝑝𝐵) → 𝑝 ∥ (𝐴 gcd 𝐵)))
53 nprmdvds1 16409 . . . . . . . . . . . . 13 (𝑝 ∈ ℙ → ¬ 𝑝 ∥ 1)
54 breq2 5080 . . . . . . . . . . . . . 14 ((𝐴 gcd 𝐵) = 1 → (𝑝 ∥ (𝐴 gcd 𝐵) ↔ 𝑝 ∥ 1))
5554notbid 318 . . . . . . . . . . . . 13 ((𝐴 gcd 𝐵) = 1 → (¬ 𝑝 ∥ (𝐴 gcd 𝐵) ↔ ¬ 𝑝 ∥ 1))
5653, 55syl5ibrcom 246 . . . . . . . . . . . 12 (𝑝 ∈ ℙ → ((𝐴 gcd 𝐵) = 1 → ¬ 𝑝 ∥ (𝐴 gcd 𝐵)))
5756necon2ad 2958 . . . . . . . . . . 11 (𝑝 ∈ ℙ → (𝑝 ∥ (𝐴 gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
5857adantl 482 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
5950, 52, 583syld 60 . . . . . . . . 9 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
6059rexlimdva 3212 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝐴 gcd 𝐵) ≠ 1))
61 gcdn0cl 16207 . . . . . . . . . 10 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℕ)
62613adantl3 1167 . . . . . . . . 9 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℕ)
63 eluz2b3 12660 . . . . . . . . . 10 ((𝐴 gcd 𝐵) ∈ (ℤ‘2) ↔ ((𝐴 gcd 𝐵) ∈ ℕ ∧ (𝐴 gcd 𝐵) ≠ 1))
6463baib 536 . . . . . . . . 9 ((𝐴 gcd 𝐵) ∈ ℕ → ((𝐴 gcd 𝐵) ∈ (ℤ‘2) ↔ (𝐴 gcd 𝐵) ≠ 1))
6562, 64syl 17 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 gcd 𝐵) ∈ (ℤ‘2) ↔ (𝐴 gcd 𝐵) ≠ 1))
6660, 65sylibrd 258 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → (𝐴 gcd 𝐵) ∈ (ℤ‘2)))
6713, 66syl5 34 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) → (𝐴 gcd 𝐵) ∈ (ℤ‘2)))
68 exprmfct 16407 . . . . . . 7 ((𝐴 gcd 𝐵) ∈ (ℤ‘2) → ∃𝑝 ∈ ℙ 𝑝 ∥ (𝐴 gcd 𝐵))
6962nnzd 12423 . . . . . . . . . . . . . 14 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (𝐴 gcd 𝐵) ∈ ℤ)
7069adantr 481 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∈ ℤ)
71 gcddvds 16208 . . . . . . . . . . . . . . 15 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝐴 gcd 𝐵) ∥ 𝐴 ∧ (𝐴 gcd 𝐵) ∥ 𝐵))
7241, 21, 71syl2anc 584 . . . . . . . . . . . . . 14 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝐴 gcd 𝐵) ∥ 𝐴 ∧ (𝐴 gcd 𝐵) ∥ 𝐵))
7372simpld 495 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∥ 𝐴)
74 iddvdsexp 15987 . . . . . . . . . . . . . 14 ((𝐴 ∈ ℤ ∧ 𝑁 ∈ ℕ) → 𝐴 ∥ (𝐴𝑁))
7541, 42, 74syl2anc 584 . . . . . . . . . . . . 13 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → 𝐴 ∥ (𝐴𝑁))
7670, 41, 19, 73, 75dvdstrd 16002 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∥ (𝐴𝑁))
77 dvdstr 16001 . . . . . . . . . . . . 13 ((𝑝 ∈ ℤ ∧ (𝐴 gcd 𝐵) ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
7826, 70, 19, 77syl3anc 1370 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ (𝐴𝑁)) → 𝑝 ∥ (𝐴𝑁)))
7976, 78mpan2d 691 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → 𝑝 ∥ (𝐴𝑁)))
8072simprd 496 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝐴 gcd 𝐵) ∥ 𝐵)
81 dvdstr 16001 . . . . . . . . . . . . 13 ((𝑝 ∈ ℤ ∧ (𝐴 gcd 𝐵) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
8226, 70, 21, 81syl3anc 1370 . . . . . . . . . . . 12 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (𝐴 gcd 𝐵) ∧ (𝐴 gcd 𝐵) ∥ 𝐵) → 𝑝𝐵))
8380, 82mpan2d 691 . . . . . . . . . . 11 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → 𝑝𝐵))
8479, 83jcad 513 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → (𝑝 ∥ (𝐴𝑁) ∧ 𝑝𝐵)))
85 dvdsgcd 16250 . . . . . . . . . . 11 ((𝑝 ∈ ℤ ∧ (𝐴𝑁) ∈ ℤ ∧ 𝐵 ∈ ℤ) → ((𝑝 ∥ (𝐴𝑁) ∧ 𝑝𝐵) → 𝑝 ∥ ((𝐴𝑁) gcd 𝐵)))
8626, 19, 21, 85syl3anc 1370 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → ((𝑝 ∥ (𝐴𝑁) ∧ 𝑝𝐵) → 𝑝 ∥ ((𝐴𝑁) gcd 𝐵)))
87 breq2 5080 . . . . . . . . . . . . . 14 (((𝐴𝑁) gcd 𝐵) = 1 → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ↔ 𝑝 ∥ 1))
8887notbid 318 . . . . . . . . . . . . 13 (((𝐴𝑁) gcd 𝐵) = 1 → (¬ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵) ↔ ¬ 𝑝 ∥ 1))
8953, 88syl5ibrcom 246 . . . . . . . . . . . 12 (𝑝 ∈ ℙ → (((𝐴𝑁) gcd 𝐵) = 1 → ¬ 𝑝 ∥ ((𝐴𝑁) gcd 𝐵)))
9089necon2ad 2958 . . . . . . . . . . 11 (𝑝 ∈ ℙ → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
9190adantl 482 . . . . . . . . . 10 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ ((𝐴𝑁) gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
9284, 86, 913syld 60 . . . . . . . . 9 ((((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) ∧ 𝑝 ∈ ℙ) → (𝑝 ∥ (𝐴 gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
9392rexlimdva 3212 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ (𝐴 gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ≠ 1))
94 eluz2b3 12660 . . . . . . . . . 10 (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ (((𝐴𝑁) gcd 𝐵) ∈ ℕ ∧ ((𝐴𝑁) gcd 𝐵) ≠ 1))
9594baib 536 . . . . . . . . 9 (((𝐴𝑁) gcd 𝐵) ∈ ℕ → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ ((𝐴𝑁) gcd 𝐵) ≠ 1))
9634, 95syl 17 . . . . . . . 8 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ ((𝐴𝑁) gcd 𝐵) ≠ 1))
9793, 96sylibrd 258 . . . . . . 7 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (∃𝑝 ∈ ℙ 𝑝 ∥ (𝐴 gcd 𝐵) → ((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2)))
9868, 97syl5 34 . . . . . 6 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → ((𝐴 gcd 𝐵) ∈ (ℤ‘2) → ((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2)))
9967, 98impbid 211 . . . . 5 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ∈ (ℤ‘2) ↔ (𝐴 gcd 𝐵) ∈ (ℤ‘2)))
10099, 96, 653bitr3d 309 . . . 4 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) ≠ 1 ↔ (𝐴 gcd 𝐵) ≠ 1))
101100necon4bid 2989 . . 3 (((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) ∧ ¬ (𝐴 = 0 ∧ 𝐵 = 0)) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1))
102101ex 413 . 2 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (¬ (𝐴 = 0 ∧ 𝐵 = 0) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1)))
10312, 102pm2.61d 179 1 ((𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ∧ 𝑁 ∈ ℕ) → (((𝐴𝑁) gcd 𝐵) = 1 ↔ (𝐴 gcd 𝐵) = 1))
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 205  wa 396  w3a 1086   = wceq 1539  wcel 2106  wne 2943  wrex 3065   class class class wbr 5076  cfv 6435  (class class class)co 7277  cc 10867  0cc0 10869  1c1 10870  cn 11971  2c2 12026  0cn0 12231  cz 12317  cuz 12580  cexp 13780  cdvds 15961   gcd cgcd 16199  cprime 16374
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1798  ax-4 1812  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2709  ax-sep 5225  ax-nul 5232  ax-pow 5290  ax-pr 5354  ax-un 7588  ax-cnex 10925  ax-resscn 10926  ax-1cn 10927  ax-icn 10928  ax-addcl 10929  ax-addrcl 10930  ax-mulcl 10931  ax-mulrcl 10932  ax-mulcom 10933  ax-addass 10934  ax-mulass 10935  ax-distr 10936  ax-i2m1 10937  ax-1ne0 10938  ax-1rid 10939  ax-rnegex 10940  ax-rrecex 10941  ax-cnre 10942  ax-pre-lttri 10943  ax-pre-lttrn 10944  ax-pre-ltadd 10945  ax-pre-mulgt0 10946  ax-pre-sup 10947
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1783  df-nf 1787  df-sb 2068  df-mo 2540  df-eu 2569  df-clab 2716  df-cleq 2730  df-clel 2816  df-nfc 2889  df-ne 2944  df-nel 3050  df-ral 3069  df-rex 3070  df-rmo 3071  df-reu 3072  df-rab 3073  df-v 3433  df-sbc 3718  df-csb 3834  df-dif 3891  df-un 3893  df-in 3895  df-ss 3905  df-pss 3907  df-nul 4259  df-if 4462  df-pw 4537  df-sn 4564  df-pr 4566  df-op 4570  df-uni 4842  df-iun 4928  df-br 5077  df-opab 5139  df-mpt 5160  df-tr 5194  df-id 5491  df-eprel 5497  df-po 5505  df-so 5506  df-fr 5546  df-we 5548  df-xp 5597  df-rel 5598  df-cnv 5599  df-co 5600  df-dm 5601  df-rn 5602  df-res 5603  df-ima 5604  df-pred 6204  df-ord 6271  df-on 6272  df-lim 6273  df-suc 6274  df-iota 6393  df-fun 6437  df-fn 6438  df-f 6439  df-f1 6440  df-fo 6441  df-f1o 6442  df-fv 6443  df-riota 7234  df-ov 7280  df-oprab 7281  df-mpo 7282  df-om 7713  df-1st 7831  df-2nd 7832  df-frecs 8095  df-wrecs 8126  df-recs 8200  df-rdg 8239  df-1o 8295  df-2o 8296  df-er 8496  df-en 8732  df-dom 8733  df-sdom 8734  df-fin 8735  df-sup 9199  df-inf 9200  df-pnf 11009  df-mnf 11010  df-xr 11011  df-ltxr 11012  df-le 11013  df-sub 11205  df-neg 11206  df-div 11631  df-nn 11972  df-2 12034  df-3 12035  df-n0 12232  df-z 12318  df-uz 12581  df-rp 12729  df-fz 13238  df-fl 13510  df-mod 13588  df-seq 13720  df-exp 13781  df-cj 14808  df-re 14809  df-im 14810  df-sqrt 14944  df-abs 14945  df-dvds 15962  df-gcd 16200  df-prm 16375
This theorem is referenced by:  rpexp1i  16426  phiprmpw  16475  pockthlem  16604  logbgcd1irr  25942  aks4d1p8d3  40091  flt4lem7  40493
  Copyright terms: Public domain W3C validator