Nearby theorems
|
|
Intuitionistic Logic Explorer |
< Previous
Next >
Nearby theorems |
|
| Mirrors > Home > ILE Home > Th. List > modprm0 | Unicode version | ||
| Description: For two positive integers less than a given prime number there is always a nonnegative integer (less than the given prime number) so that the sum of one of the two positive integers and the other of the positive integers multiplied by the nonnegative integer is 0 ( modulo the given prime number). (Contributed by Alexander van der Vekens, 17-May-2018.) |
| Ref | Expression |
|---|---|
| modprm0 |
     ![/\](wedge.gif "/\"){kind=small}   ..^  ..^     ..^     |
, , ,
is distinct from all other
variables.| Step | Hyp | Ref | Expression |
|---|---|---|---|
| 1 | reumodprminv 12181 |
. . . 4
..^
  
| |
| 2 | reurex 2678 |
. . . 4
| |
| 3 | prmz 12039 |
. . . . . . . . . . 11
 | |
| 4 | 3 | 3ad2ant1 1008 |
. . . . . . . . . 10
..^ ..^ |
| 5 | 4 | adantl 275 |
. . . . . . . . 9
..^ ..^
|
| 6 | elfzelz 9956 |
. . . . . . . . . . 11
| |
| 7 | 6 | adantr 274 |
. . . . . . . . . 10
|
| 8 | elfzoelz 10078 |
. . . . . . . . . . 11
..^
| |
| 9 | 8 | 3ad2ant3 1010 |
. . . . . . . . . 10
..^ ..^ |
| 10 | zmulcl 9240 |
. . . . . . . . . 10
| |
| 11 | 7, 9, 10 | syl2an 287 |
. . . . . . . . 9
..^ ..^
|
| 12 | 5, 11 | zsubcld 9314 |
. . . . . . . 8
..^ ..^
|
| 13 | prmnn 12038 |
. . . . . . . . . 10
 | |
| 14 | 13 | 3ad2ant1 1008 |
. . . . . . . . 9
..^ ..^ |
| 15 | 14 | adantl 275 |
. . . . . . . 8
..^ ..^
|
| 16 | zmodfzo 10278 |
. . . . . . . 8
..^ | |
| 17 | 12, 15, 16 | syl2anc 409 |
. . . . . . 7
..^ ..^
..^ |
| 18 | 9 | adantl 275 |
. . . . . . . . . 10
..^ ..^
|
| 19 | zq 9560 |
. . . . . . . . . 10
 | |
| 20 | 18, 19 | syl 14 |
. . . . . . . . 9
..^ ..^
|
| 21 | zq 9560 |
. . . . . . . . . 10
| |
| 22 | 12, 21 | syl 14 |
. . . . . . . . 9
..^ ..^
|
| 23 | elfzoelz 10078 |
. . . . . . . . . . 11
..^
| |
| 24 | 23 | 3ad2ant2 1009 |
. . . . . . . . . 10
..^ ..^ |
| 25 | 24 | adantl 275 |
. . . . . . . . 9
..^ ..^
|
| 26 | zq 9560 |
. . . . . . . . . 10
| |
| 27 | 5, 26 | syl 14 |
. . . . . . . . 9
..^ ..^
|
| 28 | 15 | nngt0d 8897 |
. . . . . . . . 9
..^ ..^
 |
| 29 | modqaddmulmod 10322 |
. . . . . . . . 9
| |
| 30 | 20, 22, 25, 27, 28, 29 | syl32anc 1236 |
. . . . . . . 8
..^ ..^
|
| 31 | 13 | nncnd 8867 |
. . . . . . . . . . . . 13
 |
| 32 | 31 | 3ad2ant1 1008 |
. . . . . . . . . . . 12
..^ ..^ |
| 33 | 32 | adantl 275 |
. . . . . . . . . . 11
..^ ..^
|
| 34 | 6 | zcnd 9310 |
. . . . . . . . . . . . 13
|
| 35 | 34 | adantr 274 |
. . . . . . . . . . . 12
|
| 36 | 8 | zcnd 9310 |
. . . . . . . . . . . . 13
..^
|
| 37 | 36 | 3ad2ant3 1010 |
. . . . . . . . . . . 12
..^ ..^ |
| 38 | mulcl 7876 |
. . . . . . . . . . . 12
| |
| 39 | 35, 37, 38 | syl2an 287 |
. . . . . . . . . . 11
..^ ..^
|
| 40 | 23 | zcnd 9310 |
. . . . . . . . . . . . 13
..^
|
| 41 | 40 | 3ad2ant2 1009 |
. . . . . . . . . . . 12
..^ ..^ |
| 42 | 41 | adantl 275 |
. . . . . . . . . . 11
..^ ..^
|
| 43 | 33, 39, 42 | subdird 8309 |
. . . . . . . . . 10
..^ ..^
|
| 44 | 43 | oveq2d 5857 |
. . . . . . . . 9
..^ ..^
|
| 45 | 44 | oveq1d 5856 |
. . . . . . . 8
..^ ..^
|
| 46 | mulcom 7878 |
. . . . . . . . . . . . . . . . . . 19
| |
| 47 | 31, 40, 46 | syl2an 287 |
. . . . . . . . . . . . . . . . . 18
..^
|
| 48 | 47 | oveq1d 5856 |
. . . . . . . . . . . . . . . . 17
..^
|
| 49 | 23 | adantl 275 |
. . . . . . . . . . . . . . . . . 18
..^
|
| 50 | 3 | adantr 274 |
. . . . . . . . . . . . . . . . . . 19
..^
|
| 51 | 50, 26 | syl 14 |
. . . . . . . . . . . . . . . . . 18
..^
|
| 52 | 13 | nngt0d 8897 |
. . . . . . . . . . . . . . . . . . 19
|
| 53 | 52 | adantr 274 |
. . . . . . . . . . . . . . . . . 18
..^
|
| 54 | mulqmod0 10261 |
. . . . . . . . . . . . . . . . . 18
| |
| 55 | 49, 51, 53, 54 | syl3anc 1228 |
. . . . . . . . . . . . . . . . 17
..^
|
| 56 | 48, 55 | eqtrd 2198 |
. . . . . . . . . . . . . . . 16
..^
|
| 57 | 56 | 3adant3 1007 |
. . . . . . . . . . . . . . 15
..^ ..^ |
| 58 | 57 | adantl 275 |
. . . . . . . . . . . . . 14
..^ ..^
|
| 59 | 35 | adantr 274 |
. . . . . . . . . . . . . . . . 17
..^ ..^
|
| 60 | 37 | adantl 275 |
. . . . . . . . . . . . . . . . 17
..^ ..^
|
| 61 | 59, 60, 42 | mul32d 8047 |
. . . . . . . . . . . . . . . 16
..^ ..^
|
| 62 | 61 | oveq1d 5856 |
. . . . . . . . . . . . . . 15
..^ ..^
|
| 63 | elfznn 9985 |
. . . . . . . . . . . . . . . . . . . 20
| |
| 64 | 63 | adantr 274 |
. . . . . . . . . . . . . . . . . . 19
|
| 65 | 64 | adantr 274 |
. . . . . . . . . . . . . . . . . 18
..^ ..^
|
| 66 | elfzo1 10121 |
. . . . . . . . . . . . . . . . . . . . 21
..^  | |
| 67 | 66 | simp1bi 1002 |
. . . . . . . . . . . . . . . . . . . 20
..^
|
| 68 | 67 | 3ad2ant2 1009 |
. . . . . . . . . . . . . . . . . . 19
..^ ..^ |
| 69 | 68 | adantl 275 |
. . . . . . . . . . . . . . . . . 18
..^ ..^
|
| 70 | 65, 69 | nnmulcld 8902 |
. . . . . . . . . . . . . . . . 17
..^ ..^
|
| 71 | nnq 9567 |
. . . . . . . . . . . . . . . . 17
| |
| 72 | 70, 71 | syl 14 |
. . . . . . . . . . . . . . . 16
..^ ..^
|
| 73 | modqmulmod 10320 |
. . . . . . . . . . . . . . . 16
| |
| 74 | 72, 18, 27, 28, 73 | syl22anc 1229 |
. . . . . . . . . . . . . . 15
..^ ..^
|
| 75 | 62, 74 | eqtr4d 2201 |
. . . . . . . . . . . . . 14
..^ ..^
|
| 76 | 58, 75 | oveq12d 5859 |
. . . . . . . . . . . . 13
..^ ..^
|
| 77 | 76 | oveq1d 5856 |
. . . . . . . . . . . 12
..^ ..^
|
| 78 | 15, 69 | nnmulcld 8902 |
. . . . . . . . . . . . . 14
..^ ..^
|
| 79 | nnq 9567 |
. . . . . . . . . . . . . 14
| |
| 80 | 78, 79 | syl 14 |
. . . . . . . . . . . . 13
..^ ..^
|
| 81 | elfzo1 10121 |
. . . . . . . . . . . . . . . . . . 19
..^ | |
| 82 | 81 | simp1bi 1002 |
. . . . . . . . . . . . . . . . . 18
..^
|
| 83 | 82 | 3ad2ant3 1010 |
. . . . . . . . . . . . . . . . 17
..^ ..^ |
| 84 | 83 | adantl 275 |
. . . . . . . . . . . . . . . 16
..^ ..^
|
| 85 | 65, 84 | nnmulcld 8902 |
. . . . . . . . . . . . . . 15
..^ ..^
|
| 86 | 85, 69 | nnmulcld 8902 |
. . . . . . . . . . . . . 14
..^ ..^
|
| 87 | nnq 9567 |
. . . . . . . . . . . . . 14
| |
| 88 | 86, 87 | syl 14 |
. . . . . . . . . . . . 13
..^ ..^
|
| 89 | modqsubmodmod 10314 |
. . . . . . . . . . . . 13
| |
| 90 | 80, 88, 27, 28, 89 | syl22anc 1229 |
. . . . . . . . . . . 12
..^ ..^
|
| 91 | mulcom 7878 |
. . . . . . . . . . . . . . . . . . . . . . 23
| |
| 92 | 41, 34, 91 | syl2anr 288 |
. . . . . . . . . . . . . . . . . . . . . 22
..^ ..^
|
| 93 | 92 | oveq1d 5856 |
. . . . . . . . . . . . . . . . . . . . 21
..^ ..^
|
| 94 | 93 | eqeq1d 2174 |
. . . . . . . . . . . . . . . . . . . 20
..^ ..^
|
| 95 | 94 | biimpd 143 |
. . . . . . . . . . . . . . . . . . 19
..^ ..^ |
| 96 | 95 | impancom 258 |
. . . . . . . . . . . . . . . . . 18
..^ ..^ |
| 97 | 96 | imp 123 |
. . . . . . . . . . . . . . . . 17
..^ ..^
|
| 98 | 97 | oveq1d 5856 |
. . . . . . . . . . . . . . . 16
..^ ..^
|
| 99 | 98 | oveq1d 5856 |
. . . . . . . . . . . . . . 15
..^ ..^
|
| 100 | 99 | oveq2d 5857 |
. . . . . . . . . . . . . 14
..^ ..^
|
| 101 | 100 | oveq1d 5856 |
. . . . . . . . . . . . 13
..^ ..^
|
| 102 | 60 | mulid2d 7913 |
. . . . . . . . . . . . . . . . 17
..^ ..^
|
| 103 | 102 | oveq1d 5856 |
. . . . . . . . . . . . . . . 16
..^ ..^
|
| 104 | 84 | nnnn0d 9163 |
. . . . . . . . . . . . . . . . . 18
..^ ..^
 |
| 105 | 104 | nn0ge0d 9166 |
. . . . . . . . . . . . . . . . 17
..^ ..^
 |
| 106 | elfzolt2 10087 |
. . . . . . . . . . . . . . . . . . 19
..^
| |
| 107 | 106 | 3ad2ant3 1010 |
. . . . . . . . . . . . . . . . . 18
..^ ..^ |
| 108 | 107 | adantl 275 |
. . . . . . . . . . . . . . . . 17
..^ ..^
|
| 109 | modqid 10280 |
. . . . . . . . . . . . . . . . 17
| |
| 110 | 20, 27, 105, 108, 109 | syl22anc 1229 |
. . . . . . . . . . . . . . . 16
..^ ..^
|
| 111 | 103, 110 | eqtrd 2198 |
. . . . . . . . . . . . . . 15
..^ ..^
|
| 112 | 111 | oveq2d 5857 |
. . . . . . . . . . . . . 14
..^ ..^
|
| 113 | 112 | oveq1d 5856 |
. . . . . . . . . . . . 13
..^ ..^
|
| 114 | 101, 113 | eqtrd 2198 |
. . . . . . . . . . . 12
..^ ..^
|
| 115 | 77, 90, 114 | 3eqtr3d 2206 |
. . . . . . . . . . 11
..^ ..^
|
| 116 | 115 | oveq2d 5857 |
. . . . . . . . . 10
..^ ..^
|
| 117 | 116 | oveq1d 5856 |
. . . . . . . . 9
..^ ..^
|
| 118 | qsubcl 9572 |
. . . . . . . . . . 11
| |
| 119 | 80, 88, 118 | syl2anc 409 |
. . . . . . . . . 10
..^ ..^
|
| 120 | modqadd2mod 10305 |
. . . . . . . . . 10
| |
| 121 | 119, 20, 27, 28, 120 | syl22anc 1229 |
. . . . . . . . 9
..^ ..^
|
| 122 | 0zd 9199 |
. . . . . . . . . . . . 13
..^ ..^
| |
| 123 | 122, 18 | zsubcld 9314 |
. . . . . . . . . . . 12
..^ ..^
|
| 124 | zq 9560 |
. . . . . . . . . . . 12
| |
| 125 | 123, 124 | syl 14 |
. . . . . . . . . . 11
..^ ..^
|
| 126 | modqadd2mod 10305 |
. . . . . . . . . . 11
| |
| 127 | 125, 20, 27, 28, 126 | syl22anc 1229 |
. . . . . . . . . 10
..^ ..^
|
| 128 | 0cnd 7888 |
. . . . . . . . . . . . . 14
..^
| |
| 129 | 36, 128 | pncan3d 8208 |
. . . . . . . . . . . . 13
..^
|
| 130 | 129 | 3ad2ant3 1010 |
. . . . . . . . . . . 12
..^ ..^ |
| 131 | 130 | adantl 275 |
. . . . . . . . . . 11
..^ ..^
|
| 132 | 131 | oveq1d 5856 |
. . . . . . . . . 10
..^ ..^
|
| 133 | 3, 26 | syl 14 |
. . . . . . . . . . . . 13
|
| 134 | q0mod 10286 |
. . . . . . . . . . . . 13
| |
| 135 | 133, 52, 134 | syl2anc 409 |
. . . . . . . . . . . 12
|
| 136 | 135 | 3ad2ant1 1008 |
. . . . . . . . . . 11
..^ ..^ |
| 137 | 136 | adantl 275 |
. . . . . . . . . 10
..^ ..^
|
| 138 | 127, 132, 137 | 3eqtrd 2202 |
. . . . . . . . 9
..^ ..^
|
| 139 | 117, 121, 138 | 3eqtr3d 2206 |
. . . . . . . 8
..^ ..^
|
| 140 | 30, 45, 139 | 3eqtrd 2202 |
. . . . . . 7
..^ ..^
|
| 141 | oveq1 5848 |
. . . . . . . . . . 11
| |
| 142 | 141 | oveq2d 5857 |
. . . . . . . . . 10
|
| 143 | 142 | oveq1d 5856 |
. . . . . . . . 9
|
| 144 | 143 | eqeq1d 2174 |
. . . . . . . 8
|
| 145 | 144 | rspcev 2829 |
. . . . . . 7
..^
..^ |
| 146 | 17, 140, 145 | syl2anc 409 |
. . . . . 6
..^ ..^
..^ |
| 147 | 146 | ex 114 |
. . . . 5
..^ ..^ ..^ |
| 148 | 147 | rexlimiva 2577 |
. . . 4
..^ ..^
..^ |
| 149 | 1, 2, 148 | 3syl 17 |
. . 3
..^
..^ ..^ ..^ |
| 150 | 149 | 3adant3 1007 |
. 2
..^ ..^
..^ ..^ ..^ |
| 151 | 150 | pm2.43i 49 |
1
..^ ..^ ..^ |
| Colors of variables: wff set class |
| Syntax hints: wi 4
wa 103
w3a 968
wceq 1343
wcel 2136
wrex 2444
wreu 2445
class class class wbr 3981 (class class class)co 5841
cc 7747
cc0 7749
c1 7750
caddc 7752 cmul 7754 clt 7929 cle 7930 cmin 8065 cn 8853 cz 9187 cq 9553 cfz 9940 ..^cfzo 10073
cmo 10253
cprime 12035 |
| This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 105 ax-ia2 106 ax-ia3 107 ax-in1 604 ax-in2 605 ax-io 699 ax-5 1435 ax-7 1436 ax-gen 1437 ax-ie1 1481 ax-ie2 1482 ax-8 1492 ax-10 1493 ax-11 1494 ax-i12 1495 ax-bndl 1497 ax-4 1498 ax-17 1514 ax-i9 1518 ax-ial 1522 ax-i5r 1523 ax-13 2138 ax-14 2139 ax-ext 2147 ax-coll 4096 ax-sep 4099 ax-nul 4107 ax-pow 4152 ax-pr 4186 ax-un 4410 ax-setind 4513 ax-iinf 4564 ax-cnex 7840 ax-resscn 7841 ax-1cn 7842 ax-1re 7843 ax-icn 7844 ax-addcl 7845 ax-addrcl 7846 ax-mulcl 7847 ax-mulrcl 7848 ax-addcom 7849 ax-mulcom 7850 ax-addass 7851 ax-mulass 7852 ax-distr 7853 ax-i2m1 7854 ax-0lt1 7855 ax-1rid 7856 ax-0id 7857 ax-rnegex 7858 ax-precex 7859 ax-cnre 7860 ax-pre-ltirr 7861 ax-pre-ltwlin 7862 ax-pre-lttrn 7863 ax-pre-apti 7864 ax-pre-ltadd 7865 ax-pre-mulgt0 7866 ax-pre-mulext 7867 ax-arch 7868 ax-caucvg 7869 |
| This theorem depends on definitions: df-bi 116 df-stab 821 df-dc 825 df-3or 969 df-3an 970 df-tru 1346 df-fal 1349 df-nf 1449 df-sb 1751 df-eu 2017 df-mo 2018 df-clab 2152 df-cleq 2158 df-clel 2161 df-nfc 2296 df-ne 2336 df-nel 2431 df-ral 2448 df-rex 2449 df-reu 2450 df-rmo 2451 df-rab 2452 df-v 2727 df-sbc 2951 df-csb 3045 df-dif 3117 df-un 3119 df-in 3121 df-ss 3128 df-nul 3409 df-if 3520 df-pw 3560 df-sn 3581 df-pr 3582 df-op 3584 df-uni 3789 df-int 3824 df-iun 3867 df-br 3982 df-opab 4043 df-mpt 4044 df-tr 4080 df-id 4270 df-po 4273 df-iso 4274 df-iord 4343 df-on 4345 df-ilim 4346 df-suc 4348 df-iom 4567 df-xp 4609 df-rel 4610 df-cnv 4611 df-co 4612 df-dm 4613 df-rn 4614 df-res 4615 df-ima 4616 df-iota 5152 df-fun 5189 df-fn 5190 df-f 5191 df-f1 5192 df-fo 5193 df-f1o 5194 df-fv 5195 df-isom 5196 df-riota 5797 df-ov 5844 df-oprab 5845 df-mpo 5846 df-1st 6105 df-2nd 6106 df-recs 6269 df-irdg 6334 df-frec 6355 df-1o 6380 df-2o 6381 df-oadd 6384 df-er 6497 df-en 6703 df-dom 6704 df-fin 6705 df-sup 6945 df-pnf 7931 df-mnf 7932 df-xr 7933 df-ltxr 7934 df-le 7935 df-sub 8067 df-neg 8068 df-reap 8469 df-ap 8476 df-div 8565 df-inn 8854 df-2 8912 df-3 8913 df-4 8914 df-n0 9111 df-z 9188 df-uz 9463 df-q 9554 df-rp 9586 df-fz 9941 df-fzo 10074 df-fl 10201 df-mod 10254 df-seqfrec 10377 df-exp 10451 df-ihash 10685 df-cj 10780 df-re 10781 df-im 10782 df-rsqrt 10936 df-abs 10937 df-clim 11216 df-proddc 11488 df-dvds 11724 df-gcd 11872 df-prm 12036 df-phi 12139 |
| This theorem is referenced by: nnnn0modprm0 12183 |
| Copyright terms: Public domain | W3C validator |