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

Theorem oddvds 18137
 Description: The only multiples of 𝐴 that are equal to the identity are the multiples of the order of 𝐴. (Contributed by Mario Carneiro, 14-Jan-2015.) (Revised by Mario Carneiro, 23-Sep-2015.)
Hypotheses
Ref Expression
odcl.1 𝑋 = (Base‘𝐺)
odcl.2 𝑂 = (od‘𝐺)
odid.3 · = (.g𝐺)
odid.4 0 = (0g𝐺)
Assertion
Ref Expression
oddvds ((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) → ((𝑂𝐴) ∥ 𝑁 ↔ (𝑁 · 𝐴) = 0 ))

Proof of Theorem oddvds
StepHypRef Expression
1 simpr 479 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (𝑂𝐴) ∈ ℕ)
2 simpl3 1208 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → 𝑁 ∈ ℤ)
3 dvdsval3 15157 . . . 4 (((𝑂𝐴) ∈ ℕ ∧ 𝑁 ∈ ℤ) → ((𝑂𝐴) ∥ 𝑁 ↔ (𝑁 mod (𝑂𝐴)) = 0))
41, 2, 3syl2anc 696 . . 3 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑂𝐴) ∥ 𝑁 ↔ (𝑁 mod (𝑂𝐴)) = 0))
5 simpl2 1206 . . . . . 6 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → 𝐴𝑋)
6 odcl.1 . . . . . . 7 𝑋 = (Base‘𝐺)
7 odid.4 . . . . . . 7 0 = (0g𝐺)
8 odid.3 . . . . . . 7 · = (.g𝐺)
96, 7, 8mulg0 17718 . . . . . 6 (𝐴𝑋 → (0 · 𝐴) = 0 )
105, 9syl 17 . . . . 5 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (0 · 𝐴) = 0 )
11 oveq1 6808 . . . . . 6 ((𝑁 mod (𝑂𝐴)) = 0 → ((𝑁 mod (𝑂𝐴)) · 𝐴) = (0 · 𝐴))
1211eqeq1d 2750 . . . . 5 ((𝑁 mod (𝑂𝐴)) = 0 → (((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ↔ (0 · 𝐴) = 0 ))
1310, 12syl5ibrcom 237 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑁 mod (𝑂𝐴)) = 0 → ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ))
142zred 11645 . . . . . . . 8 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → 𝑁 ∈ ℝ)
151nnrpd 12034 . . . . . . . 8 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (𝑂𝐴) ∈ ℝ+)
16 modlt 12844 . . . . . . . 8 ((𝑁 ∈ ℝ ∧ (𝑂𝐴) ∈ ℝ+) → (𝑁 mod (𝑂𝐴)) < (𝑂𝐴))
1714, 15, 16syl2anc 696 . . . . . . 7 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (𝑁 mod (𝑂𝐴)) < (𝑂𝐴))
182, 1zmodcld 12856 . . . . . . . . 9 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (𝑁 mod (𝑂𝐴)) ∈ ℕ0)
1918nn0red 11515 . . . . . . . 8 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (𝑁 mod (𝑂𝐴)) ∈ ℝ)
201nnred 11198 . . . . . . . 8 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (𝑂𝐴) ∈ ℝ)
2119, 20ltnled 10347 . . . . . . 7 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑁 mod (𝑂𝐴)) < (𝑂𝐴) ↔ ¬ (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴))))
2217, 21mpbid 222 . . . . . 6 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ¬ (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴)))
23 odcl.2 . . . . . . . . . . . 12 𝑂 = (od‘𝐺)
246, 23, 8, 7odlem2 18129 . . . . . . . . . . 11 ((𝐴𝑋 ∧ (𝑁 mod (𝑂𝐴)) ∈ ℕ ∧ ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ) → (𝑂𝐴) ∈ (1...(𝑁 mod (𝑂𝐴))))
25 elfzle2 12509 . . . . . . . . . . 11 ((𝑂𝐴) ∈ (1...(𝑁 mod (𝑂𝐴))) → (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴)))
2624, 25syl 17 . . . . . . . . . 10 ((𝐴𝑋 ∧ (𝑁 mod (𝑂𝐴)) ∈ ℕ ∧ ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ) → (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴)))
27263com23 1120 . . . . . . . . 9 ((𝐴𝑋 ∧ ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ∧ (𝑁 mod (𝑂𝐴)) ∈ ℕ) → (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴)))
28273expia 1114 . . . . . . . 8 ((𝐴𝑋 ∧ ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ) → ((𝑁 mod (𝑂𝐴)) ∈ ℕ → (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴))))
2928con3d 148 . . . . . . 7 ((𝐴𝑋 ∧ ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ) → (¬ (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴)) → ¬ (𝑁 mod (𝑂𝐴)) ∈ ℕ))
3029impancom 455 . . . . . 6 ((𝐴𝑋 ∧ ¬ (𝑂𝐴) ≤ (𝑁 mod (𝑂𝐴))) → (((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 → ¬ (𝑁 mod (𝑂𝐴)) ∈ ℕ))
315, 22, 30syl2anc 696 . . . . 5 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 → ¬ (𝑁 mod (𝑂𝐴)) ∈ ℕ))
32 elnn0 11457 . . . . . . 7 ((𝑁 mod (𝑂𝐴)) ∈ ℕ0 ↔ ((𝑁 mod (𝑂𝐴)) ∈ ℕ ∨ (𝑁 mod (𝑂𝐴)) = 0))
3318, 32sylib 208 . . . . . 6 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑁 mod (𝑂𝐴)) ∈ ℕ ∨ (𝑁 mod (𝑂𝐴)) = 0))
3433ord 391 . . . . 5 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (¬ (𝑁 mod (𝑂𝐴)) ∈ ℕ → (𝑁 mod (𝑂𝐴)) = 0))
3531, 34syld 47 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 → (𝑁 mod (𝑂𝐴)) = 0))
3613, 35impbid 202 . . 3 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑁 mod (𝑂𝐴)) = 0 ↔ ((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ))
376, 23, 8, 7odmod 18136 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑁 mod (𝑂𝐴)) · 𝐴) = (𝑁 · 𝐴))
3837eqeq1d 2750 . . 3 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → (((𝑁 mod (𝑂𝐴)) · 𝐴) = 0 ↔ (𝑁 · 𝐴) = 0 ))
394, 36, 383bitrd 294 . 2 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) ∈ ℕ) → ((𝑂𝐴) ∥ 𝑁 ↔ (𝑁 · 𝐴) = 0 ))
40 simpr 479 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → (𝑂𝐴) = 0)
4140breq1d 4802 . . 3 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → ((𝑂𝐴) ∥ 𝑁 ↔ 0 ∥ 𝑁))
42 simpl3 1208 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → 𝑁 ∈ ℤ)
43 0dvds 15175 . . . 4 (𝑁 ∈ ℤ → (0 ∥ 𝑁𝑁 = 0))
4442, 43syl 17 . . 3 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → (0 ∥ 𝑁𝑁 = 0))
45 simpl2 1206 . . . . . 6 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → 𝐴𝑋)
4645, 9syl 17 . . . . 5 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → (0 · 𝐴) = 0 )
47 oveq1 6808 . . . . . 6 (𝑁 = 0 → (𝑁 · 𝐴) = (0 · 𝐴))
4847eqeq1d 2750 . . . . 5 (𝑁 = 0 → ((𝑁 · 𝐴) = 0 ↔ (0 · 𝐴) = 0 ))
4946, 48syl5ibrcom 237 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → (𝑁 = 0 → (𝑁 · 𝐴) = 0 ))
506, 23, 8, 7odnncl 18135 . . . . . . . . 9 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑁 ≠ 0 ∧ (𝑁 · 𝐴) = 0 )) → (𝑂𝐴) ∈ ℕ)
5150nnne0d 11228 . . . . . . . 8 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑁 ≠ 0 ∧ (𝑁 · 𝐴) = 0 )) → (𝑂𝐴) ≠ 0)
5251expr 644 . . . . . . 7 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ 𝑁 ≠ 0) → ((𝑁 · 𝐴) = 0 → (𝑂𝐴) ≠ 0))
5352impancom 455 . . . . . 6 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑁 · 𝐴) = 0 ) → (𝑁 ≠ 0 → (𝑂𝐴) ≠ 0))
5453necon4d 2944 . . . . 5 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑁 · 𝐴) = 0 ) → ((𝑂𝐴) = 0 → 𝑁 = 0))
5554impancom 455 . . . 4 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → ((𝑁 · 𝐴) = 0𝑁 = 0))
5649, 55impbid 202 . . 3 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → (𝑁 = 0 ↔ (𝑁 · 𝐴) = 0 ))
5741, 44, 563bitrd 294 . 2 (((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) ∧ (𝑂𝐴) = 0) → ((𝑂𝐴) ∥ 𝑁 ↔ (𝑁 · 𝐴) = 0 ))
586, 23odcl 18126 . . . 4 (𝐴𝑋 → (𝑂𝐴) ∈ ℕ0)
59583ad2ant2 1126 . . 3 ((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) → (𝑂𝐴) ∈ ℕ0)
60 elnn0 11457 . . 3 ((𝑂𝐴) ∈ ℕ0 ↔ ((𝑂𝐴) ∈ ℕ ∨ (𝑂𝐴) = 0))
6159, 60sylib 208 . 2 ((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) → ((𝑂𝐴) ∈ ℕ ∨ (𝑂𝐴) = 0))
6239, 57, 61mpjaodan 862 1 ((𝐺 ∈ Grp ∧ 𝐴𝑋𝑁 ∈ ℤ) → ((𝑂𝐴) ∥ 𝑁 ↔ (𝑁 · 𝐴) = 0 ))
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   → wi 4   ↔ wb 196   ∨ wo 382   ∧ wa 383   ∧ w3a 1072   = wceq 1620   ∈ wcel 2127   ≠ wne 2920   class class class wbr 4792  ‘cfv 6037  (class class class)co 6801  ℝcr 10098  0cc0 10099  1c1 10100   < clt 10237   ≤ cle 10238  ℕcn 11183  ℕ0cn0 11455  ℤcz 11540  ℝ+crp 11996  ...cfz 12490   mod cmo 12833   ∥ cdvds 15153  Basecbs 16030  0gc0g 16273  Grpcgrp 17594  .gcmg 17712  odcod 18115 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1859  ax-4 1874  ax-5 1976  ax-6 2042  ax-7 2078  ax-8 2129  ax-9 2136  ax-10 2156  ax-11 2171  ax-12 2184  ax-13 2379  ax-ext 2728  ax-rep 4911  ax-sep 4921  ax-nul 4929  ax-pow 4980  ax-pr 5043  ax-un 7102  ax-inf2 8699  ax-cnex 10155  ax-resscn 10156  ax-1cn 10157  ax-icn 10158  ax-addcl 10159  ax-addrcl 10160  ax-mulcl 10161  ax-mulrcl 10162  ax-mulcom 10163  ax-addass 10164  ax-mulass 10165  ax-distr 10166  ax-i2m1 10167  ax-1ne0 10168  ax-1rid 10169  ax-rnegex 10170  ax-rrecex 10171  ax-cnre 10172  ax-pre-lttri 10173  ax-pre-lttrn 10174  ax-pre-ltadd 10175  ax-pre-mulgt0 10176  ax-pre-sup 10177 This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1623  df-ex 1842  df-nf 1847  df-sb 2035  df-eu 2599  df-mo 2600  df-clab 2735  df-cleq 2741  df-clel 2744  df-nfc 2879  df-ne 2921  df-nel 3024  df-ral 3043  df-rex 3044  df-reu 3045  df-rmo 3046  df-rab 3047  df-v 3330  df-sbc 3565  df-csb 3663  df-dif 3706  df-un 3708  df-in 3710  df-ss 3717  df-pss 3719  df-nul 4047  df-if 4219  df-pw 4292  df-sn 4310  df-pr 4312  df-tp 4314  df-op 4316  df-uni 4577  df-iun 4662  df-br 4793  df-opab 4853  df-mpt 4870  df-tr 4893  df-id 5162  df-eprel 5167  df-po 5175  df-so 5176  df-fr 5213  df-we 5215  df-xp 5260  df-rel 5261  df-cnv 5262  df-co 5263  df-dm 5264  df-rn 5265  df-res 5266  df-ima 5267  df-pred 5829  df-ord 5875  df-on 5876  df-lim 5877  df-suc 5878  df-iota 6000  df-fun 6039  df-fn 6040  df-f 6041  df-f1 6042  df-fo 6043  df-f1o 6044  df-fv 6045  df-riota 6762  df-ov 6804  df-oprab 6805  df-mpt2 6806  df-om 7219  df-1st 7321  df-2nd 7322  df-wrecs 7564  df-recs 7625  df-rdg 7663  df-er 7899  df-en 8110  df-dom 8111  df-sdom 8112  df-sup 8501  df-inf 8502  df-pnf 10239  df-mnf 10240  df-xr 10241  df-ltxr 10242  df-le 10243  df-sub 10431  df-neg 10432  df-div 10848  df-nn 11184  df-2 11242  df-3 11243  df-n0 11456  df-z 11541  df-uz 11851  df-rp 11997  df-fz 12491  df-fl 12758  df-mod 12834  df-seq 12967  df-exp 13026  df-cj 14009  df-re 14010  df-im 14011  df-sqrt 14145  df-abs 14146  df-dvds 15154  df-0g 16275  df-mgm 17414  df-sgrp 17456  df-mnd 17467  df-grp 17597  df-minusg 17598  df-sbg 17599  df-mulg 17713  df-od 18119 This theorem is referenced by:  oddvdsi  18138  odcong  18139  odeq  18140  odmulgid  18142  odbezout  18146  gexdvds2  18171  gexod  18172  gexcl3  18173  odadd1  18422  odadd2  18423  oddvdssubg  18429  pgpfac1lem3a  18646  chrdvds  20049  dchrfi  25150  dchrabs  25155  dchrptlem2  25160  idomodle  38245
 Copyright terms: Public domain W3C validator