Metamath Proof Explorer


Theorem divcoprmndiv

Description: An integer greater than 1 dividing an integer does not divide an integer which is coprime to the first integer. (Contributed by AV, 3-Nov-2026)

Ref Expression
Assertion divcoprmndiv ⊢ A ∈ ℤ ∧ B ∈ ℤ ∧ A gcd B = 1 ∧ N ∈ ℤ ≥ 2 ∧ N ∥ A → ¬ N ∥ B

Proof

Step Hyp Ref Expression
1 eluzelz ⊢ N ∈ ℤ ≥ 2 → N ∈ ℤ
2 1 adantr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A → N ∈ ℤ
3 2 anim1i ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ → N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ
4 3anass ⊢ N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ ↔ N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ
5 3 4 sylibr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ → N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ
6 5 adantr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B → N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ
7 6 adantr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ
8 ax-1ne0 ⊢ 1 ≠ 0
9 8 neii ⊢ ¬ 1 = 0
10 eqeq1 ⊢ A gcd B = 1 → A gcd B = 0 ↔ 1 = 0
11 9 10 mtbiri ⊢ A gcd B = 1 → ¬ A gcd B = 0
12 11 adantl ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → ¬ A gcd B = 0
13 gcdeq0 ⊢ A ∈ ℤ ∧ B ∈ ℤ → A gcd B = 0 ↔ A = 0 ∧ B = 0
14 13 notbid ⊢ A ∈ ℤ ∧ B ∈ ℤ → ¬ A gcd B = 0 ↔ ¬ A = 0 ∧ B = 0
15 14 ad3antlr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → ¬ A gcd B = 0 ↔ ¬ A = 0 ∧ B = 0
16 12 15 mpbid ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → ¬ A = 0 ∧ B = 0
17 simplr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ → N ∥ A
18 17 anim1i ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B → N ∥ A ∧ N ∥ B
19 18 adantr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → N ∥ A ∧ N ∥ B
20 dvdslegcd ⊢ N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ ¬ A = 0 ∧ B = 0 → N ∥ A ∧ N ∥ B → N ≤ A gcd B
21 20 imp ⊢ N ∈ ℤ ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ ¬ A = 0 ∧ B = 0 ∧ N ∥ A ∧ N ∥ B → N ≤ A gcd B
22 7 16 19 21 syl21anc ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → N ≤ A gcd B
23 breq2 ⊢ A gcd B = 1 → N ≤ A gcd B ↔ N ≤ 1
24 23 adantl ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → N ≤ A gcd B ↔ N ≤ 1
25 eluz2 ⊢ N ∈ ℤ ≥ 2 ↔ 2 ∈ ℤ ∧ N ∈ ℤ ∧ 2 ≤ N
26 1zzd ⊢ N ∈ ℤ → 1 ∈ ℤ
27 id ⊢ N ∈ ℤ → N ∈ ℤ
28 26 27 zltp1led ⊢ N ∈ ℤ → 1 < N ↔ 1 + 1 ≤ N
29 1p1e2 ⊢ 1 + 1 = 2
30 29 a1i ⊢ N ∈ ℤ → 1 + 1 = 2
31 30 breq1d ⊢ N ∈ ℤ → 1 + 1 ≤ N ↔ 2 ≤ N
32 28 31 bitrd ⊢ N ∈ ℤ → 1 < N ↔ 2 ≤ N
33 1red ⊢ N ∈ ℤ → 1 ∈ ℝ
34 zre ⊢ N ∈ ℤ → N ∈ ℝ
35 33 34 ltnled ⊢ N ∈ ℤ → 1 < N ↔ ¬ N ≤ 1
36 pm2.21 ⊢ ¬ N ≤ 1 → N ≤ 1 → ¬ N ∥ B
37 35 36 biimtrdi ⊢ N ∈ ℤ → 1 < N → N ≤ 1 → ¬ N ∥ B
38 32 37 sylbird ⊢ N ∈ ℤ → 2 ≤ N → N ≤ 1 → ¬ N ∥ B
39 38 imp ⊢ N ∈ ℤ ∧ 2 ≤ N → N ≤ 1 → ¬ N ∥ B
40 39 3adant1 ⊢ 2 ∈ ℤ ∧ N ∈ ℤ ∧ 2 ≤ N → N ≤ 1 → ¬ N ∥ B
41 25 40 sylbi ⊢ N ∈ ℤ ≥ 2 → N ≤ 1 → ¬ N ∥ B
42 41 ad4antr ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → N ≤ 1 → ¬ N ∥ B
43 24 42 sylbid ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → N ≤ A gcd B → ¬ N ∥ B
44 22 43 mpd ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ ∧ N ∥ B ∧ A gcd B = 1 → ¬ N ∥ B
45 44 exp31 ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ → N ∥ B → A gcd B = 1 → ¬ N ∥ B
46 45 com23 ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A ∧ A ∈ ℤ ∧ B ∈ ℤ → A gcd B = 1 → N ∥ B → ¬ N ∥ B
47 46 ex ⊢ N ∈ ℤ ≥ 2 ∧ N ∥ A → A ∈ ℤ ∧ B ∈ ℤ → A gcd B = 1 → N ∥ B → ¬ N ∥ B
48 47 com14 ⊢ N ∥ B → A ∈ ℤ ∧ B ∈ ℤ → A gcd B = 1 → N ∈ ℤ ≥ 2 ∧ N ∥ A → ¬ N ∥ B
49 48 3impd ⊢ N ∥ B → A ∈ ℤ ∧ B ∈ ℤ ∧ A gcd B = 1 ∧ N ∈ ℤ ≥ 2 ∧ N ∥ A → ¬ N ∥ B
50 ax-1 ⊢ ¬ N ∥ B → A ∈ ℤ ∧ B ∈ ℤ ∧ A gcd B = 1 ∧ N ∈ ℤ ≥ 2 ∧ N ∥ A → ¬ N ∥ B
51 49 50 pm2.61i ⊢ A ∈ ℤ ∧ B ∈ ℤ ∧ A gcd B = 1 ∧ N ∈ ℤ ≥ 2 ∧ N ∥ A → ¬ N ∥ B