Scribd
Upload
15 views36 pages

Modular Arithmetic Module5

The document discusses various concepts related to arithmetic, including divisibility, greatest common divisors, and linear congruences. It explains how to determine if one number divides another, the properties of divisors, and methods for finding solutions to linear equations. Additionally, it covers the concept of relatively prime numbers and provides examples and steps for solving related problems.

Uploaded by

suhaasbg7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
15 views36 pages

Modular Arithmetic Module5

The document discusses various concepts related to arithmetic, including divisibility, greatest common divisors, and linear congruences. It explains how to determine if one number divides another, the properties of divisors, and methods for finding solutions to linear equations. Additionally, it covers the concept of relatively prime numbers and provides examples and steps for solving related problems.

Uploaded by

suhaasbg7
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
D phe VA Mocluboy Arithmetic Aaistont professor Let a b be atnte [Link] Diviestbel’t 4 I- 6 | Say that 4 divide b y theyre UAE om ire: | k Auch ‘Yaak b=aKxk. | = a dividu 6» we wrttt a alb. | | rt a dou not divide b, wel write a fb- Ex:- th 18/94 | «> T= 13XS fiy In)ay 6% 84 =18x7 | itiy Hoy sae Propenttas \— “ihe 4 Qala ¥aEez, ato ayers vaez, ato iD ‘la \v gem @-ala ¥ aéZ © afb v albx wxEz ® ale ond ‘ale =F albte @ alb ond ale =7 alb-e alb amd ble = ale | Devisten Algost tem t= Let a,b be +w0 Embeguis ,a to tere “xine tne yr such that b=agtn, osela wo cd the peice amol x t ths ts bow ow the quotteat , when b iA atuidect hag a" ne Citlsenal = Divison x Quotient + Remainder: Let a,b be two integers a) integin gre ade to be GC.d aod 6 id 4 tA tommen AIVI50A 4 a &b) lemme divider (1) 9 Ja omol gh ci tity nla ondl hip = nl (4 omy a od b tA alse a cliviaoy 4 9] G euatest common Diitiser CGC D*. | | 4 a ond b Is wr tten ow (a,b). G-c:D tthm i- Let a,b be, two lachegers such that b=ayt” ths sumasn der ” Euckid'a Al govt rato. There existe enegers yn oe nelal Tha i4 dome ar" IA va the quottent: , whim b lA divided ae a LL Divident = Divison quotient + Remain dor ooreatut commen dtviapn (4c Dd) Let a,b be two cot An tintegen gze 14 said ee a fe B Gs Aa a 4 . . | ih gla ono gle tne g ™ neu aivizor 4 4 & bd ity hla ool hl =y bla Ute a and b ts abo & divisoY 4 9) a anol btA vor tiem oA Za.b) 4 ang remmen divisor Geo H | Fusli'd!a At ont tM : : ‘ Lucida goa thm vA a metheel to pene! fhe " divicelen . cb y 100 mide ab by succusne ‘ A / d il be Fhe Gre? ei lout um" 30 gumarnde W ; =(a,b). thn by wating efivitem algorNin a | uly ; . a | dasa uf we cam fev ie mY auth wl VLE Equation. ‘ fin +07™ att = G who at¢o.b+0 called a lintan dia phomtine cou Uridmeus Linea Di'ophatt? and cis om inte “k tyradton in @ Yeowablr xy + x % Y Veruiablis. workin sulei Given axthy=C Steplé timo taba CaCO 4% a & &) stepal verity ale or not. tt dhe thm rt Wes mo solution . z+ ale thm time! a pantielan Aolutionte step 3 : eultds attby=e.b dimdine, 20 & yp uti al yori thm Auth that oot eee Step © guural solution UA Rv by. = 0- Bm , y=Y4oth ™ mMEZ. Froblews 7 te Fimd gecl of a) (84129 710) pinel GreD Y (3,12) 3)12 C4 cz 2. GeD=3 Cth Lert non- Bee gumeum dur) b) (9,14) —¥To Hrd GCA 69,14) q)14 (1 09 SIAC! 5 4 )5 (1 TH Ch 4 Oo 68 Geb-D= yy Cru darten- yet pumandoty c) (8,8) —y To Final Ger 2 gC & (3.8) o | 1 G@eD=8 Gaurt mon - 3070) | eumasinder) ANG, 6) —yTo Find @-C-D of (16) 6 Cé oS : oO GEeD=e Verity the Diophamtiine (or) mot. equ atten solutions bxi @ 6 +514 =aa : atvm Ly” i4 a tm dorm aa+by=c .1a56,b251 ware Ca b)=(6 523 : -ONa ; 4 anol 3f22 ot clot Ae Me hieon, oyna s0latTon ] @ aax+lhy= 11% Givin £47 16 of ant by =e ., 2233 (33,14 7= 14) 33 (2 38 “oo af Solutren +o Finel Dio phot m™m @ oa rtiay = 168 P ee Given Ly” % oF the gor art by=e a=70, baller: cab C70, 12) =/4 =a zo) nr (! wt howe ae “gay vl! na = 1t#0) +42 4a qo = 1(4a+as 2g) 4al! wo = 198) 414 Se ig )2el2 as = alla)to ag TO Fimol the genurad Ao Wen = y= 4a - 188) y= Ha! (40-1429) py 2810) 1(40) ty = atha) — 1199) my = e[na- a0) - 1070) py = 2 (la) - 240 pps 30 [-a) + Hal@ Q xb 4d sy 16t 2 19g = 40 (-as) tua lee) Go ee Ap =~ 2h = oy tA a pax teculan dolution - wural Aol 14 n= Xo- 2 Be G4 Ao: Papin ° % Bat Seva. bere =) 2 = 64 aly erOm 1H. 14 x = -ateeme a Ee Thur 42-8m-Ay 7 aomtay 7 E? 5 thy quot alt, cll @OsexerFay=4o Giver ty” VA of Hu {orm att by =e a=56, b=78 > C= 40 tab) = (66,72) = 8.50 56) 7aC! 5 =y FQ = NSO HE “a 56? & 56 = 3Clb6)+8 “ee l® le = acadt+ 0 a die =840 2) G@GR 4 Ca. bd =8 jo Fimel the quand Aoludton - 8= 56-3616) 8 =56-3[7a-1(56) g = 0(66)-317%) & = 56(a) tal BD x'Y by 8 oy = 56 (a)tIU-D to=&, Y= vara peorttoubern 40 lution 5 o = -b al goludiron (4 X=%0~Z™: yey-2m The re a- Fa, ya-3-5é6m 6 daa- mM, Y= 3-F™ Thy 4 = -qmras Ge va the qewred polutton. @ e4x+tasy =18 Given uy ra oF He fe A= 9H, b= 138. c= 18 Carb) = (a4 ,138)= 6 20 ay)iaals >) attby =6 we hove Haat 138 = 5004413 10d 2g (8 = 3(6) +0 : To Finol the polation. 6 = ay -/ (18) 6 = a4 -I (lax -fe4) 6 = 624) - 'U38a> 6 = ay (62 HB8-) . x ba ow Ig= 4 Cpgre 1232? Ho=- “hs Yp= 53! gurl sol” 1's =7t= |g-der Relatvely Prime Mumbetrs: Two numbur a ancl b aru Aatcl to be gular Prime. 07 Co-poime Yq ane! only tt (Ca,b)=1 1-4GCP of aad b tad. Eon t- (48,15) =1 +* Bama 15 wre sala tidy prem Congres t- Lee m be a postive mace anc a.b be amy two tntegers, wet say tra a conceuunt fo b moclulo m" 4 mca —b) symbeltcally we wrtte azabtmodm) 4 m[ca-b Ex’) B=23emods) "5 divide (8-3) 4 5/5 12) aszatmodud %° "Ieas—2) We tac. 13) 79 = 8CmokF) %6 afFl. Note +- wry astcmoctso) di'g't tor? unt te ima the form 37 cam be exprasecl | SHRED, git? gy gtht? octelo, then tis the feut la) any number ws ene ot 34 BAK = pemocw), HHS 3 pmoclto), 34**% atmadi ond 3h+t3 =4¢modla) According iy unt digtt ¥ any number Y sthe Form 371s ent 4 1,3,9 orF. a) 6726 (moclle) gor all n. of unt chigt't a omg number y the form nis | (4) 5%= stmodto) jor an: ot unt digg g anny num be; of th form SKS (5) Aang number of the form &" can be sapruseed an ene of atk, ghkt! Q4kta oy gukt? otk =e cmed lo) , a@tk"= gtmod to), 2t*?% yemodn and otkKM= 8 ¢moclle) Accordingly unt chiguts y any pum btn of tae form an "A ome 4 6n09, 4.8, 6) Ruy. number ot the dorm #” can be Laprttol on ene o quik, put! 7H Pg 4K =) ¢modl) , 24*t=21mod lo), pF amet omel 44k = a ¢mocllo) - | Accosdtingly, unt cuit af any number 4 form FV ts o7e Bal he FG, OF Bs (72 Wumber of tHe form 4%= gen (s) Mumber ot the 4orm ats 22" ym qn gee (a) wum ber ag the He, Ie Finch the Remeaunden coun) Find Mme srematriden hen 98? 1% divide! by HF then 220 t's alevieol 5 woes 4 soln! 08% 956 2al(mod4 7 i 2a 2¢-mocl 47, gol: 245 (6 =I (mods) Hy (9882 CAI CmMOAY ? pegagels (04) %= 1?%¢-mocl 5) a6 at dapoeonaennte > i 300 oS =e tmocd 471 47) air) 9300= 1(mods 49 | : a gltgrs iexattmod yy) ms | 2900 gl = gtmods) 22° = almod®) wh 230 1% aivi'decl bg 5. ae Find the Remaunde wher | the number 1091's divide by 12+ sol} a4 6=3¢mocki3) 5. (24)°= 943 ¢-modi3) w= = 4emodis) ra)auacie ° 13 Fe I emodi3) 3 104 100 — ue 59049 (mo liz) fq (190) 5 =3¢ (9100)? comectis) (eaeteaal 23" moolra) $3 70 Ql900 ¥ = 59044 Imodnyeay l000 _ oh = 3cmodr) 27 a6 The memunder (4 3. = 1g ts the Leart ne vamatel 4) 424 13 yay, “ad =H =y 9°? = aaou trod! a%= ;emod 49) + pne ramalnd 7 fat nd ne Remainder whan os ty divided) tne run bo Ci by 13+ solm 200_ be > ( ao mods) | @ rend ne Remainder w the umber (1 ys divid by 10 /72= 3 Crmecl lo) (17 3Ylz atemod 10? pps tmo of 10) $43, (ita tumod ie) 7 (19 "a 1 cerned jail, Pz aatmodle) jporrs atmool 10) @ Finck the pemacinden when FS Cs dive'decl ky —7 gts umnaeleeg (Fits icmoel Loe 3 moll ee — = doris FT: Tha eo Limean Congnuence 2 A tongruumce g th Collect a linear congrusence fn x, A Vntegen vahuk x which sahafeu He Limca congrumte iD called t'ta solation oF aoot» ¢ torm axz= blmod™) Us | Note: | 0) The Linean congauente ax =blmodlm) with Carm)= has t$mno solution 4 d%b wy exactly ca in tongrunent Aolatiera modulo ™ “f d/b | (@) zt a ono m ane eulativel prime h4 C4M)=/ tum tnt Linea corierivienee aL bemooln) has a | Unt’ que solution. | (3) Let mEN . ub be Untegun . rt aandm cane | ptlativel, prime tue a Sol” ay Antear congrruuente ax sitmbdlm) 1% cablect am imvouwr of a modulo m. (tt x =a! ¢moodm) Working procedure +o sewe limten cen qui tt. Givm ALE bemool m7 —+ lM step! Find [Link]=ol steph! check cohethen Alb | steppes Ep olp-thim tay tI) has vo dolution. ry Lp a]b +nim tq, ) has al tn tengrceent solution. T Step i “et Gon, bop amel 2 ng — TM ey 01) becomes AX = 1 lmool m—¥ (2) with (AMo=) amd '/p +f eg" ta) has a ung solution a to Steps. The ol tn comgrrent Aolu Hows 4 4p 1) oy wo by. Xo » Xot tO... aytld-1m er Propsttes of moeulan Azithmet'es— O cctoned oa) clémodm) = anol b= clmod m).tua 2= © azbimed™) ee) © aactmod™) anol b= clmoclm). tw il Hun amy c, ate =tbte) @ azvcemedm™) jor ny ons clin) tn jo” any c. f=9° pam maken @zp a= btme anes @ rp ae 2 be cmoctm) a oy @ zy ac = belmodm) 4m 4 a aeblmodm) | Probluii= Put : K=0/ H=0 EZ ii O Solve ! ax = ¢moct a5) 2 LE Aalmocksgy 1's dhe Aoludd Mere A=8. =), m=2a5 @ (asm) = 69,25) =1=0l (Aad J ama "1 (re otf bd es Thur KVM congruuim it how wnrque. 60 lution. Cle andy 85/gy-1 =y Seeldop SF =) on-| = aok | =Y a= ask tl => 72 98k T! , REZ - 2 | By imspectton For pay woe yt x=96 - B=12 ez SL=13lmodds) @solve i 3x= Ecmeocl 18)__sp Heve AZ, b=6, M=a$Z d:ged = Ca,m) = 3.05) ea8e amd clp = 3/6 2 ThE given congrumente has 3 Zou’ * divide 2y%0) by iis 306 = 8 (moda \—y 2) =y 32-6 = k 3x = ar+h Ls akth/z Let 128 and tu suemalnin a sol" ot oblarned by ot Th. 1 00 ran = 2448 at alle) = 6,10 5 eae B Thus +e holudion 4 Ly BD aus asatmodla), 25 6C(mod 12), 2=10(med 9). (solve Mat 2H gmod 25) = bimodw, Solty Cominco pea, Mae ca.m) = 1-95) Here Qzell, b= cde ob (eg) =? d= eas d=(2-! xa = a= (Sp x12 ie _caim)= (asa) eS daqeos Wy Che lb) Ae THe. ge ten. ce pnt'qur Aoludlon cleary arebemodm) mfax-b y =F oy 29fyart 27" Ea eae [1% = 25#Y LEHR FE Sy LE HEE || y= aS kKHY a ——— pat F=9. 228. Z 7 pce oat wt pat k= : P 0, £24 gz pod bal a put R22, Tae puk k=l »"=84 ae? a x =armotA? put Ka) =54 kl pn Botudr put F=3) m= 2h ¢? put po4, Hala g? ul pul = 95 nee put B= 6, 2 =H EZ | thus aeialmod as) ist solution - (4) solve 4% = almod 87a fin paptiodkton’ 10 | tht Jorm 4 ane pert a=lay b= d=ged = Can) ll Baa say 4b» aia geen con gruumle har solu ; a mg ztacmed’) -¥ (2) 22 gee ened or 4 /an-6 =7 71-6 4k at al fax xot™ x0 +2 | ot 3™ - HO Od APE yp 8X8, HF EXE. a “A mam 5» 8,10 7 xegemodal), 2356 it gimodaiand 1 = toc mods au tH solution 4 tH hi caualion - O Fenct the Leash oligtt 6 2013 az soln? 72003 _ Z 4x503 41 = 2 IKES a¢modl to) : avs the dat dtigtt @ Fenot the lout ditt gid | soln; 13513 ¢modl lo) 13 = 3tmed to) 137= 37 C-mod 107 137 = % lmodl to) ~1Cmoed tod (132)"8= c-18 temo io) 13° = | (mod tod 13°4 13 = 3 Cmod ty) ot 3 tA the Lat dtytt. @® Find thé sumea'mder | when | D1P5XU3BX 59 US dlred dec oy I | | solv? 11 )175C15 | ai 1752 o(modu) 65 55 10 Hatt Mae N2= acmoedu) 4h | 53=9 (modi!) a (FEXUBXS 3 = 1OX3x4 cmedl Ww = 070 CmodI) 110701 24 ae 50 AY tne oumainder UA & a 64X65 XLELA devittee) by 64 soln’ 64 =-3 Cmocl 67) 65= -acmod 64) 66= -1¢mod by 1164X65x66 =—6 Cr0d VP | Z6lemodsv | se presumain den (61 3S 1B5XTHXYB EA sided soM: 4)135(19 4 2 ae 1352 atmod 63 4 wn aed By snemeds am aus (é Than ys z atmod f ax4x2 [mel Vita x 74 Hs = 16 (mocdl4) Tor wt The sumeunder tad. ] |@ Fincel thet Leort positive | val a Auch Hot QO #1= x0modf))azbrmady az » a-b=nk 64 Ji-usexk of. Bl-a s3K8 «1 The valu yt tnF @ 784+2x = a0mod 5) pesa-3 25m (08 ong inbeger) Fora 0 yt = 5 [ot bok Pe | Ante 025 valu eJ 75 +5290 1h crus —s-phe daank vals of % IA? @ sracarayimed4) Bq-(A4 BIE4E gq-4-3 = 4k B$6-L=4AK ajae 8 Aaa A paaee Leowrk 4 | poarhie va § mud-tiply bg Bb-a= BH A Te hat valli a | Poly nomial conepuuences FAD =aoxN4 Qa l4t -- ané Z, ou presents +he polynovt ) where N21 ad, +an = ocmeal-™ | amol avai 42 Cee Root of 40) ¢medm) tao’ CS callecl the soot oF $ (xemohnt 4g fllj=20 (modm) Of 4+ m|£c0) System of Limean cenapuiint conslden a agit 4 Linton congo on axdb enlmodn) cot tay = A Lmocl h) hon el polation 4 heap le solulon 4 ace ats ie ina varua bles * waitin a veou'a bles The Austen The system hor & urntqut Fermat Little thease ; rf P’ ca,pr=) thm @ ableiimodp?. is a prime num ber aol PX& cord Pol deviant ble by P yh Wilson +hneovm: re p ta @ prime mumby tun Cp-i2pe (p-101 = tpi emodp) tp-a)! = 1 (moolp) ani 5 ts prin mum ber , we check that te ase ormod 5) (04) 2/5 iy 4121 aaa fy 315 ttmods) ft 5 = ocmodls) lor) Stes . -1tmedp) note: Probluom eo Polynomtal son “ I Erma the moots ot th potmomal x24+2x- 3 mods) soln! cewtden $OO= 2+ 296 — put £0 Swe -3 4 ocmod 5) 2€(™-1) (6-D nel gu = 0 BeCmes) a4 yor faj2 5s ocmod 5) u=3 £063) = (0 # OCmod 6) n= 4) tty) = abso Cc med) wp eel, MED ATE tne routs Lt fenyemod 5) 2] Selve +ve comop ure 45-342 42 Z0t-mod +) solni FO = yS5—3x2+2 =O Cre 4) 1 the Wer os 4-423 > 3, 00-8 Selo? jee gn2atommed D £01) =ozocmed 3?) 0) =22 sotmod 3) $t3) sarsgormed ats “solute WO ty + £(-37 =-asS HO cmodt) £(-ap = -4a Bo cmed 3) £t-) =—-a #0 Cacia wt XLELtenod#) & xe -a (med 7) ou tH sol” ag. 2 tz tmoda) Sa” Bieta oe sol = *, aia -the + 21-32 3) Find ot e soot % comapuuna le 2+ 22-3 20m $i) = aoe eens SO cmed co\M: ev em ao: OOF the sotten tre, om tet ak (0,12) é-4,-3,-2, |r y ocen)= -75 oO $(-29 =-1sxfotmody) $¢-3p = -36 Zz 0tmod4a) "| Bt) = -6#2 (moda) £ (0D =-3 $0 Cmod 1) £03) =3020¢moda) $ID = oz 0tmoda)r | Fl) = 64 Ftocmodq) Sar=9 8 5-3, lyn cmocdla)d cow the ooh ae comeuue . yj x= 6Cmoda), LE 1Cmed 1), 25. 20m0d 2) 9m srooty o-t “the quvim Comgpusim Ce- Chuness Fematnden Thtovem + Let M1sMag.--- Me bE Posl Hye siateger « sudo velg prime ' paris elm, msI= 1 fo pS Let biyb2---- bY bE on brteang inter, Then +ue system a Lineot congpruin (es xX =bitmod m™,) X= be lmodma) x = balmodma) hou exactly enc solution moeclulo tne procluct m Lo working gules Givm xXSbi tmod m1) x = ba lmodmy a bert mool ma) steplt verity ime my d=t +07 ah stcpe! Finck M=am),.---Ma ---- My step 3 Fenel me = for Babi HM stepa* cotiden the Ldintot conapuuien tes MX =limocd mr) au satiefeck wrin tu unique polutien . steps: The Uniqs solution ef the system 4 Hie comet vhs qv by. N= byt, + b2MaX24 -- tb aMs 21 moclulo M. Problowu + 1 Solve the austen 4 Linton congruent oy sumealird. theorem! = aimodsa) ,4s3lmods) = acmodD | lHere - bi=a , br2=3, bg=ad m=3 , M5, Mga. woe veritythat (3,5)=1, (5,47=14 (a=p=! SMa Mix Max = 3X 5% = 105, Oh M=105 105 _ br= 2 5 ba=h m=5> my = 6 , M3 = 4 woe veriply dred (5, 6)21, CORDS MUSDAT = 210 wo Miz Mp xMygr~Mg= 5X6 KTR MgM5\ = \emodrag) 30 M5! = \ (moa? -\ =4 Z, Ms 30Ms!—1 [xo A= “lla! xc Ar2ajuraAc a 1 Li The untae, solution ef tht ee ate? Bug i el 2. = by Mi Mil + ba MaMa) + baMaMy! mo cl M XS BxXuyax 3+ dx asx St HXBox 4 mool 210 w= are +as50theotmoddato) 1 = 1008 ¢pmod ala) x £198 Comodl alo) 14 teu warn a solution, 158 t=stmodds3) . 1 =almoeds7, x= 1tmed un) @ solve Herve bh= Qa, br2=3, bg=aQ M,=3, M2=5 5° ™3=4 we verity thot 63,5751, 15/12!» (n,37=) oe MM xmMxXmMs, = 3x 5x9 = 165 MaM 5.55, Maat = 15/5 = 33, Mga =198 a1 ne Now, M\Mj!=ttmod mm) 55M! =I bmodl 3D mia mM, M3! = Vtmod m3) 33 Mz! =I lmed 5) Mp MaMs3. = 1 tmod ms) 15 ag! = mod 2) + a Malas Thus, a unique soll X= bM Mi! +b: Problum en system Minkan Congyuenie rin a Variable } Solve the system Lauatien 7X24 =10Cmod 16) on ef duty =1mod 16) > Gum 724-34 = (moot (6) ant oy = gtmocl 6) o) a=7 , bFa , Aalto cua, a€=5,429 col Ca, b, n= CF) a6J=! Col Cah aber. wy ged (a9, 6J=4 nN=16 The system har a Uevigus solution Zot BYy= 100mockl6), x5 arts = 4 mocl!6) x3 BSu+15y = 50 (moa 16 600 HISY=9F (mod 16> = > oO 24 = a3 CmokI6) : = 16 teak yx alek+e3 $ | 21x03 ov 29q2—-23= 6K = YX 2 k=!) 2¢2 , hear xgz k=a? 2EZ 1 key! BEAEZ - fesstmodie) aw Now 42 +34 =10~mod 16) 24 +34 =10¢mod 16) By = -I (mod le) =y Mf ut (or) Sy-H sie y =lok—l 5 ker yf2 3 k=oKeHE? (modl6) | Ans @ solve The Aystom —} a=. b=6, m=! cay ,d=3, d=a ot equations Jxt6i =1lmod3) hx 15y=acmoda) nsdn cella, bshd= geclle.6,7) =] +t ged Ca,b, indie Also ged Cacl— be, oo The ays lent has a unlqut 60 => The system has a solution, n= ged la, 792! lution. conslden OUtEGS Iimod 7) = almod#) %9 Mize gic artt6y= imod 4). Btts4 zycmod P DVO f © —___ —62t= -3 (mol): ax = 1 tmolF) SY F ga =7 es ee . a put kel? {x= 4 EZ. , comsider Qt +6 A=H, Bté oy AWS \= | tmocl ) eltmodD. =-F (mod) of eye (07) ytd tk a7. = BK F put kel }JysoyeZ a [ysocmodt] aws OS Problema on Fermat's ttle Theorem. State mont ee tp? gg a pola mami ber am ec! ts drviat ble by e al“) =o med p? at! = 1tmod p> Problems i @ Erol 33! mod + By cermatis litle pormm (a=3, P=) aP'l=ttmod p) 3 = iemodlt) (36)%s 1S (mod 4) ao | camod 4+) MW 30 at emod 3) uw ow 3= 3 cmodt) @s-T 372104 devia ble by 3\ By Fewmat' uttle orm heve a=@, p=Fl al! =1¢mod Pp) 20 a et imod 317 30 (or) @°-1 Z ocmed 31) gimce He oumounden (A 77, WE cenctude Hho g2@1 fa dintarble by 3)- @ Find tu nemainden colon 210° (4 divided by 13 By Eenmot's Wttle Huorem heve A=2 ,Pp='3 aP! = 1 (mod p> g! = emo 13) (2) 87H 33 Cm 13.) aoe a8 2m7e = 1 cmodk 13) 22M 94 = 24 (mold) plocoo = (ecmod 3) 13) le (1 3 21002 = acmodl3) 3S W000 fy, divided) by I3- otls (@ He 2. BLA THe suwainden whim 2 @ ser a=, Gy atwistble by 21 by wine By Fenmat's little theorm. heve anke ee 227 -;20 Umeda Jatt tien bis J 22° =| (mok 3) 3goe a BO =3L (22°) = emed 31) fee D = (¢med 2D aaa 2'°= 1024 1 tmod 31) ——-7@) prem saycre ds i ae Ga goed ell tmod 31) ‘ 234? =1 (mod I Caclll +1 on bls) 2240S ag emod ai) stme the gumumden (A gem we conclude hat 3Ho eo -! (a divrarble by ZI. ~g_ Wilson's Theorem past pie 04 rece number p= = (p-v (mod 6 — 7 ‘. ee on — — _ = (b+)! = -1 (mod p) nt ee aie 4 — _tp-2)! = 1 (mod p) = = (no oe te Upsa>1_2 {bat ) tod p) «4 . a a a 4 Find the reminder When 15! is divides s We have pea 3 2. The toninder ts 2.4 Find “the remindec rhea 14! t divioled a JE 8. cons 7 -m1_=(b- , oa tal = 8 (odta) eg te the tenia a... a ee \% I: 90 ie the reminder = 28 Bod The_vemnder ulab+s L dle et | le hare ps3) BE __ ae 5 = By soilsons theorem ae Ht h-2d ts 1 tm — ee _ st Ulaal)=u tmodb) —O I oe St = = 2a (mods) — oO 31) pols | 43 _04® Comayrwences EY ubal)+5] = 442% (mods) Ylrat)+s! = 31 4 [2a \)45! <0 (mods) “Baltes hen oa ¥ aand n te am 0; Ave, Anteqers 10) pee “8s nol dite htog gle plone ee M_Need not A apt ES Ltmodn) pas ELE a on & prime divs ob 9 a 1 §o) = Oe( Py ifetyy e — ' e 2 dled = tox (ETT yy ote dko)e box tx rt Glu)= te PROBLEMS 4 God “Ih tumnioder 6.7 is divided by se —_ — We have (5 36)=1 4 “es she eb pp I (36) = 12 pbs. . aT Euler's Theorer oe = \ ([Link]) . | a ee ee. | [tind - he ‘Tamainder ahen_3 a = teal Gioye1 — —_W10 = 245 sua — SO 2 _ 1 ns =10.x{ frye) — =e = : is they, Foe a ao $= \tmoan) [este LOmod to) ‘ 2.13")"= 1" (modo) 4 MHey zs: | Eind the reoninder hen 23% is divided boy 25 Iwe hove a=283 Wa25_6 :, By Euler's Theores 237°= 1 (mod 25) w)e— 6 25) me | (node _ 524 <4 (mod25) 5 = s 2) 2565 23° = a56(modss) 25)256 (to 2 10 0 ae V0«® gs®= 6 (moda5) +. 6 isthe remainder N= Ib = 3X5 oa Nt d(n)= tex(-$)(F-4) 28 | |e: ‘safle = Limod n) Eee Ses oi | 3° = Ltmod ts) L (4) = 15 (mods) | te tmodisl=> © l wiki += 1cmodis)—» © | 4% = utmodis)— - | v aus (modis) | 2401 ] by A =utmodis) —> 6) | 3° = utmodis) | 44 (0x® x@) aya yas (mods) i + 4 is The remainder if | 1 J | yy

You might also like