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 ( ( ( 𝐴 ∈ ℤ ∧ 𝐵 ∈ ℤ ) ∧ ( 𝐴 gcd 𝐵 ) = 1 ∧ ( 𝑁 ∈ ( ℤ≥ ‘ 2 ) ∧ 𝑁 ∥ 𝐴 ) ) → ¬ 𝑁 ∥ 𝐵 )

Proof

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