Theorem gcdcom 15235

Description: The gcd operator is commutative. Theorem 1.4(a) in [ApostolNT] p. 16. (Contributed by Paul Chapman, 21-Mar-2011.)

Assertion

Ref	Expression
gcdcom	|- ( ( M e. ZZ /\ N e. ZZ ) -> ( M gcd N ) = ( N gcd M ) )

Proof of Theorem gcdcom

Dummy variable n is distinct from all other variables.

Step	Hyp	Ref	Expression
1		ancom 466	. . 3 |- ( ( M = 0 /\ N = 0 ) <-> ( N = 0 /\ M = 0 ) )
2		ancom 466	. . . . . 6 |- ( ( n || M /\ n || N ) <-> ( n || N /\ n || M ) )
3	2	a1i 11	. . . . 5 |- ( n e. ZZ -> ( ( n || M /\ n || N ) <-> ( n || N /\ n || M ) ) )
4	3	rabbiia 3185	. . . 4 |- { n e. ZZ | ( n || M /\ n || N ) } = { n e. ZZ | ( n || N /\ n || M ) }
5	4	supeq1i 8353	. . 3 |- sup ( { n e. ZZ | ( n || M /\ n || N ) } , RR , < ) = sup ( { n e. ZZ | ( n || N /\ n || M ) } , RR , < )
6	1, 5	ifbieq2i 4110	. 2 |- if ( ( M = 0 /\ N = 0 ) , 0 , sup ( { n e. ZZ | ( n || M /\ n || N ) } , RR , < ) ) = if ( ( N = 0 /\ M = 0 ) , 0 , sup ( { n e. ZZ | ( n || N /\ n || M ) } , RR , < ) )
7		gcdval 15218	. 2 |- ( ( M e. ZZ /\ N e. ZZ ) -> ( M gcd N ) = if ( ( M = 0 /\ N = 0 ) , 0 , sup ( { n e. ZZ | ( n || M /\ n || N ) } , RR , < ) ) )
8		gcdval 15218	. . 3 |- ( ( N e. ZZ /\ M e. ZZ ) -> ( N gcd M ) = if ( ( N = 0 /\ M = 0 ) , 0 , sup ( { n e. ZZ | ( n || N /\ n || M ) } , RR , < ) ) )
9	8	ancoms 469	. 2 |- ( ( M e. ZZ /\ N e. ZZ ) -> ( N gcd M ) = if ( ( N = 0 /\ M = 0 ) , 0 , sup ( { n e. ZZ | ( n || N /\ n || M ) } , RR , < ) ) )
10	6, 7, 9	3eqtr4a 2682	1 |- ( ( M e. ZZ /\ N e. ZZ ) -> ( M gcd N ) = ( N gcd M ) )

Syntax hints:   -> wi 4   <-> wb 196   /\ wa 384   = wceq 1483   e. wcel 1990   {crab 2916   ifcif 4086   class class class wbr 4653  (class class class)co 6650   supcsup 8346   RRcr 9935   0cc0 9936   < clt 10074   ZZcz 11377   || cdvds 14983   gcd cgcd 15216

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1722  ax-4 1737  ax-5 1839  ax-6 1888  ax-7 1935  ax-8 1992  ax-9 1999  ax-10 2019  ax-11 2034  ax-12 2047  ax-13 2246  ax-ext 2602  ax-sep 4781  ax-nul 4789  ax-pow 4843  ax-pr 4906  ax-un 6949  ax-resscn 9993  ax-1cn 9994  ax-icn 9995  ax-addcl 9996  ax-mulcl 9998  ax-i2m1 10004  ax-pre-lttri 10010  ax-pre-lttrn 10011

This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1038  df-3an 1039  df-tru 1486  df-ex 1705  df-nf 1710  df-sb 1881  df-eu 2474  df-mo 2475  df-clab 2609  df-cleq 2615  df-clel 2618  df-nfc 2753  df-ne 2795  df-nel 2898  df-ral 2917  df-rex 2918  df-rmo 2920  df-rab 2921  df-v 3202  df-sbc 3436  df-csb 3534  df-dif 3577  df-un 3579  df-in 3581  df-ss 3588  df-nul 3916  df-if 4087  df-pw 4160  df-sn 4178  df-pr 4180  df-op 4184  df-uni 4437  df-br 4654  df-opab 4713  df-mpt 4730  df-id 5024  df-po 5035  df-so 5036  df-xp 5120  df-rel 5121  df-cnv 5122  df-co 5123  df-dm 5124  df-rn 5125  df-res 5126  df-ima 5127  df-iota 5851  df-fun 5890  df-fn 5891  df-f 5892  df-f1 5893  df-fo 5894  df-f1o 5895  df-fv 5896  df-ov 6653  df-oprab 6654  df-mpt2 6655  df-er 7742  df-en 7956  df-dom 7957  df-sdom 7958  df-sup 8348  df-pnf 10076  df-mnf 10077  df-ltxr 10079  df-gcd 15217

This theorem is referenced by:  divgcdnnr  15237  gcdid0  15241  neggcd  15244  gcdabs2  15252  modgcd  15253  1gcd  15254  6gcd4e2  15255  rplpwr  15276  rppwr  15277  eucalginv  15297  3lcm2e6woprm  15328  coprmdvds  15366  qredeq  15371  coprmprod  15375  divgcdcoprmex  15380  cncongr1  15381  rpexp12i  15434  cncongrprm  15437  phiprmpw  15481  eulerthlem1  15486  eulerthlem2  15487  fermltl  15489  prmdiv  15490  vfermltl  15506  coprimeprodsq  15513  coprimeprodsq2  15514  pythagtriplem3  15523  pythagtrip  15539  pcgcd  15582  prmpwdvds  15608  pockthlem  15609  prmgaplem7  15761  gcdi  15777  gcdmodi  15778  1259lem5  15842  2503lem3  15846  4001lem4  15851  odinv  17978  gexexlem  18255  ablfacrp2  18466  pgpfac1lem2  18474  dvdsmulf1o  24920  perfect1  24953  perfectlem1  24954  lgslem1  25022  lgsprme0  25064  lgsdirnn0  25069  lgsqrlem2  25072  lgsqr  25076  gausslemma2dlem0c  25083  lgsquad2lem2  25110  lgsquad2  25111  lgsquad3  25112  2sqlem8  25151  ex-gcd  27314  2sqmod  29648  gcd32  31637  nn0prpwlem  32317  jm2.19lem2  37557  jm2.20nn  37564  goldbachthlem2  41458  goldbachth  41459  perfectALTVlem1  41630