![]() |
Metamath Proof Explorer |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > cncongrprm | Structured version Visualization version GIF version |
Description: Corollary 2 of Cancellability of Congruences: Two products with a common factor are congruent modulo a prime number not dividing the common factor iff the other factors are congruent modulo the prime number. (Contributed by AV, 13-Jul-2021.) |
Ref | Expression |
---|---|
cncongrprm | โข (((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โง (๐ โ โ โง ยฌ ๐ โฅ ๐ถ)) โ (((๐ด ยท ๐ถ) mod ๐) = ((๐ต ยท ๐ถ) mod ๐) โ (๐ด mod ๐) = (๐ต mod ๐))) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | prmnn 16642 | . . . 4 โข (๐ โ โ โ ๐ โ โ) | |
2 | 1 | ad2antrl 726 | . . 3 โข (((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โง (๐ โ โ โง ยฌ ๐ โฅ ๐ถ)) โ ๐ โ โ) |
3 | coprm 16679 | . . . . . . . . 9 โข ((๐ โ โ โง ๐ถ โ โค) โ (ยฌ ๐ โฅ ๐ถ โ (๐ gcd ๐ถ) = 1)) | |
4 | prmz 16643 | . . . . . . . . . . 11 โข (๐ โ โ โ ๐ โ โค) | |
5 | gcdcom 16485 | . . . . . . . . . . 11 โข ((๐ โ โค โง ๐ถ โ โค) โ (๐ gcd ๐ถ) = (๐ถ gcd ๐)) | |
6 | 4, 5 | sylan 578 | . . . . . . . . . 10 โข ((๐ โ โ โง ๐ถ โ โค) โ (๐ gcd ๐ถ) = (๐ถ gcd ๐)) |
7 | 6 | eqeq1d 2727 | . . . . . . . . 9 โข ((๐ โ โ โง ๐ถ โ โค) โ ((๐ gcd ๐ถ) = 1 โ (๐ถ gcd ๐) = 1)) |
8 | 3, 7 | bitrd 278 | . . . . . . . 8 โข ((๐ โ โ โง ๐ถ โ โค) โ (ยฌ ๐ โฅ ๐ถ โ (๐ถ gcd ๐) = 1)) |
9 | 8 | ancoms 457 | . . . . . . 7 โข ((๐ถ โ โค โง ๐ โ โ) โ (ยฌ ๐ โฅ ๐ถ โ (๐ถ gcd ๐) = 1)) |
10 | 9 | biimpd 228 | . . . . . 6 โข ((๐ถ โ โค โง ๐ โ โ) โ (ยฌ ๐ โฅ ๐ถ โ (๐ถ gcd ๐) = 1)) |
11 | 10 | expimpd 452 | . . . . 5 โข (๐ถ โ โค โ ((๐ โ โ โง ยฌ ๐ โฅ ๐ถ) โ (๐ถ gcd ๐) = 1)) |
12 | 11 | 3ad2ant3 1132 | . . . 4 โข ((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โ ((๐ โ โ โง ยฌ ๐ โฅ ๐ถ) โ (๐ถ gcd ๐) = 1)) |
13 | 12 | imp 405 | . . 3 โข (((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โง (๐ โ โ โง ยฌ ๐ โฅ ๐ถ)) โ (๐ถ gcd ๐) = 1) |
14 | 2, 13 | jca 510 | . 2 โข (((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โง (๐ โ โ โง ยฌ ๐ โฅ ๐ถ)) โ (๐ โ โ โง (๐ถ gcd ๐) = 1)) |
15 | cncongrcoprm 16638 | . 2 โข (((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โง (๐ โ โ โง (๐ถ gcd ๐) = 1)) โ (((๐ด ยท ๐ถ) mod ๐) = ((๐ต ยท ๐ถ) mod ๐) โ (๐ด mod ๐) = (๐ต mod ๐))) | |
16 | 14, 15 | syldan 589 | 1 โข (((๐ด โ โค โง ๐ต โ โค โง ๐ถ โ โค) โง (๐ โ โ โง ยฌ ๐ โฅ ๐ถ)) โ (((๐ด ยท ๐ถ) mod ๐) = ((๐ต ยท ๐ถ) mod ๐) โ (๐ด mod ๐) = (๐ต mod ๐))) |
Colors of variables: wff setvar class |
Syntax hints: ยฌ wn 3 โ wi 4 โ wb 205 โง wa 394 โง w3a 1084 = wceq 1533 โ wcel 2098 class class class wbr 5143 (class class class)co 7415 1c1 11137 ยท cmul 11141 โcn 12240 โคcz 12586 mod cmo 13864 โฅ cdvds 16228 gcd cgcd 16466 โcprime 16639 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1789 ax-4 1803 ax-5 1905 ax-6 1963 ax-7 2003 ax-8 2100 ax-9 2108 ax-10 2129 ax-11 2146 ax-12 2166 ax-ext 2696 ax-sep 5294 ax-nul 5301 ax-pow 5359 ax-pr 5423 ax-un 7737 ax-cnex 11192 ax-resscn 11193 ax-1cn 11194 ax-icn 11195 ax-addcl 11196 ax-addrcl 11197 ax-mulcl 11198 ax-mulrcl 11199 ax-mulcom 11200 ax-addass 11201 ax-mulass 11202 ax-distr 11203 ax-i2m1 11204 ax-1ne0 11205 ax-1rid 11206 ax-rnegex 11207 ax-rrecex 11208 ax-cnre 11209 ax-pre-lttri 11210 ax-pre-lttrn 11211 ax-pre-ltadd 11212 ax-pre-mulgt0 11213 ax-pre-sup 11214 |
This theorem depends on definitions: df-bi 206 df-an 395 df-or 846 df-3or 1085 df-3an 1086 df-tru 1536 df-fal 1546 df-ex 1774 df-nf 1778 df-sb 2060 df-mo 2528 df-eu 2557 df-clab 2703 df-cleq 2717 df-clel 2802 df-nfc 2877 df-ne 2931 df-nel 3037 df-ral 3052 df-rex 3061 df-rmo 3364 df-reu 3365 df-rab 3420 df-v 3465 df-sbc 3770 df-csb 3886 df-dif 3943 df-un 3945 df-in 3947 df-ss 3957 df-pss 3960 df-nul 4319 df-if 4525 df-pw 4600 df-sn 4625 df-pr 4627 df-op 4631 df-uni 4904 df-iun 4993 df-br 5144 df-opab 5206 df-mpt 5227 df-tr 5261 df-id 5570 df-eprel 5576 df-po 5584 df-so 5585 df-fr 5627 df-we 5629 df-xp 5678 df-rel 5679 df-cnv 5680 df-co 5681 df-dm 5682 df-rn 5683 df-res 5684 df-ima 5685 df-pred 6300 df-ord 6367 df-on 6368 df-lim 6369 df-suc 6370 df-iota 6494 df-fun 6544 df-fn 6545 df-f 6546 df-f1 6547 df-fo 6548 df-f1o 6549 df-fv 6550 df-riota 7371 df-ov 7418 df-oprab 7419 df-mpo 7420 df-om 7868 df-2nd 7990 df-frecs 8283 df-wrecs 8314 df-recs 8388 df-rdg 8427 df-1o 8483 df-2o 8484 df-er 8721 df-en 8961 df-dom 8962 df-sdom 8963 df-fin 8964 df-sup 9463 df-inf 9464 df-pnf 11278 df-mnf 11279 df-xr 11280 df-ltxr 11281 df-le 11282 df-sub 11474 df-neg 11475 df-div 11900 df-nn 12241 df-2 12303 df-3 12304 df-n0 12501 df-z 12587 df-uz 12851 df-rp 13005 df-fl 13787 df-mod 13865 df-seq 13997 df-exp 14057 df-cj 15076 df-re 15077 df-im 15078 df-sqrt 15212 df-abs 15213 df-dvds 16229 df-gcd 16467 df-prm 16640 |
This theorem is referenced by: (None) |
Copyright terms: Public domain | W3C validator |