/ Class of 2001 / ClassOf2001.iso / Scinotebook / scinoteb / help / dm12-4.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 25 20 54 68 69 73 20 | 64 6f 63 75 6d 65 6e 74 |%% This |document|
|00000010| 20 63 72 65 61 74 65 64 | 20 62 79 20 53 63 69 65 | created| by Scie|
|00000020| 6e 74 69 66 69 63 20 4e | 6f 74 65 62 6f 6f 6b 20 |ntific N|otebook |
|00000030| 28 52 29 20 56 65 72 73 | 69 6f 6e 20 33 2e 30 0d |(R) Vers|ion 3.0.|
|00000040| 0a 0d 0a 0d 0a 5c 64 6f | 63 75 6d 65 6e 74 63 6c |.....\do|cumentcl|
|00000050| 61 73 73 5b 31 32 70 74 | 2c 74 68 6d 73 61 5d 7b |ass[12pt|,thmsa]{|
|00000060| 61 72 74 69 63 6c 65 7d | 0d 0a 5c 75 73 65 70 61 |article}|..\usepa|
|00000070| 63 6b 61 67 65 7b 61 6d | 73 73 79 6d 62 7d 0d 0a |ckage{am|ssymb}..|
|00000080| 0d 0a 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |..%%%%%%|%%%%%%%%|
|00000090| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000a0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000b0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000c0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000d0| 25 25 25 25 25 25 25 25 | 25 25 25 25 25 25 25 25 |%%%%%%%%|%%%%%%%%|
|000000e0| 25 25 25 25 25 25 0d 0a | 5c 75 73 65 70 61 63 6b |%%%%%%..|\usepack|
|000000f0| 61 67 65 7b 6d 61 6b 65 | 69 64 78 7d 0d 0a 5c 75 |age{make|idx}..\u|
|00000100| 73 65 70 61 63 6b 61 67 | 65 7b 73 77 32 30 6a 61 |sepackag|e{sw20ja|
|00000110| 72 74 7d 0d 0a 0d 0a 25 | 54 43 49 44 41 54 41 7b |rt}....%|TCIDATA{|
|00000120| 54 43 49 73 74 79 6c 65 | 3d 61 72 74 69 63 6c 65 |TCIstyle|=article|
|00000130| 2f 61 72 74 34 2e 6c 61 | 74 2c 6a 61 72 74 2c 73 |/art4.la|t,jart,s|
|00000140| 77 32 30 6a 61 72 74 7d | 0d 0a 0d 0a 25 54 43 49 |w20jart}|....%TCI|
|00000150| 44 41 54 41 7b 3c 4d 45 | 54 41 20 4e 41 4d 45 3d |DATA{<ME|TA NAME=|
|00000160| 22 56 69 65 77 53 65 74 | 74 69 6e 67 73 22 20 43 |"ViewSet|tings" C|
|00000170| 4f 4e 54 45 4e 54 3d 22 | 33 31 22 3e 7d 0d 0a 25 |ONTENT="|31">}..%|
|00000180| 54 43 49 44 41 54 41 7b | 3c 4d 45 54 41 20 4e 41 |TCIDATA{|<META NA|
|00000190| 4d 45 3d 22 47 72 61 70 | 68 69 63 73 53 61 76 65 |ME="Grap|hicsSave|
|000001a0| 22 20 43 4f 4e 54 45 4e | 54 3d 22 33 32 22 3e 7d |" CONTEN|T="32">}|
|000001b0| 0d 0a 25 54 43 49 44 41 | 54 41 7b 3c 4d 45 54 41 |..%TCIDA|TA{<META|
|000001c0| 20 4e 41 4d 45 3d 22 54 | 69 74 6c 65 22 20 43 4f | NAME="T|itle" CO|
|000001d0| 4e 54 45 4e 54 3d 22 50 | 6f 6c 79 6e 6f 6d 69 61 |NTENT="P|olynomia|
|000001e0| 6c 73 20 4d 6f 64 75 6c | 6f 20 50 6f 6c 79 6e 6f |ls Modul|o Polyno|
|000001f0| 6d 69 61 6c 73 22 3e 7d | 0d 0a 25 54 43 49 44 41 |mials">}|..%TCIDA|
|00000200| 54 41 7b 43 72 65 61 74 | 65 64 3d 4d 6f 6e 20 41 |TA{Creat|ed=Mon A|
|00000210| 75 67 20 31 39 20 31 34 | 3a 35 32 3a 32 34 20 31 |ug 19 14|:52:24 1|
|00000220| 39 39 36 7d 0d 0a 25 54 | 43 49 44 41 54 41 7b 4c |996}..%T|CIDATA{L|
|00000230| 61 73 74 52 65 76 69 73 | 65 64 3d 54 68 75 20 46 |astRevis|ed=Thu F|
|00000240| 65 62 20 31 33 20 31 36 | 3a 35 38 3a 30 37 20 31 |eb 13 16|:58:07 1|
|00000250| 39 39 37 7d 0d 0a 25 54 | 43 49 44 41 54 41 7b 4c |997}..%T|CIDATA{L|
|00000260| 61 6e 67 75 61 67 65 3d | 41 6d 65 72 69 63 61 6e |anguage=|American|
|00000270| 20 45 6e 67 6c 69 73 68 | 7d 0d 0a 25 54 43 49 44 | English|}..%TCID|
|00000280| 41 54 41 7b 43 53 54 46 | 69 6c 65 3d 4d 61 74 68 |ATA{CSTF|ile=Math|
|00000290| 48 65 6c 70 2e 63 73 74 | 7d 0d 0a 25 54 43 49 44 |Help.cst|}..%TCID|
|000002a0| 41 54 41 7b 3c 4c 49 4e | 4b 20 52 45 4c 3d 22 62 |ATA{<LIN|K REL="b|
|000002b0| 65 67 69 6e 22 20 48 52 | 45 46 3d 22 44 4d 31 32 |egin" HR|EF="DM12|
|000002c0| 2d 31 2e 74 65 78 22 3e | 7d 0d 0a 25 54 43 49 44 |-1.tex">|}..%TCID|
|000002d0| 41 54 41 7b 3c 4c 49 4e | 4b 20 52 45 4c 3d 22 63 |ATA{<LIN|K REL="c|
|000002e0| 6f 6e 74 65 6e 74 73 22 | 20 48 52 45 46 3d 22 44 |ontents"| HREF="D|
|000002f0| 4d 30 2d 30 2e 74 65 78 | 22 3e 7d 0d 0a 25 54 43 |M0-0.tex|">}..%TC|
|00000300| 49 44 41 54 41 7b 3c 4c | 49 4e 4b 20 52 45 4c 3d |IDATA{<L|INK REL=|
|00000310| 22 65 6e 64 22 20 48 52 | 45 46 3d 22 44 4d 31 32 |"end" HR|EF="DM12|
|00000320| 2d 36 2e 74 65 78 22 3e | 7d 0d 0a 25 54 43 49 44 |-6.tex">|}..%TCID|
|00000330| 41 54 41 7b 3c 4c 49 4e | 4b 20 52 45 4c 3d 22 6e |ATA{<LIN|K REL="n|
|00000340| 65 78 74 22 20 48 52 45 | 46 3d 22 44 4d 31 32 2d |ext" HRE|F="DM12-|
|00000350| 35 2e 74 65 78 22 3e 7d | 0d 0a 25 54 43 49 44 41 |5.tex">}|..%TCIDA|
|00000360| 54 41 7b 3c 4c 49 4e 4b | 20 52 45 4c 3d 22 70 61 |TA{<LINK| REL="pa|
|00000370| 72 65 6e 74 22 20 48 52 | 45 46 3d 22 44 4d 31 32 |rent" HR|EF="DM12|
|00000380| 2e 74 65 78 22 3e 7d 0d | 0a 25 54 43 49 44 41 54 |.tex">}.|.%TCIDAT|
|00000390| 41 7b 3c 4c 49 4e 4b 20 | 52 45 4c 3d 22 70 72 65 |A{<LINK |REL="pre|
|000003a0| 76 69 6f 75 73 22 20 48 | 52 45 46 3d 22 44 4d 31 |vious" H|REF="DM1|
|000003b0| 32 2d 33 2e 74 65 78 22 | 3e 7d 0d 0a 25 54 43 49 |2-3.tex"|>}..%TCI|
|000003c0| 44 41 54 41 7b 3c 4c 49 | 4e 4b 20 52 45 4c 3d 22 |DATA{<LI|NK REL="|
|000003d0| 74 6f 70 22 20 48 52 45 | 46 3d 22 44 4d 30 2d 30 |top" HRE|F="DM0-0|
|000003e0| 2e 74 65 78 22 3e 7d 0d | 0a 0d 0a 5c 69 6e 70 75 |.tex">}.|...\inpu|
|000003f0| 74 7b 74 63 69 6c 61 74 | 65 78 7d 0d 0a 5c 62 65 |t{tcilat|ex}..\be|
|00000400| 67 69 6e 7b 64 6f 63 75 | 6d 65 6e 74 7d 0d 0a 0d |gin{docu|ment}...|
|00000410| 0a 0d 0a 5c 73 65 63 74 | 69 6f 6e 7b 5c 6c 61 62 |...\sect|ion{\lab|
|00000420| 65 6c 7b 50 6f 6c 79 6e | 6f 6d 69 61 6c 73 20 6d |el{Polyn|omials m|
|00000430| 6f 64 75 6c 6f 20 70 6f | 6c 79 6e 6f 6d 69 61 6c |odulo po|lynomial|
|00000440| 73 7d 50 6f 6c 79 6e 6f | 6d 69 61 6c 73 20 4d 6f |s}Polyno|mials Mo|
|00000450| 64 75 6c 6f 20 50 6f 6c | 79 6e 6f 6d 69 61 6c 73 |dulo Pol|ynomials|
|00000460| 0d 0a 7d 0d 0a 0d 0a 54 | 77 6f 20 70 6f 6c 79 6e |..}....T|wo polyn|
|00000470| 6f 6d 69 61 6c 73 20 0d | 0a 5c 69 6e 64 65 78 7b |omials .|.\index{|
|00000480| 50 6f 6c 79 6e 6f 6d 69 | 61 6c 73 40 50 6f 6c 79 |Polynomi|als@Poly|
|00000490| 6e 6f 6d 69 61 6c 73 21 | 6d 6f 64 75 6c 6f 20 70 |nomials!|modulo p|
|000004a0| 6f 6c 79 6e 6f 6d 69 61 | 6c 73 40 6d 6f 64 75 6c |olynomia|ls@modul|
|000004b0| 6f 20 70 6f 6c 79 6e 6f | 6d 69 61 6c 73 7d 24 66 |o polyno|mials}$f|
|000004c0| 28 78 29 24 0d 0a 61 6e | 64 20 24 67 28 78 29 24 |(x)$..an|d $g(x)$|
|000004d0| 20 61 72 65 20 0d 0a 5c | 69 6e 64 65 78 7b 43 6f | are ..\|index{Co|
|000004e0| 6e 67 72 75 65 6e 63 65 | 40 43 6f 6e 67 72 75 65 |ngruence|@Congrue|
|000004f0| 6e 63 65 21 6d 6f 64 20 | 71 28 78 29 40 6d 6f 64 |nce!mod |q(x)@mod|
|00000500| 20 71 28 78 29 7d 5c 74 | 65 78 74 73 6c 7b 63 6f | q(x)}\t|extsl{co|
|00000510| 6e 67 72 75 65 6e 74 20 | 6d 6f 64 75 6c 6f 20 61 |ngruent |modulo a|
|00000520| 0d 0a 70 6f 6c 79 6e 6f | 6d 69 61 6c 7d 20 5c 6c |..polyno|mial} \l|
|00000530| 61 62 65 6c 7b 43 6f 6e | 67 72 75 65 6e 63 65 2c |abel{Con|gruence,|
|00000540| 20 6d 6f 64 75 6c 6f 20 | 70 6f 6c 79 6e 6f 6d 69 | modulo |polynomi|
|00000550| 61 6c 73 7d 24 71 28 78 | 29 24 20 69 66 20 61 6e |als}$q(x|)$ if an|
|00000560| 64 20 6f 6e 6c 79 20 69 | 66 20 24 25 0d 0a 66 28 |d only i|f $%..f(|
|00000570| 78 29 2d 67 28 78 29 24 | 20 69 73 20 61 20 6d 75 |x)-g(x)$| is a mu|
|00000580| 6c 74 69 70 6c 65 20 6f | 66 20 24 71 28 78 29 24 |ltiple o|f $q(x)$|
|00000590| 2c 20 69 6e 20 77 68 69 | 63 68 20 63 61 73 65 20 |, in whi|ch case |
|000005a0| 77 65 20 77 72 69 74 65 | 20 0d 0a 5c 5b 0d 0a 66 |we write| ..\[..f|
|000005b0| 28 78 29 5c 65 71 75 69 | 76 20 67 28 78 29 5c 3b |(x)\equi|v g(x)\;|
|000005c0| 5c 6c 65 66 74 28 20 0d | 0a 5c 6c 69 6d 66 75 6e |\left( .|.\limfun|
|000005d0| 63 7b 6d 6f 64 7d 71 28 | 78 29 5c 72 69 67 68 74 |c{mod}q(|x)\right|
|000005e0| 29 20 0d 0a 5c 5d 0d 0a | 57 65 20 77 72 69 74 65 |) ..\]..|We write|
|000005f0| 20 0d 0a 5c 5b 0d 0a 67 | 28 78 29 5c 6c 69 6d 66 | ..\[..g|(x)\limf|
|00000600| 75 6e 63 7b 6d 6f 64 7d | 71 28 78 29 3d 68 28 78 |unc{mod}|q(x)=h(x|
|00000610| 29 20 0d 0a 5c 5d 0d 0a | 69 66 20 24 68 28 78 29 |) ..\]..|if $h(x)|
|00000620| 24 20 69 73 20 61 20 70 | 6f 6c 79 6e 6f 6d 69 61 |$ is a p|olynomia|
|00000630| 6c 20 6f 66 20 6d 69 6e | 69 6d 61 6c 20 64 65 67 |l of min|imal deg|
|00000640| 72 65 65 20 74 68 61 74 | 20 69 73 20 63 6f 6e 67 |ree that| is cong|
|00000650| 72 75 65 6e 74 20 74 6f | 20 24 67 28 78 29 24 0d |ruent to| $g(x)$.|
|00000660| 0a 6d 6f 64 75 6c 6f 20 | 24 71 28 78 29 24 2e 5c |.modulo |$q(x)$.\|
|00000670| 6d 65 64 73 6b 69 70 0d | 0a 0d 0a 5c 62 65 67 69 |medskip.|...\begi|
|00000680| 6e 7b 71 75 6f 74 65 7d | 0d 0a 24 5c 62 6c 61 63 |n{quote}|..$\blac|
|00000690| 6b 74 72 69 61 6e 67 6c | 65 72 69 67 68 74 20 24 |ktriangl|eright $|
|000006a0| 20 5c 74 65 78 74 73 66 | 7b 45 76 61 6c 75 61 74 | \textsf|{Evaluat|
|000006b0| 65 7d 0d 0a 5c 65 6e 64 | 7b 71 75 6f 74 65 7d 0d |e}..\end|{quote}.|
|000006c0| 0a 0d 0a 5c 62 65 67 69 | 6e 7b 71 75 6f 74 61 74 |...\begi|n{quotat|
|000006d0| 69 6f 6e 7d 0d 0a 24 78 | 5e 7b 34 7d 2b 78 2b 31 |ion}..$x|^{4}+x+1|
|000006e0| 5c 6c 69 6d 66 75 6e 63 | 7b 6d 6f 64 7d 5c 6c 65 |\limfunc|{mod}\le|
|000006f0| 66 74 28 20 78 5e 7b 32 | 7d 2b 34 78 2b 35 5c 72 |ft( x^{2|}+4x+5\r|
|00000700| 69 67 68 74 29 20 3d 5c | 61 6c 6c 6f 77 62 72 65 |ight) =\|allowbre|
|00000710| 61 6b 20 2d 32 33 78 2d | 35 34 5c 6d 65 64 73 6b |ak -23x-|54\medsk|
|00000720| 69 70 20 0d 0a 24 0d 0a | 5c 65 6e 64 7b 71 75 6f |ip ..$..|\end{quo|
|00000730| 74 61 74 69 6f 6e 7d 0d | 0a 0d 0a 54 6f 20 76 65 |tation}.|...To ve|
|00000740| 72 69 66 79 20 74 68 69 | 73 20 63 61 6c 63 75 6c |rify thi|s calcul|
|00000750| 61 74 69 6f 6e 2c 20 6e | 6f 74 65 20 74 68 65 20 |ation, n|ote the |
|00000760| 66 6f 6c 6c 6f 77 69 6e | 67 2e 5c 6d 65 64 73 6b |followin|g.\medsk|
|00000770| 69 70 0d 0a 0d 0a 5c 62 | 65 67 69 6e 7b 71 75 6f |ip....\b|egin{quo|
|00000780| 74 65 7d 0d 0a 24 5c 62 | 6c 61 63 6b 74 72 69 61 |te}..$\b|lacktria|
|00000790| 6e 67 6c 65 72 69 67 68 | 74 20 24 20 5c 74 65 78 |nglerigh|t $ \tex|
|000007a0| 74 73 66 7b 50 6f 6c 79 | 6e 6f 6d 69 61 6c 73 20 |tsf{Poly|nomials |
|000007b0| 2b 20 44 69 76 69 64 65 | 7d 0d 0a 5c 65 6e 64 7b |+ Divide|}..\end{|
|000007c0| 71 75 6f 74 65 7d 0d 0a | 0d 0a 5c 62 65 67 69 6e |quote}..|..\begin|
|000007d0| 7b 71 75 6f 74 61 74 69 | 6f 6e 7d 0d 0a 24 5c 64 |{quotati|on}..$\d|
|000007e0| 66 72 61 63 7b 78 5e 7b | 34 7d 2b 78 2b 31 7d 7b |frac{x^{|4}+x+1}{|
|000007f0| 78 5e 7b 32 7d 2b 34 78 | 2b 35 7d 3d 5c 2c 78 5e |x^{2}+4x|+5}=\,x^|
|00000800| 7b 32 7d 2d 34 78 2b 31 | 31 2b 5c 64 66 72 61 63 |{2}-4x+1|1+\dfrac|
|00000810| 7b 2d 32 33 78 2d 35 34 | 7d 7b 78 5e 7b 32 7d 2b |{-23x-54|}{x^{2}+|
|00000820| 34 78 2b 35 7d 25 0d 0a | 5c 6d 65 64 73 6b 69 70 |4x+5}%..|\medskip|
|00000830| 20 24 0d 0a 5c 65 6e 64 | 7b 71 75 6f 74 61 74 69 | $..\end|{quotati|
|00000840| 6f 6e 7d 0d 0a 0d 0a 54 | 68 69 73 20 72 65 73 75 |on}....T|his resu|
|00000850| 6c 74 20 69 6d 70 6c 69 | 65 73 20 74 68 61 74 20 |lt impli|es that |
|00000860| 69 6e 64 65 65 64 20 24 | 78 5e 7b 34 7d 2b 78 2b |indeed $|x^{4}+x+|
|00000870| 31 5c 6c 69 6d 66 75 6e | 63 7b 6d 6f 64 7d 5c 6c |1\limfun|c{mod}\l|
|00000880| 65 66 74 28 0d 0a 78 5e | 7b 32 7d 2b 34 78 2b 35 |eft(..x^|{2}+4x+5|
|00000890| 5c 72 69 67 68 74 29 20 | 3d 2d 32 33 78 2d 35 34 |\right) |=-23x-54|
|000008a0| 24 2e 5c 62 69 67 73 6b | 69 70 0d 0a 0d 0a 5c 73 |$.\bigsk|ip....\s|
|000008b0| 75 62 73 65 63 74 69 6f | 6e 7b 5c 20 0d 0a 5c 69 |ubsectio|n{\ ..\i|
|000008c0| 6e 64 65 78 7b 50 6f 6c | 79 6e 6f 6d 69 61 6c 73 |ndex{Pol|ynomials|
|000008d0| 40 50 6f 6c 79 6e 6f 6d | 69 61 6c 73 21 67 72 65 |@Polynom|ials!gre|
|000008e0| 61 74 65 73 74 20 63 6f | 6d 6d 6f 6e 20 64 69 76 |atest co|mmon div|
|000008f0| 69 73 6f 72 40 67 72 65 | 61 74 65 73 74 20 63 6f |isor@gre|atest co|
|00000900| 6d 6d 6f 6e 20 64 69 76 | 69 73 6f 72 7d 25 0d 0a |mmon div|isor}%..|
|00000910| 5c 6c 61 62 65 6c 7b 67 | 63 64 2c 20 70 6f 6c 79 |\label{g|cd, poly|
|00000920| 6e 6f 6d 69 61 6c 73 7d | 47 72 65 61 74 65 73 74 |nomials}|Greatest|
|00000930| 20 43 6f 6d 6d 6f 6e 20 | 44 69 76 69 73 6f 72 20 | Common |Divisor |
|00000940| 6f 66 20 50 6f 6c 79 6e | 6f 6d 69 61 6c 73 7d 0d |of Polyn|omials}.|
|00000950| 0a 0d 0a 54 68 65 20 5c | 74 65 78 74 73 6c 7b 67 |...The \|textsl{g|
|00000960| 72 65 61 74 65 73 74 20 | 63 6f 6d 6d 6f 6e 20 64 |reatest |common d|
|00000970| 69 76 69 73 6f 72 20 6f | 66 20 74 77 6f 20 70 6f |ivisor o|f two po|
|00000980| 6c 79 6e 6f 6d 69 61 6c | 73 7d 20 24 70 28 78 29 |lynomial|s} $p(x)|
|00000990| 24 20 61 6e 64 20 24 71 | 28 78 29 24 20 69 73 0d |$ and $q|(x)$ is.|
|000009a0| 0a 61 5c 6c 61 62 65 6c | 7b 50 6f 6c 79 6e 6f 6d |.a\label|{Polynom|
|000009b0| 69 61 6c 73 2c 20 67 72 | 65 61 74 65 73 74 20 63 |ials, gr|eatest c|
|000009c0| 6f 6d 6d 6f 6e 20 64 69 | 76 69 73 6f 72 7d 20 70 |ommon di|visor} p|
|000009d0| 6f 6c 79 6e 6f 6d 69 61 | 6c 20 24 64 28 78 29 24 |olynomia|l $d(x)$|
|000009e0| 20 6f 66 20 68 69 67 68 | 65 73 74 0d 0a 64 65 67 | of high|est..deg|
|000009f0| 72 65 65 20 74 68 61 74 | 20 64 69 76 69 64 65 73 |ree that| divides|
|00000a00| 20 62 6f 74 68 20 24 70 | 28 78 29 24 20 61 6e 64 | both $p|(x)$ and|
|00000a10| 20 24 71 28 78 29 24 2e | 0d 0a 0d 0a 44 65 66 69 | $q(x)$.|....Defi|
|00000a20| 6e 65 20 24 70 28 78 29 | 3d 31 38 78 5e 7b 37 7d |ne $p(x)|=18x^{7}|
|00000a30| 2d 39 78 5e 7b 35 7d 2b | 33 36 78 5e 7b 34 7d 2b |-9x^{5}+|36x^{4}+|
|00000a40| 34 78 5e 7b 33 7d 2d 31 | 36 78 5e 7b 32 7d 2b 31 |4x^{3}-1|6x^{2}+1|
|00000a50| 39 78 2b 31 32 24 20 61 | 6e 64 20 24 25 0d 0a 71 |9x+12$ a|nd $%..q|
|00000a60| 28 78 29 3d 31 35 78 5e | 7b 35 7d 2d 39 78 5e 7b |(x)=15x^|{5}-9x^{|
|00000a70| 34 7d 2b 31 31 78 5e 7b | 33 7d 2b 31 37 78 5e 7b |4}+11x^{|3}+17x^{|
|00000a80| 32 7d 2d 31 30 78 2b 38 | 24 2c 20 74 68 65 6e 20 |2}-10x+8|$, then |
|00000a90| 75 73 65 20 5c 74 65 78 | 74 73 66 7b 45 76 61 6c |use \tex|tsf{Eval|
|00000aa0| 75 61 74 65 7d 20 74 6f | 0d 0a 63 61 6c 63 75 6c |uate} to|..calcul|
|00000ab0| 61 74 65 20 24 5c 67 63 | 64 20 5c 6c 65 66 74 28 |ate $\gc|d \left(|
|00000ac0| 20 70 28 78 29 2c 71 28 | 78 29 5c 72 69 67 68 74 | p(x),q(|x)\right|
|00000ad0| 29 20 2e 5c 6d 65 64 73 | 6b 69 70 20 24 0d 0a 0d |) .\meds|kip $...|
|00000ae0| 0a 5c 62 65 67 69 6e 7b | 71 75 6f 74 65 7d 0d 0a |.\begin{|quote}..|
|00000af0| 24 5c 62 6c 61 63 6b 74 | 72 69 61 6e 67 6c 65 72 |$\blackt|riangler|
|00000b00| 69 67 68 74 20 24 20 5c | 74 65 78 74 73 66 7b 45 |ight $ \|textsf{E|
|00000b10| 76 61 6c 75 61 74 65 7d | 0d 0a 5c 65 6e 64 7b 71 |valuate}|..\end{q|
|00000b20| 75 6f 74 65 7d 0d 0a 0d | 0a 5c 62 65 67 69 6e 7b |uote}...|.\begin{|
|00000b30| 71 75 6f 74 61 74 69 6f | 6e 7d 0d 0a 24 5c 67 63 |quotatio|n}..$\gc|
|00000b40| 64 20 5c 6c 65 66 74 28 | 20 70 28 78 29 2c 71 28 |d \left(| p(x),q(|
|00000b50| 78 29 5c 72 69 67 68 74 | 29 20 3d 5c 61 6c 6c 6f |x)\right|) =\allo|
|00000b60| 77 62 72 65 61 6b 20 33 | 78 5e 7b 33 7d 2b 78 2b |wbreak 3|x^{3}+x+|
|00000b70| 34 5c 6d 65 64 73 6b 69 | 70 20 24 0d 0a 5c 65 6e |4\medski|p $..\en|
|00000b80| 64 7b 71 75 6f 74 61 74 | 69 6f 6e 7d 0d 0a 0d 0a |d{quotat|ion}....|
|00000b90| 55 73 65 20 74 68 65 20 | 66 6f 6c 6c 6f 77 69 6e |Use the |followin|
|00000ba0| 67 20 74 6f 20 76 65 72 | 69 66 79 20 74 68 61 74 |g to ver|ify that|
|00000bb0| 20 24 33 78 5e 33 2b 78 | 2b 34 24 20 69 73 20 69 | $3x^3+x|+4$ is i|
|00000bc0| 6e 64 65 65 64 20 61 20 | 63 6f 6d 6d 6f 6e 0d 0a |ndeed a |common..|
|00000bd0| 64 69 76 69 73 6f 72 2e | 5c 6d 65 64 73 6b 69 70 |divisor.|\medskip|
|00000be0| 0d 0a 0d 0a 5c 62 65 67 | 69 6e 7b 71 75 6f 74 65 |....\beg|in{quote|
|00000bf0| 7d 0d 0a 24 5c 62 6c 61 | 63 6b 74 72 69 61 6e 67 |}..$\bla|cktriang|
|00000c00| 6c 65 72 69 67 68 74 20 | 24 20 5c 74 65 78 74 73 |leright |$ \texts|
|00000c10| 66 7b 50 6f 6c 79 6e 6f | 6d 69 61 6c 73 20 2b 20 |f{Polyno|mials + |
|00000c20| 44 69 76 69 64 65 7d 0d | 0a 5c 65 6e 64 7b 71 75 |Divide}.|.\end{qu|
|00000c30| 6f 74 65 7d 0d 0a 0d 0a | 5c 62 65 67 69 6e 7b 71 |ote}....|\begin{q|
|00000c40| 75 6f 74 61 74 69 6f 6e | 7d 0d 0a 24 25 0d 0a 5c |uotation|}..$%..\|
|00000c50| 64 66 72 61 63 7b 31 38 | 78 5e 7b 37 7d 2d 39 78 |dfrac{18|x^{7}-9x|
|00000c60| 5e 7b 35 7d 2b 33 36 78 | 5e 7b 34 7d 2d 35 78 5e |^{5}+36x|^{4}-5x^|
|00000c70| 7b 33 7d 2d 31 36 78 5e | 7b 32 7d 2b 31 36 78 7d |{3}-16x^|{2}+16x}|
|00000c80| 7b 33 78 5e 7b 33 7d 2b | 78 2b 34 7d 25 0d 0a 3d |{3x^{3}+|x+4}%..=|
|00000c90| 36 78 5e 7b 34 7d 2d 35 | 78 5e 7b 32 7d 2b 34 78 |6x^{4}-5|x^{2}+4x|
|00000ca0| 5c 6d 65 64 73 6b 69 70 | 20 24 0d 0a 0d 0a 24 5c |\medskip| $....$\|
|00000cb0| 64 66 72 61 63 7b 31 35 | 78 5e 7b 35 7d 2d 39 78 |dfrac{15|x^{5}-9x|
|00000cc0| 5e 7b 34 7d 2b 31 31 78 | 5e 7b 33 7d 2b 31 37 78 |^{4}+11x|^{3}+17x|
|00000cd0| 5e 7b 32 7d 2d 31 30 78 | 2b 38 7d 7b 33 78 5e 7b |^{2}-10x|+8}{3x^{|
|00000ce0| 33 7d 2b 78 2b 34 7d 3d | 35 78 5e 7b 32 7d 2d 33 |3}+x+4}=|5x^{2}-3|
|00000cf0| 78 2b 32 25 0d 0a 5c 6d | 65 64 73 6b 69 70 20 24 |x+2%..\m|edskip $|
|00000d00| 0d 0a 5c 65 6e 64 7b 71 | 75 6f 74 61 74 69 6f 6e |..\end{q|uotation|
|00000d10| 7d 0d 0a 0d 0a 54 68 75 | 73 2c 20 0d 0a 5c 5b 0d |}....Thu|s, ..\[.|
|00000d20| 0a 70 28 78 29 3d 5c 6c | 65 66 74 28 20 36 78 5e |.p(x)=\l|eft( 6x^|
|00000d30| 34 2d 35 78 5e 32 2b 34 | 78 2b 33 5c 72 69 67 68 |4-5x^2+4|x+3\righ|
|00000d40| 74 29 20 5c 6c 65 66 74 | 28 20 33 78 5e 33 2b 78 |t) \left|( 3x^3+x|
|00000d50| 2b 34 5c 72 69 67 68 74 | 29 20 0d 0a 5c 5d 0d 0a |+4\right|) ..\]..|
|00000d60| 61 6e 64 20 0d 0a 5c 5b | 0d 0a 71 28 78 29 3d 5c |and ..\[|..q(x)=\|
|00000d70| 6c 65 66 74 28 20 35 78 | 5e 32 2d 33 78 2b 32 5c |left( 5x|^2-3x+2\|
|00000d80| 72 69 67 68 74 29 20 5c | 6c 65 66 74 28 20 33 78 |right) \|left( 3x|
|00000d90| 5e 33 2b 78 2b 34 5c 72 | 69 67 68 74 29 20 0d 0a |^3+x+4\r|ight) ..|
|00000da0| 5c 5d 0d 0a 0d 0a 5c 73 | 75 62 73 65 63 74 69 6f |\]....\s|ubsectio|
|00000db0| 6e 7b 5c 20 5c 6c 61 62 | 65 6c 7b 4d 75 6c 74 69 |n{\ \lab|el{Multi|
|00000dc0| 70 6c 65 20 72 6f 6f 74 | 73 7d 4d 75 6c 74 69 70 |ple root|s}Multip|
|00000dd0| 6c 69 63 69 74 79 20 6f | 66 20 52 6f 6f 74 73 20 |licity o|f Roots |
|00000de0| 6f 66 20 50 6f 6c 79 6e | 6f 6d 69 61 6c 73 7d 0d |of Polyn|omials}.|
|00000df0| 0a 0d 0a 41 20 72 6f 6f | 74 20 24 61 24 20 6f 66 |...A roo|t $a$ of|
|00000e00| 20 61 20 70 6f 6c 79 6e | 6f 6d 69 61 6c 20 0d 0a | a polyn|omial ..|
|00000e10| 5c 69 6e 64 65 78 7b 50 | 6f 6c 79 6e 6f 6d 69 61 |\index{P|olynomia|
|00000e20| 6c 73 40 50 6f 6c 79 6e | 6f 6d 69 61 6c 73 21 6d |ls@Polyn|omials!m|
|00000e30| 75 6c 74 69 70 6c 65 20 | 72 6f 6f 74 73 40 6d 75 |ultiple |roots@mu|
|00000e40| 6c 74 69 70 6c 65 20 72 | 6f 6f 74 73 7d 20 5c 6c |ltiple r|oots} \l|
|00000e50| 61 62 65 6c 25 0d 0a 7b | 50 6f 6c 79 6e 6f 6d 69 |abel%..{|Polynomi|
|00000e60| 61 6c 73 2c 20 72 6f 6f | 74 73 20 28 32 29 7d 24 |als, roo|ts (2)}$|
|00000e70| 66 28 78 29 24 20 68 61 | 73 20 0d 0a 5c 69 6e 64 |f(x)$ ha|s ..\ind|
|00000e80| 65 78 7b 52 6f 6f 74 73 | 40 52 6f 6f 74 73 21 6d |ex{Roots|@Roots!m|
|00000e90| 75 6c 74 69 70 6c 69 63 | 69 74 79 40 6d 75 6c 74 |ultiplic|ity@mult|
|00000ea0| 69 70 6c 69 63 69 74 79 | 7d 5c 74 65 78 74 73 6c |iplicity|}\textsl|
|00000eb0| 7b 6d 75 6c 74 69 70 6c | 69 63 69 74 79 7d 20 24 |{multipl|icity} $|
|00000ec0| 6b 24 20 69 66 20 24 25 | 0d 0a 66 28 78 29 3d 28 |k$ if $%|..f(x)=(|
|00000ed0| 78 2d 61 29 5e 7b 6b 7d | 67 28 78 29 24 2c 20 77 |x-a)^{k}|g(x)$, w|
|00000ee0| 68 65 72 65 20 24 67 28 | 61 29 5c 6e 65 71 20 30 |here $g(|a)\neq 0|
|00000ef0| 24 2e 20 49 66 20 24 6b | 3e 31 24 2c 20 74 68 65 |$. If $k|>1$, the|
|00000f00| 6e 20 24 66 5e 7b 5c 70 | 72 69 6d 65 0d 0a 7d 28 |n $f^{\p|rime..}(|
|00000f10| 78 29 3d 6b 28 78 2d 61 | 29 5e 7b 6b 2d 31 7d 67 |x)=k(x-a|)^{k-1}g|
|00000f20| 28 78 29 2b 28 78 2d 61 | 29 5e 7b 6b 7d 67 5e 7b |(x)+(x-a|)^{k}g^{|
|00000f30| 5c 70 72 69 6d 65 0d 0a | 7d 28 78 29 3d 28 78 2d |\prime..|}(x)=(x-|
|00000f40| 61 29 5e 7b 6b 2d 31 7d | 28 6b 67 28 78 29 2b 28 |a)^{k-1}|(kg(x)+(|
|00000f50| 78 2d 61 29 67 5e 7b 5c | 70 72 69 6d 65 20 7d 28 |x-a)g^{\|prime }(|
|00000f60| 78 29 29 24 2c 20 61 6e | 64 20 68 65 6e 63 65 20 |x))$, an|d hence |
|00000f70| 24 5c 67 63 64 0d 0a 28 | 66 28 78 29 2c 66 5e 7b |$\gcd..(|f(x),f^{|
|00000f80| 5c 70 72 69 6d 65 20 7d | 28 78 29 29 3d 28 78 2d |\prime }|(x))=(x-|
|00000f90| 61 29 5e 7b 6b 2d 31 7d | 68 28 78 29 5c 6e 65 71 |a)^{k-1}|h(x)\neq|
|00000fa0| 20 31 24 2e 20 54 68 69 | 73 20 6f 62 73 65 72 76 | 1$. Thi|s observ|
|00000fb0| 61 74 69 6f 6e 20 70 72 | 6f 76 69 64 65 73 20 61 |ation pr|ovides a|
|00000fc0| 0d 0a 74 65 73 74 20 66 | 6f 72 20 6d 75 6c 74 69 |..test f|or multi|
|00000fd0| 70 6c 65 20 72 6f 6f 74 | 73 3a 20 49 66 20 24 5c |ple root|s: If $\|
|00000fe0| 67 63 64 20 5c 6c 65 66 | 74 28 20 66 28 78 29 2c |gcd \lef|t( f(x),|
|00000ff0| 66 5e 7b 5c 70 72 69 6d | 65 20 7d 28 78 29 5c 72 |f^{\prim|e }(x)\r|
|00001000| 69 67 68 74 29 20 24 20 | 69 73 20 61 0d 0a 63 6f |ight) $ |is a..co|
|00001010| 6e 73 74 61 6e 74 2c 20 | 74 68 65 6e 20 24 66 28 |nstant, |then $f(|
|00001020| 78 29 24 20 68 61 73 20 | 6e 6f 20 0d 0a 5c 69 6e |x)$ has |no ..\in|
|00001030| 64 65 78 7b 4d 75 6c 74 | 69 70 6c 65 20 72 6f 6f |dex{Mult|iple roo|
|00001040| 74 73 40 4d 75 6c 74 69 | 70 6c 65 20 72 6f 6f 74 |ts@Multi|ple root|
|00001050| 73 7d 6d 75 6c 74 69 70 | 6c 65 20 72 6f 6f 74 73 |s}multip|le roots|
|00001060| 3b 20 6f 74 68 65 72 77 | 69 73 65 2c 20 24 66 28 |; otherw|ise, $f(|
|00001070| 78 29 24 20 68 61 73 0d | 0a 61 74 20 6c 65 61 73 |x)$ has.|.at leas|
|00001080| 74 20 6f 6e 65 20 6d 75 | 6c 74 69 70 6c 65 20 72 |t one mu|ltiple r|
|00001090| 6f 6f 74 2e 0d 0a 0d 0a | 54 68 65 20 67 72 61 70 |oot.....|The grap|
|000010a0| 68 73 20 6f 66 20 0d 0a | 5c 5b 0d 0a 66 28 78 29 |hs of ..|\[..f(x)|
|000010b0| 3d 35 35 33 37 78 5e 7b | 35 7d 2d 33 34 38 30 34 |=5537x^{|5}-34804|
|000010c0| 78 5e 7b 34 7d 2b 36 30 | 32 32 39 78 5e 7b 33 7d |x^{4}+60|229x^{3}|
|000010d0| 2d 32 39 32 36 37 78 5e | 7b 32 7d 2b 31 39 38 38 |-29267x^|{2}+1988|
|000010e0| 38 78 2b 35 34 36 39 32 | 20 0d 0a 5c 5d 0d 0a 61 |8x+54692| ..\]..a|
|000010f0| 6e 64 20 0d 0a 5c 5b 0d | 0a 67 28 78 29 3d 35 35 |nd ..\[.|.g(x)=55|
|00001100| 33 37 78 5e 7b 35 7d 2d | 33 34 37 39 37 78 5e 7b |37x^{5}-|34797x^{|
|00001110| 34 7d 2b 36 30 32 30 37 | 78 5e 7b 33 7d 2d 32 39 |4}+60207|x^{3}-29|
|00001120| 32 36 30 78 5e 7b 32 7d | 2b 31 39 38 37 33 78 2b |260x^{2}|+19873x+|
|00001130| 35 34 36 37 30 20 0d 0a | 5c 5d 0d 0a 61 70 70 65 |54670 ..|\]..appe|
|00001140| 61 72 20 69 6e 64 69 73 | 74 69 6e 67 75 69 73 68 |ar indis|tinguish|
|00001150| 61 62 6c 65 2e 20 42 6f | 74 68 20 61 70 70 65 61 |able. Bo|th appea|
|00001160| 72 20 74 6f 20 68 61 76 | 65 20 61 20 72 6f 6f 74 |r to hav|e a root|
|00001170| 20 6e 65 61 72 20 33 2e | 31 2e 0d 0a 0d 0a 5c 62 | near 3.|1.....\b|
|00001180| 65 67 69 6e 7b 63 65 6e | 74 65 72 7d 0d 0a 5c 46 |egin{cen|ter}..\F|
|00001190| 52 41 4d 45 7b 69 74 62 | 70 46 55 7d 7b 32 2e 31 |RAME{itb|pFU}{2.1|
|000011a0| 35 37 37 69 6e 7d 7b 31 | 2e 37 35 37 33 69 6e 7d |577in}{1|.7573in}|
|000011b0| 7b 30 69 6e 7d 7b 5c 51 | 63 62 7b 24 66 28 78 29 |{0in}{\Q|cb{$f(x)|
|000011c0| 24 7d 7d 7b 7d 7b 7d 7b | 5c 73 70 65 63 69 61 6c |$}}{}{}{|\special|
|000011d0| 7b 6c 61 6e 67 75 61 67 | 65 0d 0a 22 53 63 69 65 |{languag|e.."Scie|
|000011e0| 6e 74 69 66 69 63 20 57 | 6f 72 64 22 3b 74 79 70 |ntific W|ord";typ|
|000011f0| 65 20 22 4d 41 50 4c 45 | 50 4c 4f 54 22 3b 77 69 |e "MAPLE|PLOT";wi|
|00001200| 64 74 68 20 32 2e 31 35 | 37 37 69 6e 3b 68 65 69 |dth 2.15|77in;hei|
|00001210| 67 68 74 20 31 2e 37 35 | 37 33 69 6e 3b 64 65 70 |ght 1.75|73in;dep|
|00001220| 74 68 0d 0a 30 69 6e 3b | 64 69 73 70 6c 61 79 20 |th..0in;|display |
|00001230| 22 50 49 43 54 22 3b 66 | 75 6e 63 74 69 6f 6e 0d |"PICT";f|unction.|
|00001240| 0a 5c 54 45 58 55 58 7b | 24 35 35 33 37 78 5e 7b |.\TEXUX{|$5537x^{|
|00001250| 35 7d 2d 33 34 38 30 34 | 78 5e 7b 34 7d 2b 36 30 |5}-34804|x^{4}+60|
|00001260| 32 32 39 78 5e 7b 33 7d | 2d 32 39 32 36 37 78 5e |229x^{3}|-29267x^|
|00001270| 7b 32 7d 2b 31 39 38 38 | 38 78 2b 35 34 36 39 32 |{2}+1988|8x+54692|
|00001280| 24 7d 3b 6c 69 6e 65 63 | 6f 6c 6f 72 0d 0a 22 72 |$};linec|olor.."r|
|00001290| 65 64 22 3b 6c 69 6e 65 | 73 74 79 6c 65 20 31 3b |ed";line|style 1;|
|000012a0| 6c 69 6e 65 74 68 69 63 | 6b 6e 65 73 73 20 31 3b |linethic|kness 1;|
|000012b0| 70 6f 69 6e 74 73 74 79 | 6c 65 20 22 70 6f 69 6e |pointsty|le "poin|
|000012c0| 74 22 3b 78 6d 69 6e 20 | 22 2d 32 22 3b 78 6d 61 |t";xmin |"-2";xma|
|000012d0| 78 0d 0a 22 34 22 3b 78 | 76 69 65 77 6d 69 6e 20 |x.."4";x|viewmin |
|000012e0| 22 2d 32 2e 31 32 22 3b | 78 76 69 65 77 6d 61 78 |"-2.12";|xviewmax|
|000012f0| 20 22 34 2e 31 32 32 22 | 3b 79 76 69 65 77 6d 69 | "4.122"|;yviewmi|
|00001300| 6e 20 22 30 22 3b 79 76 | 69 65 77 6d 61 78 0d 0a |n "0";yv|iewmax..|
|00001310| 22 31 30 30 30 30 30 22 | 3b 76 69 65 77 73 65 74 |"100000"|;viewset|
|00001320| 22 58 59 22 3b 72 61 6e | 67 65 73 65 74 22 58 22 |"XY";ran|geset"X"|
|00001330| 3b 70 68 69 20 34 35 3b | 74 68 65 74 61 20 34 35 |;phi 45;|theta 45|
|00001340| 3b 70 6c 6f 74 74 79 70 | 65 20 34 3b 6e 75 6d 70 |;plottyp|e 4;nump|
|00001350| 6f 69 6e 74 73 0d 0a 34 | 39 3b 61 78 65 73 73 74 |oints..4|9;axesst|
|00001360| 79 6c 65 20 22 6e 6f 72 | 6d 61 6c 22 3b 78 69 73 |yle "nor|mal";xis|
|00001370| 20 5c 54 45 58 55 58 7b | 78 7d 3b 76 61 72 31 6e | \TEXUX{|x};var1n|
|00001380| 61 6d 65 20 5c 54 45 58 | 55 58 7b 24 78 24 7d 3b |ame \TEX|UX{$x$};|
|00001390| 7d 7d 20 5c 46 52 41 4d | 45 7b 69 74 62 70 46 55 |}} \FRAM|E{itbpFU|
|000013a0| 7d 7b 25 0d 0a 32 2e 31 | 35 37 37 69 6e 7d 7b 31 |}{%..2.1|577in}{1|
|000013b0| 2e 37 35 37 33 69 6e 7d | 7b 30 69 6e 7d 7b 5c 51 |.7573in}|{0in}{\Q|
|000013c0| 63 62 7b 24 67 28 78 29 | 24 7d 7d 7b 7d 7b 7d 7b |cb{$g(x)|$}}{}{}{|
|000013d0| 5c 73 70 65 63 69 61 6c | 7b 6c 61 6e 67 75 61 67 |\special|{languag|
|000013e0| 65 20 22 53 63 69 65 6e | 74 69 66 69 63 0d 0a 57 |e "Scien|tific..W|
|000013f0| 6f 72 64 22 3b 74 79 70 | 65 20 22 4d 41 50 4c 45 |ord";typ|e "MAPLE|
|00001400| 50 4c 4f 54 22 3b 77 69 | 64 74 68 20 32 2e 31 35 |PLOT";wi|dth 2.15|
|00001410| 37 37 69 6e 3b 68 65 69 | 67 68 74 20 31 2e 37 35 |77in;hei|ght 1.75|
|00001420| 37 33 69 6e 3b 64 65 70 | 74 68 20 30 69 6e 3b 64 |73in;dep|th 0in;d|
|00001430| 69 73 70 6c 61 79 0d 0a | 22 50 49 43 54 22 3b 66 |isplay..|"PICT";f|
|00001440| 75 6e 63 74 69 6f 6e 0d | 0a 5c 54 45 58 55 58 7b |unction.|.\TEXUX{|
|00001450| 24 35 35 33 37 78 5e 7b | 35 7d 2d 33 34 37 39 37 |$5537x^{|5}-34797|
|00001460| 78 5e 7b 34 7d 2b 36 30 | 32 30 37 78 5e 7b 33 7d |x^{4}+60|207x^{3}|
|00001470| 2d 32 39 32 36 30 78 5e | 7b 32 7d 2b 31 39 38 37 |-29260x^|{2}+1987|
|00001480| 33 78 2b 35 34 36 37 30 | 24 7d 3b 6c 69 6e 65 63 |3x+54670|$};linec|
|00001490| 6f 6c 6f 72 0d 0a 22 72 | 65 64 22 3b 6c 69 6e 65 |olor.."r|ed";line|
|000014a0| 73 74 79 6c 65 20 31 3b | 6c 69 6e 65 74 68 69 63 |style 1;|linethic|
|000014b0| 6b 6e 65 73 73 20 31 3b | 70 6f 69 6e 74 73 74 79 |kness 1;|pointsty|
|000014c0| 6c 65 20 22 70 6f 69 6e | 74 22 3b 78 6d 69 6e 20 |le "poin|t";xmin |
|000014d0| 22 2d 32 22 3b 78 6d 61 | 78 0d 0a 22 34 22 3b 78 |"-2";xma|x.."4";x|
|000014e0| 76 69 65 77 6d 69 6e 20 | 22 2d 32 2e 31 32 22 3b |viewmin |"-2.12";|
|000014f0| 78 76 69 65 77 6d 61 78 | 20 22 34 2e 31 32 32 22 |xviewmax| "4.122"|
|00001500| 3b 79 76 69 65 77 6d 69 | 6e 20 22 30 22 3b 79 76 |;yviewmi|n "0";yv|
|00001510| 69 65 77 6d 61 78 0d 0a | 22 31 30 30 30 30 30 22 |iewmax..|"100000"|
|00001520| 3b 76 69 65 77 73 65 74 | 22 58 59 22 3b 72 61 6e |;viewset|"XY";ran|
|00001530| 67 65 73 65 74 22 58 22 | 3b 70 68 69 20 34 35 3b |geset"X"|;phi 45;|
|00001540| 74 68 65 74 61 20 34 35 | 3b 70 6c 6f 74 74 79 70 |theta 45|;plottyp|
|00001550| 65 20 34 3b 6e 75 6d 70 | 6f 69 6e 74 73 0d 0a 34 |e 4;nump|oints..4|
|00001560| 39 3b 61 78 65 73 73 74 | 79 6c 65 20 22 6e 6f 72 |9;axesst|yle "nor|
|00001570| 6d 61 6c 22 3b 78 69 73 | 20 5c 54 45 58 55 58 7b |mal";xis| \TEXUX{|
|00001580| 78 7d 3b 76 61 72 31 6e | 61 6d 65 20 5c 54 45 58 |x};var1n|ame \TEX|
|00001590| 55 58 7b 24 78 24 7d 3b | 7d 7d 0d 0a 5c 65 6e 64 |UX{$x$};|}}..\end|
|000015a0| 7b 63 65 6e 74 65 72 7d | 0d 0a 0d 0a 48 6f 77 65 |{center}|....Howe|
|000015b0| 76 65 72 2c 5c 6d 65 64 | 73 6b 69 70 0d 0a 0d 0a |ver,\med|skip....|
|000015c0| 5c 62 65 67 69 6e 7b 71 | 75 6f 74 65 7d 0d 0a 24 |\begin{q|uote}..$|
|000015d0| 5c 62 6c 61 63 6b 74 72 | 69 61 6e 67 6c 65 72 69 |\blacktr|iangleri|
|000015e0| 67 68 74 20 24 20 5c 74 | 65 78 74 73 66 7b 45 76 |ght $ \t|extsf{Ev|
|000015f0| 61 6c 75 61 74 65 7d 0d | 0a 5c 65 6e 64 7b 71 75 |aluate}.|.\end{qu|
|00001600| 6f 74 65 7d 0d 0a 0d 0a | 5c 62 65 67 69 6e 7b 71 |ote}....|\begin{q|
|00001610| 75 6f 74 61 74 69 6f 6e | 7d 0d 0a 24 5c 67 63 64 |uotation|}..$\gcd|
|00001620| 20 28 66 28 78 29 2c 66 | 5e 7b 5c 70 72 69 6d 65 | (f(x),f|^{\prime|
|00001630| 20 7d 28 78 29 29 3d 5c | 2c 37 39 31 78 2d 32 34 | }(x))=\|,791x-24|
|00001640| 38 36 5c 6d 65 64 73 6b | 69 70 20 24 0d 0a 5c 65 |86\medsk|ip $..\e|
|00001650| 6e 64 7b 71 75 6f 74 61 | 74 69 6f 6e 7d 0d 0a 0d |nd{quota|tion}...|
|00001660| 0a 77 68 65 72 65 61 73 | 5c 6d 65 64 73 6b 69 70 |.whereas|\medskip|
|00001670| 0d 0a 0d 0a 5c 62 65 67 | 69 6e 7b 71 75 6f 74 65 |....\beg|in{quote|
|00001680| 7d 0d 0a 24 5c 62 6c 61 | 63 6b 74 72 69 61 6e 67 |}..$\bla|cktriang|
|00001690| 6c 65 72 69 67 68 74 20 | 24 20 5c 74 65 78 74 73 |leright |$ \texts|
|000016a0| 66 7b 45 76 61 6c 75 61 | 74 65 7d 0d 0a 5c 65 6e |f{Evalua|te}..\en|
|000016b0| 64 7b 71 75 6f 74 65 7d | 0d 0a 0d 0a 5c 62 65 67 |d{quote}|....\beg|
|000016c0| 69 6e 7b 71 75 6f 74 61 | 74 69 6f 6e 7d 0d 0a 24 |in{quota|tion}..$|
|000016d0| 5c 67 63 64 20 28 67 28 | 78 29 2c 67 5e 7b 5c 70 |\gcd (g(|x),g^{\p|
|000016e0| 72 69 6d 65 20 7d 28 78 | 29 29 3d 5c 2c 37 5c 6d |rime }(x|))=\,7\m|
|000016f0| 65 64 73 6b 69 70 20 24 | 0d 0a 5c 65 6e 64 7b 71 |edskip $|..\end{q|
|00001700| 75 6f 74 61 74 69 6f 6e | 7d 0d 0a 0d 0a 54 68 75 |uotation|}....Thu|
|00001710| 73 2c 20 24 78 3d 32 34 | 38 36 2f 37 39 31 3d 32 |s, $x=24|86/791=2|
|00001720| 32 2f 37 24 20 69 73 20 | 61 20 72 6f 6f 74 20 6f |2/7$ is |a root o|
|00001730| 66 20 24 66 28 78 29 24 | 20 6f 66 20 6d 75 6c 74 |f $f(x)$| of mult|
|00001740| 69 70 6c 69 63 69 74 79 | 20 61 74 20 6c 65 61 73 |iplicity| at leas|
|00001750| 74 20 24 32 24 2c 0d 0a | 77 68 65 72 65 61 73 20 |t $2$,..|whereas |
|00001760| 24 67 28 78 29 24 20 68 | 61 73 20 6e 6f 20 6d 75 |$g(x)$ h|as no mu|
|00001770| 6c 74 69 70 6c 65 20 72 | 6f 6f 74 73 2e 20 53 6f |ltiple r|oots. So|
|00001780| 6c 76 69 6e 67 20 24 66 | 28 78 29 3d 30 24 20 61 |lving $f|(x)=0$ a|
|00001790| 6e 64 20 24 67 28 78 29 | 3d 30 24 2c 20 74 68 65 |nd $g(x)|=0$, the|
|000017a0| 0d 0a 72 65 61 6c 20 73 | 6f 6c 75 74 69 6f 6e 73 |..real s|olutions|
|000017b0| 20 61 72 65 20 61 73 20 | 66 6f 6c 6c 6f 77 73 2e | are as |follows.|
|000017c0| 5c 6d 65 64 73 6b 69 70 | 0d 0a 0d 0a 5c 62 65 67 |\medskip|....\beg|
|000017d0| 69 6e 7b 71 75 6f 74 65 | 7d 0d 0a 24 5c 62 6c 61 |in{quote|}..$\bla|
|000017e0| 63 6b 74 72 69 61 6e 67 | 6c 65 72 69 67 68 74 20 |cktriang|leright |
|000017f0| 24 20 5c 74 65 78 74 73 | 66 7b 53 6f 6c 76 65 20 |$ \texts|f{Solve |
|00001800| 2b 20 45 78 61 63 74 7d | 0d 0a 5c 65 6e 64 7b 71 |+ Exact}|..\end{q|
|00001810| 75 6f 74 65 7d 0d 0a 0d | 0a 5c 62 65 67 69 6e 7b |uote}...|.\begin{|
|00001820| 71 75 6f 74 61 74 69 6f | 6e 7d 0d 0a 24 66 28 78 |quotatio|n}..$f(x|
|00001830| 29 3d 30 24 2c 20 53 6f | 6c 75 74 69 6f 6e 20 69 |)=0$, So|lution i|
|00001840| 73 20 3a 20 24 5c 6c 65 | 66 74 5c 7b 20 78 3d 5c |s : $\le|ft\{ x=\|
|00001850| 66 72 61 63 7b 32 32 7d | 7b 37 7d 5c 72 69 67 68 |frac{22}|{7}\righ|
|00001860| 74 5c 7d 20 2c 5c 2c 5c | 6c 65 66 74 5c 7b 20 78 |t\} ,\,\|left\{ x|
|00001870| 3d 5c 66 72 61 63 7b 32 | 32 25 0d 0a 7d 7b 37 7d |=\frac{2|2%..}{7}|
|00001880| 5c 72 69 67 68 74 5c 7d | 20 2c 24 0d 0a 0d 0a 24 |\right\}| ,$....$|
|00001890| 5c 2c 5c 71 71 75 61 64 | 20 5c 6c 65 66 74 5c 7b |\,\qquad| \left\{|
|000018a0| 20 78 3d 2d 5c 73 71 72 | 74 5b 33 5d 7b 5c 6c 65 | x=-\sqr|t[3]{\le|
|000018b0| 66 74 28 20 5c 66 72 61 | 63 7b 31 7d 7b 32 7d 2b |ft( \fra|c{1}{2}+|
|000018c0| 5c 66 72 61 63 7b 31 7d | 7b 31 38 7d 5c 73 71 72 |\frac{1}|{18}\sqr|
|000018d0| 74 7b 39 33 7d 25 0d 0a | 5c 72 69 67 68 74 29 20 |t{93}%..|\right) |
|000018e0| 7d 2b 5c 64 66 72 61 63 | 7b 31 7d 7b 33 5c 73 71 |}+\dfrac|{1}{3\sq|
|000018f0| 72 74 5b 33 5d 7b 5c 6c | 65 66 74 28 20 5c 66 72 |rt[3]{\l|eft( \fr|
|00001900| 61 63 7b 31 7d 7b 32 7d | 2b 5c 66 72 61 63 7b 31 |ac{1}{2}|+\frac{1|
|00001910| 7d 7b 31 38 7d 5c 73 71 | 72 74 7b 39 33 7d 25 0d |}{18}\sq|rt{93}%.|
|00001920| 0a 5c 72 69 67 68 74 29 | 20 7d 7d 5c 72 69 67 68 |.\right)| }}\righ|
|00001930| 74 5c 7d 20 24 0d 0a 0d | 0a 5c 20 0d 0a 0d 0a 24 |t\} $...|.\ ....$|
|00001940| 67 28 78 29 3d 30 24 2c | 20 53 6f 6c 75 74 69 6f |g(x)=0$,| Solutio|
|00001950| 6e 20 69 73 20 3a 20 24 | 5c 6c 65 66 74 5c 7b 20 |n is : $|\left\{ |
|00001960| 78 3d 5c 66 72 61 63 7b | 32 32 7d 7b 37 7d 5c 72 |x=\frac{|22}{7}\r|
|00001970| 69 67 68 74 5c 7d 20 2c | 5c 2c 5c 6c 65 66 74 5c |ight\} ,|\,\left\|
|00001980| 7b 20 78 3d 5c 66 72 61 | 63 7b 25 0d 0a 33 35 35 |{ x=\fra|c{%..355|
|00001990| 7d 7b 31 31 33 7d 5c 72 | 69 67 68 74 5c 7d 20 2c |}{113}\r|ight\} ,|
|000019a0| 24 0d 0a 0d 0a 24 5c 71 | 71 75 61 64 20 5c 2c 5c |$....$\q|quad \,\|
|000019b0| 6c 65 66 74 5c 7b 20 78 | 3d 2d 5c 73 71 72 74 5b |left\{ x|=-\sqrt[|
|000019c0| 33 5d 7b 5c 6c 65 66 74 | 28 20 5c 66 72 61 63 7b |3]{\left|( \frac{|
|000019d0| 31 7d 7b 32 7d 2b 5c 66 | 72 61 63 7b 31 7d 7b 31 |1}{2}+\f|rac{1}{1|
|000019e0| 38 7d 5c 73 71 72 74 7b | 39 33 7d 25 0d 0a 5c 72 |8}\sqrt{|93}%..\r|
|000019f0| 69 67 68 74 29 20 7d 2b | 5c 64 66 72 61 63 7b 31 |ight) }+|\dfrac{1|
|00001a00| 7d 7b 33 5c 73 71 72 74 | 5b 33 5d 7b 5c 6c 65 66 |}{3\sqrt|[3]{\lef|
|00001a10| 74 28 20 5c 66 72 61 63 | 7b 31 7d 7b 32 7d 2b 5c |t( \frac|{1}{2}+\|
|00001a20| 66 72 61 63 7b 31 7d 7b | 31 38 7d 5c 73 71 72 74 |frac{1}{|18}\sqrt|
|00001a30| 7b 39 33 7d 25 0d 0a 5c | 72 69 67 68 74 29 20 7d |{93}%..\|right) }|
|00001a40| 7d 5c 72 69 67 68 74 5c | 7d 20 2c 5c 2c 5c 6d 65 |}\right\|} ,\,\me|
|00001a50| 64 73 6b 69 70 20 24 0d | 0a 5c 65 6e 64 7b 71 75 |dskip $.|.\end{qu|
|00001a60| 6f 74 61 74 69 6f 6e 7d | 0d 0a 0d 0a 5c 62 65 67 |otation}|....\beg|
|00001a70| 69 6e 7b 71 75 6f 74 65 | 7d 0d 0a 24 5c 62 6c 61 |in{quote|}..$\bla|
|00001a80| 63 6b 74 72 69 61 6e 67 | 6c 65 72 69 67 68 74 20 |cktriang|leright |
|00001a90| 24 20 5c 74 65 78 74 73 | 66 7b 53 6f 6c 76 65 20 |$ \texts|f{Solve |
|00001aa0| 2b 20 4e 75 6d 65 72 69 | 63 7d 0d 0a 5c 65 6e 64 |+ Numeri|c}..\end|
|00001ab0| 7b 71 75 6f 74 65 7d 0d | 0a 0d 0a 5c 62 65 67 69 |{quote}.|...\begi|
|00001ac0| 6e 7b 71 75 6f 74 61 74 | 69 6f 6e 7d 0d 0a 24 66 |n{quotat|ion}..$f|
|00001ad0| 28 78 29 3d 30 24 2c 20 | 53 6f 6c 75 74 69 6f 6e |(x)=0$, |Solution|
|00001ae0| 20 69 73 20 3a 20 24 5c | 6c 65 66 74 5c 7b 20 78 | is : $\|left\{ x|
|00001af0| 3d 2d 2e 36 38 32 33 33 | 5c 72 69 67 68 74 5c 7d |=-.68233|\right\}|
|00001b00| 20 2c 5c 2c 5c 6c 65 66 | 74 5c 7b 0d 0a 78 3d 33 | ,\,\lef|t\{..x=3|
|00001b10| 2e 31 34 32 39 5c 72 69 | 67 68 74 5c 7d 20 2c 5c |.1429\ri|ght\} ,\|
|00001b20| 2c 5c 6c 65 66 74 5c 7b | 20 78 3d 33 2e 31 34 32 |,\left\{| x=3.142|
|00001b30| 39 5c 72 69 67 68 74 5c | 7d 20 24 0d 0a 0d 0a 24 |9\right\|} $....$|
|00001b40| 67 28 78 29 3d 30 24 2c | 20 53 6f 6c 75 74 69 6f |g(x)=0$,| Solutio|
|00001b50| 6e 20 69 73 20 3a 20 24 | 5c 6c 65 66 74 5c 7b 20 |n is : $|\left\{ |
|00001b60| 78 3d 2d 2e 36 38 32 33 | 33 5c 72 69 67 68 74 5c |x=-.6823|3\right\|
|00001b70| 7d 20 2c 5c 2c 5c 6c 65 | 66 74 5c 7b 0d 0a 78 3d |} ,\,\le|ft\{..x=|
|00001b80| 33 2e 31 34 31 36 5c 72 | 69 67 68 74 5c 7d 20 2c |3.1416\r|ight\} ,|
|00001b90| 5c 2c 5c 6c 65 66 74 5c | 7b 20 78 3d 33 2e 31 34 |\,\left\|{ x=3.14|
|00001ba0| 32 39 5c 72 69 67 68 74 | 5c 7d 20 5c 6d 65 64 73 |29\right|\} \meds|
|00001bb0| 6b 69 70 20 24 0d 0a 5c | 65 6e 64 7b 71 75 6f 74 |kip $..\|end{quot|
|00001bc0| 61 74 69 6f 6e 7d 0d 0a | 0d 0a 5c 20 0d 0a 0d 0a |ation}..|..\ ....|
|00001bd0| 54 68 75 73 2c 20 24 67 | 24 20 68 61 73 20 74 77 |Thus, $g|$ has tw|
|00001be0| 6f 20 64 69 73 74 69 6e | 63 74 20 72 6f 6f 74 73 |o distin|ct roots|
|00001bf0| 20 74 68 61 74 20 61 72 | 65 20 65 78 74 72 65 6d | that ar|e extrem|
|00001c00| 65 6c 79 20 63 6c 6f 73 | 65 2c 20 77 68 65 72 65 |ely clos|e, where|
|00001c10| 61 73 20 24 66 24 20 68 | 61 73 20 61 0d 0a 72 6f |as $f$ h|as a..ro|
|00001c20| 6f 74 20 6f 66 20 6d 75 | 6c 74 69 70 6c 69 63 69 |ot of mu|ltiplici|
|00001c30| 74 79 20 74 77 6f 2e 0d | 0a 0d 0a 5c 20 0d 0a 0d |ty two..|...\ ...|
|00001c40| 0a 5c 73 75 62 73 65 63 | 74 69 6f 6e 7b 5c 20 5c |.\subsec|tion{\ \|
|00001c50| 6c 61 62 65 6c 7b 49 72 | 72 65 64 75 63 69 62 6c |label{Ir|reducibl|
|00001c60| 65 20 70 6f 6c 79 6e 6f | 6d 69 61 6c 7d 54 68 65 |e polyno|mial}The|
|00001c70| 20 47 61 6c 6f 69 73 20 | 46 69 65 6c 64 20 47 46 | Galois |Field GF|
|00001c80| 24 5f 7b 70 5e 7b 6e 7d | 7d 24 7d 0d 0a 0d 0a 41 |$_{p^{n}|}$}....A|
|00001c90| 73 73 75 6d 65 20 74 68 | 61 74 20 24 71 28 78 29 |ssume th|at $q(x)|
|00001ca0| 24 20 69 73 20 61 6e 20 | 0d 0a 5c 69 6e 64 65 78 |$ is an |..\index|
|00001cb0| 7b 50 6f 6c 79 6e 6f 6d | 69 61 6c 73 40 50 6f 6c |{Polynom|ials@Pol|
|00001cc0| 79 6e 6f 6d 69 61 6c 73 | 21 69 72 72 65 64 75 63 |ynomials|!irreduc|
|00001cd0| 69 62 6c 65 40 69 72 72 | 65 64 75 63 69 62 6c 65 |ible@irr|educible|
|00001ce0| 7d 5c 6c 61 62 65 6c 25 | 0d 0a 7b 50 6f 6c 79 6e |}\label%|..{Polyn|
|00001cf0| 6f 6d 69 61 6c 73 2c 20 | 69 72 72 65 64 75 63 69 |omials, |irreduci|
|00001d00| 62 6c 65 7d 5c 74 65 78 | 74 73 6c 7b 69 72 72 65 |ble}\tex|tsl{irre|
|00001d10| 64 75 63 69 62 6c 65 7d | 20 70 6f 6c 79 6e 6f 6d |ducible}| polynom|
|00001d20| 69 61 6c 20 6f 66 20 64 | 65 67 72 65 65 20 24 6e |ial of d|egree $n|
|00001d30| 24 20 6f 76 65 72 20 0d | 0a 24 47 46 5f 7b 70 7d |$ over .|.$GF_{p}|
|00001d40| 24 3b 20 74 68 61 74 20 | 69 73 2c 20 61 73 73 75 |$; that |is, assu|
|00001d50| 6d 65 20 74 68 61 74 20 | 24 71 28 78 29 24 20 69 |me that |$q(x)$ i|
|00001d60| 73 20 6f 66 20 64 65 67 | 72 65 65 20 24 6e 24 20 |s of deg|ree $n$ |
|00001d70| 61 6e 64 2c 20 77 68 65 | 6e 65 76 65 72 20 24 25 |and, whe|never $%|
|00001d80| 0d 0a 71 28 78 29 3d 61 | 28 78 29 62 28 78 29 24 |..q(x)=a|(x)b(x)$|
|00001d90| 20 66 6f 72 20 73 6f 6d | 65 20 24 61 28 78 29 24 | for som|e $a(x)$|
|00001da0| 20 61 6e 64 20 24 62 28 | 78 29 24 20 69 6e 20 24 | and $b(|x)$ in $|
|00001db0| 47 46 5f 7b 70 7d 5b 78 | 5d 24 2c 20 74 68 65 6e |GF_{p}[x|]$, then|
|00001dc0| 20 65 69 74 68 65 72 20 | 24 5c 64 65 67 0d 0a 28 | either |$\deg..(|
|00001dd0| 61 28 78 29 29 3d 30 24 | 20 6f 72 20 24 5c 64 65 |a(x))=0$| or $\de|
|00001de0| 67 20 28 62 28 78 29 29 | 3d 30 24 2e 20 47 69 76 |g (b(x))|=0$. Giv|
|00001df0| 65 6e 20 74 77 6f 20 70 | 6f 6c 79 6e 6f 6d 69 61 |en two p|olynomia|
|00001e00| 6c 73 20 24 66 28 78 29 | 24 20 61 6e 64 20 24 67 |ls $f(x)|$ and $g|
|00001e10| 28 78 29 24 20 69 6e 20 | 24 25 0d 0a 47 46 5f 7b |(x)$ in |$%..GF_{|
|00001e20| 70 7d 5b 78 5d 24 2c 20 | 64 65 66 69 6e 65 20 74 |p}[x]$, |define t|
|00001e30| 68 65 20 70 72 6f 64 75 | 63 74 20 74 6f 20 62 65 |he produ|ct to be|
|00001e40| 20 74 68 65 20 70 6f 6c | 79 6e 6f 6d 69 61 6c 20 | the pol|ynomial |
|00001e50| 24 28 66 28 78 29 67 28 | 78 29 25 0d 0a 5c 6c 69 |$(f(x)g(|x)%..\li|
|00001e60| 6d 66 75 6e 63 7b 6d 6f | 64 7d 71 28 78 29 29 5c |mfunc{mo|d}q(x))\|
|00001e70| 6c 69 6d 66 75 6e 63 7b | 6d 6f 64 7d 70 24 20 61 |limfunc{|mod}p$ a|
|00001e80| 6e 64 20 74 68 65 20 73 | 75 6d 20 74 6f 20 62 65 |nd the s|um to be|
|00001e90| 20 74 68 65 20 70 6f 6c | 79 6e 6f 6d 69 61 6c 20 | the pol|ynomial |
|00001ea0| 24 5c 6c 65 66 74 28 0d | 0a 66 28 78 29 2b 67 28 |$\left(.|.f(x)+g(|
|00001eb0| 78 29 5c 72 69 67 68 74 | 29 20 5c 6c 69 6d 66 75 |x)\right|) \limfu|
|00001ec0| 6e 63 7b 6d 6f 64 7d 70 | 24 2e 20 57 69 74 68 20 |nc{mod}p|$. With |
|00001ed0| 74 68 65 73 65 20 64 65 | 66 69 6e 69 74 69 6f 6e |these de|finition|
|00001ee0| 73 2c 20 74 68 65 20 73 | 65 74 20 6f 66 0d 0a 70 |s, the s|et of..p|
|00001ef0| 6f 6c 79 6e 6f 6d 69 61 | 6c 73 20 69 6e 20 24 47 |olynomia|ls in $G|
|00001f00| 46 5f 7b 70 7d 5b 78 5d | 24 20 6f 66 20 64 65 67 |F_{p}[x]|$ of deg|
|00001f10| 72 65 65 20 6c 65 73 73 | 20 74 68 61 6e 20 24 6e |ree less| than $n|
|00001f20| 24 20 66 6f 72 6d 73 20 | 61 20 66 69 65 6c 64 20 |$ forms |a field |
|00001f30| 63 61 6c 6c 65 64 20 74 | 68 65 20 0d 0a 5c 74 65 |called t|he ..\te|
|00001f40| 78 74 73 6c 7b 47 61 6c | 6f 69 73 20 66 69 65 6c |xtsl{Gal|ois fiel|
|00001f50| 64 7d 20 24 47 46 5f 7b | 70 5e 7b 6e 7d 7d 24 2e |d} $GF_{|p^{n}}$.|
|00001f60| 0d 0a 0d 0a 54 68 65 20 | 73 65 74 20 6f 66 20 70 |....The |set of p|
|00001f70| 6f 6c 79 6e 6f 6d 69 61 | 6c 73 20 69 6e 20 24 47 |olynomia|ls in $G|
|00001f80| 46 5f 32 5b 78 5d 24 20 | 6f 66 20 64 65 67 72 65 |F_2[x]$ |of degre|
|00001f90| 65 20 6c 65 73 73 20 74 | 68 61 6e 20 24 32 24 20 |e less t|han $2$ |
|00001fa0| 66 6f 72 6d 73 20 74 68 | 65 20 66 69 65 6c 64 20 |forms th|e field |
|00001fb0| 24 25 0d 0a 47 46 5f 7b | 32 5e 32 7d 3d 5c 3b 47 |$%..GF_{|2^2}=\;G|
|00001fc0| 46 5f 34 24 2e 20 54 68 | 65 20 6d 75 6c 74 69 70 |F_4$. Th|e multip|
|00001fd0| 6c 69 63 61 74 69 6f 6e | 20 61 6e 64 20 61 64 64 |lication| and add|
|00001fe0| 69 74 69 6f 6e 20 74 61 | 62 6c 65 73 20 66 6f 72 |ition ta|bles for|
|00001ff0| 20 24 47 46 5f 32 24 20 | 61 72 65 0d 0a 67 69 76 | $GF_2$ |are..giv|
|00002000| 65 6e 20 62 79 20 0d 0a | 5c 5b 0d 0a 5c 62 65 67 |en by ..|\[..\beg|
|00002010| 69 6e 7b 74 61 62 75 6c | 61 72 7d 7b 63 7c 63 63 |in{tabul|ar}{c|cc|
|00002020| 7d 0d 0a 24 5c 74 69 6d | 65 73 20 24 20 26 20 30 |}..$\tim|es $ & 0|
|00002030| 20 26 20 31 20 5c 5c 20 | 5c 68 6c 69 6e 65 0d 0a | & 1 \\ |\hline..|
|00002040| 30 20 26 20 30 20 26 20 | 30 20 5c 5c 20 0d 0a 31 |0 & 0 & |0 \\ ..1|
|00002050| 20 26 20 30 20 26 20 31 | 0d 0a 5c 65 6e 64 7b 74 | & 0 & 1|..\end{t|
|00002060| 61 62 75 6c 61 72 7d 0d | 0a 5c 71 71 75 61 64 20 |abular}.|.\qquad |
|00002070| 5c 71 71 75 61 64 20 0d | 0a 5c 62 65 67 69 6e 7b |\qquad .|.\begin{|
|00002080| 74 61 62 75 6c 61 72 7d | 7b 63 7c 63 63 7d 0d 0a |tabular}|{c|cc}..|
|00002090| 24 2b 24 20 26 20 30 20 | 26 20 31 20 5c 5c 20 5c |$+$ & 0 |& 1 \\ \|
|000020a0| 68 6c 69 6e 65 0d 0a 30 | 20 26 20 30 20 26 20 31 |hline..0| & 0 & 1|
|000020b0| 20 5c 5c 20 0d 0a 31 20 | 26 20 31 20 26 20 30 0d | \\ ..1 |& 1 & 0.|
|000020c0| 0a 5c 65 6e 64 7b 74 61 | 62 75 6c 61 72 7d 0d 0a |.\end{ta|bular}..|
|000020d0| 5c 5d 0d 0a 54 68 65 20 | 70 6f 6c 79 6e 6f 6d 69 |\]..The |polynomi|
|000020e0| 61 6c 20 24 71 28 78 29 | 3d 78 5e 32 2b 78 2b 31 |al $q(x)|=x^2+x+1|
|000020f0| 24 20 69 73 20 61 6e 20 | 28 69 6e 20 66 61 63 74 |$ is an |(in fact|
|00002100| 2c 20 74 68 65 20 6f 6e | 6c 79 29 20 69 72 72 65 |, the on|ly) irre|
|00002110| 64 75 63 69 62 6c 65 0d | 0a 70 6f 6c 79 6e 6f 6d |ducible.|.polynom|
|00002120| 69 61 6c 20 6f 66 20 64 | 65 67 72 65 65 20 24 32 |ial of d|egree $2|
|00002130| 24 20 6f 76 65 72 20 24 | 47 46 5f 32 24 2e 20 54 |$ over $|GF_2$. T|
|00002140| 68 65 20 65 6c 65 6d 65 | 6e 74 73 20 6f 66 20 24 |he eleme|nts of $|
|00002150| 47 46 5f 34 24 20 61 72 | 65 20 24 30 24 2c 20 24 |GF_4$ ar|e $0$, $|
|00002160| 31 24 2c 20 24 25 0d 0a | 78 20 24 2c 20 61 6e 64 |1$, $%..|x $, and|
|00002170| 20 24 31 2b 78 24 2e 0d | 0a 0d 0a 54 6f 20 66 69 | $1+x$..|...To fi|
|00002180| 6e 64 20 74 68 65 20 70 | 72 6f 64 75 63 74 20 24 |nd the p|roduct $|
|00002190| 78 5c 63 64 6f 74 20 78 | 24 20 69 6e 20 24 47 46 |x\cdot x|$ in $GF|
|000021a0| 5f 34 2c 24 20 72 65 64 | 75 63 65 20 74 68 65 20 |_4,$ red|uce the |
|000021b0| 70 72 6f 64 75 63 74 20 | 6d 6f 64 75 6c 6f 20 24 |product |modulo $|
|000021c0| 25 0d 0a 78 5e 32 2b 78 | 2b 31 2c 20 24 20 74 68 |%..x^2+x|+1, $ th|
|000021d0| 65 6e 20 72 65 64 75 63 | 65 20 74 68 65 20 72 65 |en reduc|e the re|
|000021e0| 73 75 6c 74 20 6d 6f 64 | 75 6c 6f 20 24 32 2e 5c |sult mod|ulo $2.\|
|000021f0| 6d 65 64 73 6b 69 70 20 | 24 0d 0a 0d 0a 5c 62 65 |medskip |$....\be|
|00002200| 67 69 6e 7b 71 75 6f 74 | 65 7d 0d 0a 24 5c 62 6c |gin{quot|e}..$\bl|
|00002210| 61 63 6b 74 72 69 61 6e | 67 6c 65 72 69 67 68 74 |acktrian|gleright|
|00002220| 20 24 20 5c 74 65 78 74 | 73 66 7b 45 76 61 6c 75 | $ \text|sf{Evalu|
|00002230| 61 74 65 7d 0d 0a 5c 65 | 6e 64 7b 71 75 6f 74 65 |ate}..\e|nd{quote|
|00002240| 7d 0d 0a 0d 0a 5c 62 65 | 67 69 6e 7b 71 75 6f 74 |}....\be|gin{quot|
|00002250| 61 74 69 6f 6e 7d 0d 0a | 24 28 78 5e 7b 32 7d 5c |ation}..|$(x^{2}\|
|00002260| 6c 69 6d 66 75 6e 63 7b | 6d 6f 64 7d 71 28 78 29 |limfunc{|mod}q(x)|
|00002270| 29 5c 6c 69 6d 66 75 6e | 63 7b 6d 6f 64 7d 32 3d |)\limfun|c{mod}2=|
|00002280| 78 2b 31 5c 6d 65 64 73 | 6b 69 70 20 24 0d 0a 5c |x+1\meds|kip $..\|
|00002290| 65 6e 64 7b 71 75 6f 74 | 61 74 69 6f 6e 7d 0d 0a |end{quot|ation}..|
|000022a0| 0d 0a 54 68 75 73 2c 20 | 24 78 5e 32 3d 78 2b 31 |..Thus, |$x^2=x+1|
|000022b0| 24 20 69 6e 20 24 47 46 | 5f 34 24 2e 20 59 6f 75 |$ in $GF|_4$. You|
|000022c0| 20 63 61 6e 20 67 65 6e | 65 72 61 74 65 20 74 68 | can gen|erate th|
|000022d0| 65 20 65 6e 74 69 72 65 | 20 6d 75 6c 74 69 70 6c |e entire| multipl|
|000022e0| 69 63 61 74 69 6f 6e 20 | 74 61 62 6c 65 0d 0a 65 |ication |table..e|
|000022f0| 66 66 69 63 69 65 6e 74 | 6c 79 20 75 73 69 6e 67 |fficient|ly using|
|00002300| 20 6d 61 74 72 69 78 20 | 61 6e 64 20 6d 6f 64 75 | matrix |and modu|
|00002310| 6c 61 72 20 61 72 69 74 | 68 6d 65 74 69 63 2e 5c |lar arit|hmetic.\|
|00002320| 6d 65 64 73 6b 69 70 0d | 0a 0d 0a 5c 62 65 67 69 |medskip.|...\begi|
|00002330| 6e 7b 71 75 6f 74 65 7d | 0d 0a 24 5c 62 6c 61 63 |n{quote}|..$\blac|
|00002340| 6b 74 72 69 61 6e 67 6c | 65 72 69 67 68 74 20 24 |ktriangl|eright $|
|00002350| 20 5c 74 65 78 74 73 66 | 7b 45 76 61 6c 75 61 74 | \textsf|{Evaluat|
|00002360| 65 20 7d 28 33 20 74 69 | 6d 65 73 29 0d 0a 5c 65 |e }(3 ti|mes)..\e|
|00002370| 6e 64 7b 71 75 6f 74 65 | 7d 0d 0a 0d 0a 5c 62 65 |nd{quote|}....\be|
|00002380| 67 69 6e 7b 71 75 6f 74 | 61 74 69 6f 6e 7d 0d 0a |gin{quot|ation}..|
|00002390| 24 5c 6c 65 66 74 5b 20 | 0d 0a 5c 62 65 67 69 6e |$\left[ |..\begin|
|000023a0| 7b 61 72 72 61 79 7d 7b | 63 7d 0d 0a 30 20 5c 5c |{array}{|c}..0 \\|
|000023b0| 20 0d 0a 31 20 5c 5c 20 | 0d 0a 78 20 5c 5c 20 0d | ..1 \\ |..x \\ .|
|000023c0| 0a 78 2b 31 0d 0a 5c 65 | 6e 64 7b 61 72 72 61 79 |.x+1..\e|nd{array|
|000023d0| 7d 0d 0a 5c 72 69 67 68 | 74 5d 20 5c 6c 65 66 74 |}..\righ|t] \left|
|000023e0| 5b 20 0d 0a 5c 62 65 67 | 69 6e 7b 61 72 72 61 79 |[ ..\beg|in{array|
|000023f0| 7d 7b 63 63 63 63 7d 0d | 0a 30 20 26 20 31 20 26 |}{cccc}.|.0 & 1 &|
|00002400| 20 78 20 26 20 78 2b 31 | 0d 0a 5c 65 6e 64 7b 61 | x & x+1|..\end{a|
|00002410| 72 72 61 79 7d 0d 0a 5c | 72 69 67 68 74 5d 20 3d |rray}..\|right] =|
|00002420| 5c 61 6c 6c 6f 77 62 72 | 65 61 6b 20 5c 6c 65 66 |\allowbr|eak \lef|
|00002430| 74 5b 20 0d 0a 5c 62 65 | 67 69 6e 7b 61 72 72 61 |t[ ..\be|gin{arra|
|00002440| 79 7d 7b 63 63 63 63 7d | 0d 0a 30 20 26 20 30 20 |y}{cccc}|..0 & 0 |
|00002450| 26 20 30 20 26 20 30 20 | 5c 5c 20 0d 0a 30 20 26 |& 0 & 0 |\\ ..0 &|
|00002460| 20 31 20 26 20 78 20 26 | 20 78 2b 31 20 5c 5c 20 | 1 & x &| x+1 \\ |
|00002470| 0d 0a 30 20 26 20 78 20 | 26 20 78 5e 7b 32 7d 20 |..0 & x |& x^{2} |
|00002480| 26 20 78 5c 6c 65 66 74 | 28 20 78 2b 31 5c 72 69 |& x\left|( x+1\ri|
|00002490| 67 68 74 29 20 5c 5c 20 | 0d 0a 30 20 26 20 78 2b |ght) \\ |..0 & x+|
|000024a0| 31 20 26 20 78 5c 6c 65 | 66 74 28 20 78 2b 31 5c |1 & x\le|ft( x+1\|
|000024b0| 72 69 67 68 74 29 20 26 | 20 5c 6c 65 66 74 28 20 |right) &| \left( |
|000024c0| 78 2b 31 5c 72 69 67 68 | 74 29 20 5e 7b 32 7d 0d |x+1\righ|t) ^{2}.|
|000024d0| 0a 5c 65 6e 64 7b 61 72 | 72 61 79 7d 0d 0a 5c 72 |.\end{ar|ray}..\r|
|000024e0| 69 67 68 74 5d 20 24 0d | 0a 0d 0a 5c 20 0d 0a 0d |ight] $.|...\ ...|
|000024f0| 0a 24 5c 6c 65 66 74 5b | 20 0d 0a 5c 62 65 67 69 |.$\left[| ..\begi|
|00002500| 6e 7b 61 72 72 61 79 7d | 7b 63 63 63 63 7d 0d 0a |n{array}|{cccc}..|
|00002510| 30 20 26 20 30 20 26 20 | 30 20 26 20 30 20 5c 5c |0 & 0 & |0 & 0 \\|
|00002520| 20 0d 0a 30 20 26 20 31 | 20 26 20 78 20 26 20 78 | ..0 & 1| & x & x|
|00002530| 2b 31 20 5c 5c 20 0d 0a | 30 20 26 20 78 20 26 20 |+1 \\ ..|0 & x & |
|00002540| 78 5e 7b 32 7d 20 26 20 | 78 5c 6c 65 66 74 28 20 |x^{2} & |x\left( |
|00002550| 78 2b 31 5c 72 69 67 68 | 74 29 20 5c 5c 20 0d 0a |x+1\righ|t) \\ ..|
|00002560| 30 20 26 20 78 2b 31 20 | 26 20 78 5c 6c 65 66 74 |0 & x+1 |& x\left|
|00002570| 28 20 78 2b 31 5c 72 69 | 67 68 74 29 20 26 20 5c |( x+1\ri|ght) & \|
|00002580| 6c 65 66 74 28 20 78 2b | 31 5c 72 69 67 68 74 29 |left( x+|1\right)|
|00002590| 20 5e 7b 32 7d 0d 0a 5c | 65 6e 64 7b 61 72 72 61 | ^{2}..\|end{arra|
|000025a0| 79 7d 0d 0a 5c 72 69 67 | 68 74 5d 20 5c 66 75 6e |y}..\rig|ht] \fun|
|000025b0| 63 7b 6d 6f 64 7d 78 5e | 7b 32 7d 2b 78 2b 31 24 |c{mod}x^|{2}+x+1$|
|000025c0| 0d 0a 0d 0a 24 5c 71 71 | 75 61 64 20 5c 71 71 75 |....$\qq|uad \qqu|
|000025d0| 61 64 20 5c 71 71 75 61 | 64 20 5c 71 71 75 61 64 |ad \qqua|d \qquad|
|000025e0| 20 5c 71 71 75 61 64 20 | 5c 71 71 75 61 64 20 5c | \qquad |\qquad \|
|000025f0| 71 71 75 61 64 20 5c 71 | 75 61 64 20 3d 5c 6c 65 |qquad \q|uad =\le|
|00002600| 66 74 5b 20 0d 0a 5c 62 | 65 67 69 6e 7b 61 72 72 |ft[ ..\b|egin{arr|
|00002610| 61 79 7d 7b 63 63 63 63 | 7d 0d 0a 30 20 26 20 30 |ay}{cccc|}..0 & 0|
|00002620| 20 26 20 30 20 26 20 30 | 20 5c 5c 20 0d 0a 30 20 | & 0 & 0| \\ ..0 |
|00002630| 26 20 31 20 26 20 78 20 | 26 20 78 2b 31 20 5c 5c |& 1 & x |& x+1 \\|
|00002640| 20 0d 0a 30 20 26 20 78 | 20 26 20 2d 78 2d 31 20 | ..0 & x| & -x-1 |
|00002650| 26 20 2d 31 20 5c 5c 20 | 0d 0a 30 20 26 20 78 2b |& -1 \\ |..0 & x+|
|00002660| 31 20 26 20 2d 31 20 26 | 20 78 0d 0a 5c 65 6e 64 |1 & -1 &| x..\end|
|00002670| 7b 61 72 72 61 79 7d 0d | 0a 5c 72 69 67 68 74 5d |{array}.|.\right]|
|00002680| 20 24 0d 0a 0d 0a 5c 20 | 0d 0a 0d 0a 24 5c 6c 65 | $....\ |....$\le|
|00002690| 66 74 5b 20 0d 0a 5c 62 | 65 67 69 6e 7b 61 72 72 |ft[ ..\b|egin{arr|
|000026a0| 61 79 7d 7b 63 63 63 63 | 7d 0d 0a 30 20 26 20 30 |ay}{cccc|}..0 & 0|
|000026b0| 20 26 20 30 20 26 20 30 | 20 5c 5c 20 0d 0a 30 20 | & 0 & 0| \\ ..0 |
|000026c0| 26 20 31 20 26 20 78 20 | 26 20 78 2b 31 20 5c 5c |& 1 & x |& x+1 \\|
|000026d0| 20 0d 0a 30 20 26 20 78 | 20 26 20 2d 78 2d 31 20 | ..0 & x| & -x-1 |
|000026e0| 26 20 2d 31 20 5c 5c 20 | 0d 0a 30 20 26 20 78 2b |& -1 \\ |..0 & x+|
|000026f0| 31 20 26 20 2d 31 20 26 | 20 78 0d 0a 5c 65 6e 64 |1 & -1 &| x..\end|
|00002700| 7b 61 72 72 61 79 7d 0d | 0a 5c 72 69 67 68 74 5d |{array}.|.\right]|
|00002710| 20 5c 66 75 6e 63 7b 6d | 6f 64 7d 32 3d 5c 61 6c | \func{m|od}2=\al|
|00002720| 6c 6f 77 62 72 65 61 6b | 20 5c 6c 65 66 74 5b 20 |lowbreak| \left[ |
|00002730| 0d 0a 5c 62 65 67 69 6e | 7b 61 72 72 61 79 7d 7b |..\begin|{array}{|
|00002740| 63 63 63 63 7d 0d 0a 30 | 20 26 20 30 20 26 20 30 |cccc}..0| & 0 & 0|
|00002750| 20 26 20 30 20 5c 5c 20 | 0d 0a 30 20 26 20 31 20 | & 0 \\ |..0 & 1 |
|00002760| 26 20 78 20 26 20 78 2b | 31 20 5c 5c 20 0d 0a 30 |& x & x+|1 \\ ..0|
|00002770| 20 26 20 78 20 26 20 78 | 2b 31 20 26 20 31 20 5c | & x & x|+1 & 1 \|
|00002780| 5c 20 0d 0a 30 20 26 20 | 78 2b 31 20 26 20 31 20 |\ ..0 & |x+1 & 1 |
|00002790| 26 20 78 0d 0a 5c 65 6e | 64 7b 61 72 72 61 79 7d |& x..\en|d{array}|
|000027a0| 0d 0a 5c 72 69 67 68 74 | 5d 20 5c 6d 65 64 73 6b |..\right|] \medsk|
|000027b0| 69 70 20 24 0d 0a 5c 65 | 6e 64 7b 71 75 6f 74 61 |ip $..\e|nd{quota|
|000027c0| 74 69 6f 6e 7d 0d 0a 0d | 0a 5c 20 0d 0a 0d 0a 53 |tion}...|.\ ....S|
|000027d0| 75 6d 73 20 72 65 71 75 | 69 72 65 20 6f 6e 6c 79 |ums requ|ire only|
|000027e0| 20 72 65 64 75 63 74 69 | 6f 6e 20 6f 66 20 70 6f | reducti|on of po|
|000027f0| 6c 79 6e 6f 6d 69 61 6c | 20 73 75 6d 73 20 6d 6f |lynomial| sums mo|
|00002800| 64 75 6c 6f 20 24 32 24 | 2e 20 54 68 65 0d 0a 6d |dulo $2$|. The..m|
|00002810| 75 6c 74 69 70 6c 69 63 | 61 74 69 6f 6e 20 61 6e |ultiplic|ation an|
|00002820| 64 20 61 64 64 69 74 69 | 6f 6e 20 74 61 62 6c 65 |d additi|on table|
|00002830| 73 20 61 72 65 20 67 69 | 76 65 6e 20 62 79 20 0d |s are gi|ven by .|
|00002840| 0a 5c 5b 0d 0a 5c 62 65 | 67 69 6e 7b 74 61 62 75 |.\[..\be|gin{tabu|
|00002850| 6c 61 72 7d 7b 63 7c 63 | 63 63 63 7d 0d 0a 24 5c |lar}{c|c|ccc}..$\|
|00002860| 74 69 6d 65 73 20 24 20 | 26 20 30 20 26 20 31 20 |times $ |& 0 & 1 |
|00002870| 26 20 24 78 24 20 26 20 | 24 78 2b 31 24 20 5c 5c |& $x$ & |$x+1$ \\|
|00002880| 20 5c 68 6c 69 6e 65 0d | 0a 30 20 26 20 30 20 26 | \hline.|.0 & 0 &|
|00002890| 20 30 20 26 20 30 20 26 | 20 30 20 5c 5c 20 0d 0a | 0 & 0 &| 0 \\ ..|
|000028a0| 31 20 26 20 30 20 26 20 | 31 20 26 20 24 78 24 20 |1 & 0 & |1 & $x$ |
|000028b0| 26 20 24 78 2b 31 24 20 | 5c 5c 20 0d 0a 24 78 24 |& $x+1$ |\\ ..$x$|
|000028c0| 20 26 20 30 20 26 20 24 | 78 24 20 26 20 24 78 2b | & 0 & $|x$ & $x+|
|000028d0| 31 24 20 26 20 31 20 5c | 5c 20 0d 0a 24 78 2b 31 |1$ & 1 \|\ ..$x+1|
|000028e0| 24 20 26 20 30 20 26 20 | 24 78 2b 31 24 20 26 20 |$ & 0 & |$x+1$ & |
|000028f0| 31 20 26 20 24 78 24 25 | 0d 0a 5c 65 6e 64 7b 74 |1 & $x$%|..\end{t|
|00002900| 61 62 75 6c 61 72 7d 0d | 0a 5c 5d 0d 0a 5c 5b 0d |abular}.|.\]..\[.|
|00002910| 0a 5c 62 65 67 69 6e 7b | 74 61 62 75 6c 61 72 7d |.\begin{|tabular}|
|00002920| 7b 63 7c 63 63 63 63 7d | 0d 0a 24 2b 24 20 26 20 |{c|cccc}|..$+$ & |
|00002930| 30 20 26 20 31 20 26 20 | 24 78 24 20 26 20 24 78 |0 & 1 & |$x$ & $x|
|00002940| 2b 31 24 20 5c 5c 20 5c | 68 6c 69 6e 65 0d 0a 30 |+1$ \\ \|hline..0|
|00002950| 20 26 20 30 20 26 20 31 | 20 26 20 24 78 24 20 26 | & 0 & 1| & $x$ &|
|00002960| 20 24 78 2b 31 24 20 5c | 5c 20 0d 0a 31 20 26 20 | $x+1$ \|\ ..1 & |
|00002970| 31 20 26 20 30 20 26 20 | 24 78 2b 31 24 20 26 20 |1 & 0 & |$x+1$ & |
|00002980| 24 78 24 20 5c 5c 20 0d | 0a 24 78 24 20 26 20 24 |$x$ \\ .|.$x$ & $|
|00002990| 78 24 20 26 20 24 78 2b | 31 24 20 26 20 30 20 26 |x$ & $x+|1$ & 0 &|
|000029a0| 20 31 20 5c 5c 20 0d 0a | 24 78 2b 31 24 20 26 20 | 1 \\ ..|$x+1$ & |
|000029b0| 24 78 2b 31 24 20 26 20 | 24 78 24 20 26 20 31 20 |$x+1$ & |$x$ & 1 |
|000029c0| 26 20 30 0d 0a 5c 65 6e | 64 7b 74 61 62 75 6c 61 |& 0..\en|d{tabula|
|000029d0| 72 7d 0d 0a 5c 5d 0d 0a | 47 69 76 65 6e 20 61 20 |r}..\]..|Given a |
|000029e0| 70 6f 6c 79 6e 6f 6d 69 | 61 6c 20 24 66 28 78 29 |polynomi|al $f(x)|
|000029f0| 3d 61 78 2b 62 24 20 77 | 69 74 68 20 24 61 24 20 |=ax+b$ w|ith $a$ |
|00002a00| 61 6e 64 20 24 62 24 20 | 69 6e 20 24 47 46 5f 7b |and $b$ |in $GF_{|
|00002a10| 32 7d 24 2c 20 63 6f 6e | 73 69 64 65 72 20 74 68 |2}$, con|sider th|
|00002a20| 65 20 0d 0a 5c 69 6e 64 | 65 78 7b 42 69 6e 61 72 |e ..\ind|ex{Binar|
|00002a30| 79 40 42 69 6e 61 72 79 | 7d 5c 6c 61 62 65 6c 7b |y@Binary|}\label{|
|00002a40| 42 69 6e 61 72 79 7d 62 | 69 6e 61 72 79 20 72 65 |Binary}b|inary re|
|00002a50| 70 72 65 73 65 6e 74 61 | 74 69 6f 6e 20 24 28 61 |presenta|tion $(a|
|00002a60| 62 29 5f 7b 32 7d 24 2e | 20 54 68 65 0d 0a 62 69 |b)_{2}$.| The..bi|
|00002a70| 6e 61 72 79 20 72 65 70 | 72 65 73 65 6e 74 61 74 |nary rep|resentat|
|00002a80| 69 6f 6e 73 20 66 6f 72 | 20 74 68 65 20 6d 75 6c |ions for| the mul|
|00002a90| 74 69 70 6c 69 63 61 74 | 69 6f 6e 20 61 6e 64 20 |tiplicat|ion and |
|00002aa0| 61 64 64 69 74 69 6f 6e | 20 74 61 62 6c 65 73 20 |addition| tables |
|00002ab0| 66 6f 72 20 24 25 0d 0a | 47 46 5f 7b 34 7d 20 24 |for $%..|GF_{4} $|
|00002ac0| 20 61 72 65 20 67 69 76 | 65 6e 20 62 79 20 5c 6d | are giv|en by \m|
|00002ad0| 65 64 73 6b 69 70 20 0d | 0a 5c 5b 0d 0a 5c 62 65 |edskip .|.\[..\be|
|00002ae0| 67 69 6e 7b 74 61 62 75 | 6c 61 72 7d 7b 63 7c 63 |gin{tabu|lar}{c|c|
|00002af0| 63 63 63 7d 0d 0a 24 5c | 74 69 6d 65 73 20 24 20 |ccc}..$\|times $ |
|00002b00| 26 20 30 30 20 26 20 30 | 31 20 26 20 31 30 20 26 |& 00 & 0|1 & 10 &|
|00002b10| 20 31 31 20 5c 5c 20 5c | 68 6c 69 6e 65 0d 0a 30 | 11 \\ \|hline..0|
|00002b20| 30 20 26 20 30 30 20 26 | 20 30 30 20 26 20 30 30 |0 & 00 &| 00 & 00|
|00002b30| 20 26 20 30 30 20 5c 5c | 20 0d 0a 30 31 20 26 20 | & 00 \\| ..01 & |
|00002b40| 30 30 20 26 20 30 31 20 | 26 20 31 30 20 26 20 31 |00 & 01 |& 10 & 1|
|00002b50| 31 20 5c 5c 20 0d 0a 31 | 30 20 26 20 30 30 20 26 |1 \\ ..1|0 & 00 &|
|00002b60| 20 31 30 20 26 20 31 31 | 20 26 20 30 31 20 5c 5c | 10 & 11| & 01 \\|
|00002b70| 20 0d 0a 31 31 20 26 20 | 30 30 20 26 20 31 31 20 | ..11 & |00 & 11 |
|00002b80| 26 20 30 31 20 26 20 31 | 30 0d 0a 5c 65 6e 64 7b |& 01 & 1|0..\end{|
|00002b90| 74 61 62 75 6c 61 72 7d | 0d 0a 5c 71 75 61 64 20 |tabular}|..\quad |
|00002ba0| 5c 71 71 75 61 64 20 0d | 0a 5c 62 65 67 69 6e 7b |\qquad .|.\begin{|
|00002bb0| 74 61 62 75 6c 61 72 7d | 7b 63 7c 63 63 63 63 7d |tabular}|{c|cccc}|
|00002bc0| 0d 0a 24 2b 24 20 26 20 | 30 30 20 26 20 31 31 20 |..$+$ & |00 & 11 |
|00002bd0| 26 20 31 30 20 26 20 31 | 31 20 5c 5c 20 5c 68 6c |& 10 & 1|1 \\ \hl|
|00002be0| 69 6e 65 0d 0a 30 30 20 | 26 20 30 30 20 26 20 30 |ine..00 |& 00 & 0|
|00002bf0| 31 20 26 20 31 30 20 26 | 20 31 31 20 5c 5c 20 0d |1 & 10 &| 11 \\ .|
|00002c00| 0a 30 31 20 26 20 30 31 | 20 26 20 30 30 20 26 20 |.01 & 01| & 00 & |
|00002c10| 31 31 20 26 20 31 30 20 | 5c 5c 20 0d 0a 31 30 20 |11 & 10 |\\ ..10 |
|00002c20| 26 20 31 30 20 26 20 31 | 31 20 26 20 30 30 20 26 |& 10 & 1|1 & 00 &|
|00002c30| 20 30 31 20 5c 5c 20 0d | 0a 31 31 20 26 20 31 31 | 01 \\ .|.11 & 11|
|00002c40| 20 26 20 31 30 20 26 20 | 30 31 20 26 20 30 30 0d | & 10 & |01 & 00.|
|00002c50| 0a 5c 65 6e 64 7b 74 61 | 62 75 6c 61 72 7d 0d 0a |.\end{ta|bular}..|
|00002c60| 5c 6d 65 64 73 6b 69 70 | 20 0d 0a 5c 5d 0d 0a 43 |\medskip| ..\]..C|
|00002c70| 6f 6e 76 65 72 74 69 6e | 67 20 66 72 6f 6d 20 62 |onvertin|g from b|
|00002c80| 69 6e 61 72 79 20 74 6f | 20 64 65 63 69 6d 61 6c |inary to| decimal|
|00002c90| 2c 20 77 65 20 68 61 76 | 65 20 24 30 3d 28 30 30 |, we hav|e $0=(00|
|00002ca0| 29 5f 7b 32 7d 24 2c 20 | 24 31 3d 28 30 31 29 5f |)_{2}$, |$1=(01)_|
|00002cb0| 7b 32 7d 24 2c 20 24 25 | 0d 0a 32 3d 28 31 30 29 |{2}$, $%|..2=(10)|
|00002cc0| 5f 7b 32 7d 24 2c 20 61 | 6e 64 20 24 33 3d 5c 6c |_{2}$, a|nd $3=\l|
|00002cd0| 65 66 74 28 20 31 31 5c | 72 69 67 68 74 29 20 5f |eft( 11\|right) _|
|00002ce0| 7b 32 7d 24 2e 20 55 73 | 69 6e 67 20 74 68 69 73 |{2}$. Us|ing this|
|00002cf0| 20 73 68 6f 72 74 68 61 | 6e 64 20 6e 6f 74 61 74 | shortha|nd notat|
|00002d00| 69 6f 6e 0d 0a 66 6f 72 | 20 70 6f 6c 79 6e 6f 6d |ion..for| polynom|
|00002d10| 69 61 6c 73 2c 20 74 68 | 65 20 6d 75 6c 74 69 70 |ials, th|e multip|
|00002d20| 6c 69 63 61 74 69 6f 6e | 20 61 6e 64 20 61 64 64 |lication| and add|
|00002d30| 69 74 69 6f 6e 20 74 61 | 62 6c 65 73 20 62 65 63 |ition ta|bles bec|
|00002d40| 6f 6d 65 20 5c 6d 65 64 | 73 6b 69 70 20 0d 0a 5c |ome \med|skip ..\|
|00002d50| 5b 0d 0a 5c 62 65 67 69 | 6e 7b 74 61 62 75 6c 61 |[..\begi|n{tabula|
|00002d60| 72 7d 7b 63 7c 63 63 63 | 63 7d 0d 0a 24 5c 74 69 |r}{c|ccc|c}..$\ti|
|00002d70| 6d 65 73 20 24 20 26 20 | 30 20 26 20 31 20 26 20 |mes $ & |0 & 1 & |
|00002d80| 32 20 26 20 33 20 5c 5c | 20 5c 68 6c 69 6e 65 0d |2 & 3 \\| \hline.|
|00002d90| 0a 30 20 26 20 30 20 26 | 20 30 20 26 20 30 20 26 |.0 & 0 &| 0 & 0 &|
|00002da0| 20 30 20 5c 5c 20 0d 0a | 31 20 26 20 30 20 26 20 | 0 \\ ..|1 & 0 & |
|00002db0| 31 20 26 20 32 20 26 20 | 33 20 5c 5c 20 0d 0a 32 |1 & 2 & |3 \\ ..2|
|00002dc0| 20 26 20 30 20 26 20 32 | 20 26 20 33 20 26 20 31 | & 0 & 2| & 3 & 1|
|00002dd0| 20 5c 5c 20 0d 0a 33 20 | 26 20 30 20 26 20 33 20 | \\ ..3 |& 0 & 3 |
|00002de0| 26 20 31 20 26 20 32 0d | 0a 5c 65 6e 64 7b 74 61 |& 1 & 2.|.\end{ta|
|00002df0| 62 75 6c 61 72 7d 0d 0a | 5c 71 75 61 64 20 5c 71 |bular}..|\quad \q|
|00002e00| 71 75 61 64 20 0d 0a 5c | 62 65 67 69 6e 7b 74 61 |quad ..\|begin{ta|
|00002e10| 62 75 6c 61 72 7d 7b 63 | 7c 63 63 63 63 7d 0d 0a |bular}{c||cccc}..|
|00002e20| 24 2b 24 20 26 20 30 20 | 26 20 31 20 26 20 32 20 |$+$ & 0 |& 1 & 2 |
|00002e30| 26 20 33 20 5c 5c 20 5c | 68 6c 69 6e 65 0d 0a 30 |& 3 \\ \|hline..0|
|00002e40| 20 26 20 30 20 26 20 31 | 20 26 20 32 20 26 20 33 | & 0 & 1| & 2 & 3|
|00002e50| 20 5c 5c 20 0d 0a 31 20 | 26 20 31 20 26 20 30 20 | \\ ..1 |& 1 & 0 |
|00002e60| 26 20 33 20 26 20 32 20 | 5c 5c 20 0d 0a 32 20 26 |& 3 & 2 |\\ ..2 &|
|00002e70| 20 32 20 26 20 33 20 26 | 20 30 20 26 20 31 20 5c | 2 & 3 &| 0 & 1 \|
|00002e80| 5c 20 0d 0a 33 20 26 20 | 33 20 26 20 32 20 26 20 |\ ..3 & |3 & 2 & |
|00002e90| 31 20 26 20 30 0d 0a 5c | 65 6e 64 7b 74 61 62 75 |1 & 0..\|end{tabu|
|00002ea0| 6c 61 72 7d 0d 0a 5c 6d | 65 64 73 6b 69 70 20 0d |lar}..\m|edskip .|
|00002eb0| 0a 5c 5d 0d 0a 0d 0a 5c | 62 65 67 69 6e 7b 65 78 |.\]....\|begin{ex|
|00002ec0| 61 6d 70 6c 65 7d 0d 0a | 5c 6c 61 62 65 6c 7b 42 |ample}..|\label{B|
|00002ed0| 43 48 20 63 6f 64 65 7d | 54 68 69 73 20 73 65 74 |CH code}|This set|
|00002ee0| 74 69 6e 67 20 70 72 6f | 76 69 64 65 73 20 74 68 |ting pro|vides th|
|00002ef0| 65 20 62 61 73 69 73 20 | 66 6f 72 20 74 68 65 0d |e basis |for the.|
|00002f00| 0a 42 6f 73 65 2d 43 68 | 61 75 64 68 75 72 69 2d |.Bose-Ch|audhuri-|
|00002f10| 48 6f 63 71 75 65 6e 67 | 68 65 6d 20 28 42 43 48 |Hocqueng|hem (BCH|
|00002f20| 29 20 43 6f 64 65 73 2e | 20 47 69 76 65 6e 20 74 |) Codes.| Given t|
|00002f30| 68 65 20 6d 65 73 73 61 | 67 65 20 77 6f 72 64 20 |he messa|ge word |
|00002f40| 24 25 0d 0a 28 61 5f 7b | 72 7d 2c 61 5f 7b 72 2d |$%..(a_{|r},a_{r-|
|00002f50| 31 7d 2c 2e 2e 2e 2c 61 | 5f 7b 32 7d 2c 61 5f 7b |1},...,a|_{2},a_{|
|00002f60| 31 7d 2c 61 5f 7b 30 7d | 29 5f 7b 32 7d 24 20 61 |1},a_{0}|)_{2}$ a|
|00002f70| 73 20 61 20 6e 75 6d 62 | 65 72 20 69 6e 20 62 61 |s a numb|er in ba|
|00002f80| 73 65 20 32 2c 20 61 73 | 73 6f 63 69 61 74 65 0d |se 2, as|sociate.|
|00002f90| 0a 74 68 65 20 70 6f 6c | 79 6e 6f 6d 69 61 6c 20 |.the pol|ynomial |
|00002fa0| 24 61 28 78 29 3d 61 5f | 7b 72 7d 78 5e 7b 72 7d |$a(x)=a_|{r}x^{r}|
|00002fb0| 2b 61 5f 7b 72 2d 31 7d | 78 5e 7b 72 2d 31 7d 2b |+a_{r-1}|x^{r-1}+|
|00002fc0| 5c 63 64 6f 74 20 5c 63 | 64 6f 74 20 5c 63 64 6f |\cdot \c|dot \cdo|
|00002fd0| 74 0d 0a 2b 61 5f 7b 32 | 7d 78 5e 7b 32 7d 2b 61 |t..+a_{2|}x^{2}+a|
|00002fe0| 5f 7b 31 7d 78 2b 61 5f | 7b 30 7d 24 20 69 6e 20 |_{1}x+a_|{0}$ in |
|00002ff0| 24 47 46 5f 7b 32 7d 5b | 78 5d 24 2e 20 41 20 63 |$GF_{2}[|x]$. A c|
|00003000| 6f 64 65 77 6f 72 64 20 | 0d 0a 5c 69 6e 64 65 78 |odeword |..\index|
|00003010| 7b 43 6f 64 65 20 77 6f | 72 64 40 43 6f 64 65 20 |{Code wo|rd@Code |
|00003020| 77 6f 72 64 7d 69 73 20 | 74 68 65 6e 20 67 65 6e |word}is |then gen|
|00003030| 65 72 61 74 65 64 20 62 | 79 20 74 68 65 20 66 6f |erated b|y the fo|
|00003040| 72 6d 75 6c 61 20 24 61 | 28 78 29 71 28 78 29 25 |rmula $a|(x)q(x)%|
|00003050| 0d 0a 5c 6c 69 6d 66 75 | 6e 63 7b 6d 6f 64 7d 32 |..\limfu|nc{mod}2|
|00003060| 24 2c 20 77 68 65 72 65 | 20 24 71 28 78 29 24 20 |$, where| $q(x)$ |
|00003070| 69 73 20 61 20 73 70 65 | 63 69 61 6c 6c 79 20 73 |is a spe|cially s|
|00003080| 65 6c 65 63 74 65 64 20 | 70 6f 6c 79 6e 6f 6d 69 |elected |polynomi|
|00003090| 61 6c 2e 0d 0a 0d 0a 43 | 6f 6e 73 69 64 65 72 20 |al.....C|onsider |
|000030a0| 74 68 65 20 47 61 6c 6f | 69 73 20 66 69 65 6c 64 |the Galo|is field|
|000030b0| 20 24 47 46 5f 7b 32 5e | 7b 34 7d 7d 3d 47 46 5f | $GF_{2^|{4}}=GF_|
|000030c0| 7b 31 36 7d 24 2e 20 4c | 65 74 20 24 5c 61 6c 70 |{16}$. L|et $\alp|
|000030d0| 68 61 20 24 20 62 65 20 | 61 20 70 72 69 6d 69 74 |ha $ be |a primit|
|000030e0| 69 76 65 0d 0a 65 6c 65 | 6d 65 6e 74 20 69 6e 20 |ive..ele|ment in |
|000030f0| 24 47 46 5f 7b 31 36 7d | 24 2c 20 73 6f 20 74 68 |$GF_{16}|$, so th|
|00003100| 61 74 20 74 68 65 20 6e | 6f 6e 7a 65 72 6f 20 65 |at the n|onzero e|
|00003110| 6c 65 6d 65 6e 74 73 20 | 6f 66 20 24 47 46 5f 7b |lements |of $GF_{|
|00003120| 31 36 7d 24 20 61 72 65 | 20 61 6c 6c 0d 0a 70 6f |16}$ are| all..po|
|00003130| 77 65 72 73 20 6f 66 20 | 24 5c 61 6c 70 68 61 20 |wers of |$\alpha |
|00003140| 24 2e 20 49 6e 20 70 61 | 72 74 69 63 75 6c 61 72 |$. In pa|rticular|
|00003150| 2c 20 74 68 69 73 20 70 | 72 6f 70 65 72 74 79 20 |, this p|roperty |
|00003160| 68 6f 6c 64 73 20 69 66 | 20 77 65 20 74 61 6b 65 |holds if| we take|
|00003170| 20 24 5c 61 6c 70 68 61 | 20 24 0d 0a 74 6f 20 62 | $\alpha| $..to b|
|00003180| 65 20 61 20 72 6f 6f 74 | 20 6f 66 20 74 68 65 20 |e a root| of the |
|00003190| 69 72 72 65 64 75 63 69 | 62 6c 65 20 70 6f 6c 79 |irreduci|ble poly|
|000031a0| 6e 6f 6d 69 61 6c 20 24 | 78 5e 7b 34 7d 2b 78 2b |nomial $|x^{4}+x+|
|000031b0| 31 24 2e 20 4c 65 74 20 | 24 6d 5f 7b 69 7d 28 78 |1$. Let |$m_{i}(x|
|000031c0| 29 24 20 62 65 0d 0a 74 | 68 65 20 6d 69 6e 69 6d |)$ be..t|he minim|
|000031d0| 61 6c 20 70 6f 6c 79 6e | 6f 6d 69 61 6c 20 6f 66 |al polyn|omial of|
|000031e0| 20 24 5c 61 6c 70 68 61 | 20 5e 7b 69 7d 24 2e 20 | $\alpha| ^{i}$. |
|000031f0| 49 66 20 24 71 28 78 29 | 3d 5c 6c 69 6d 66 75 6e |If $q(x)|=\limfun|
|00003200| 63 7b 6c 63 6d 7d 5b 25 | 0d 0a 6d 5f 7b 31 7d 28 |c{lcm}[%|..m_{1}(|
|00003210| 78 29 2c 6d 5f 7b 32 7d | 28 78 29 2c 2e 2e 2e 2c |x),m_{2}|(x),...,|
|00003220| 6d 5f 7b 32 74 7d 28 78 | 29 5d 24 2c 20 74 68 65 |m_{2t}(x|)]$, the|
|00003230| 6e 20 74 68 65 20 63 6f | 72 72 65 73 70 6f 6e 64 |n the co|rrespond|
|00003240| 69 6e 67 20 0d 0a 5c 69 | 6e 64 65 78 7b 42 43 48 |ing ..\i|ndex{BCH|
|00003250| 20 63 6f 64 65 40 42 43 | 48 20 63 6f 64 65 7d 42 | code@BC|H code}B|
|00003260| 43 48 20 63 6f 64 65 20 | 63 6f 72 72 65 63 74 73 |CH code |corrects|
|00003270| 20 61 74 20 6c 65 61 73 | 74 20 24 74 24 20 65 72 | at leas|t $t$ er|
|00003280| 72 6f 72 73 2e 0d 0a 0d | 0a 53 69 6e 63 65 20 24 |rors....|.Since $|
|00003290| 5c 61 6c 70 68 61 20 5e | 7b 34 7d 2b 5c 61 6c 70 |\alpha ^|{4}+\alp|
|000032a0| 68 61 20 2b 31 3d 30 24 | 2c 20 69 74 20 66 6f 6c |ha +1=0$|, it fol|
|000032b0| 6c 6f 77 73 20 74 68 61 | 74 20 24 30 5e 7b 32 7d |lows tha|t $0^{2}|
|000032c0| 3d 5c 6c 65 66 74 28 20 | 5c 61 6c 70 68 61 0d 0a |=\left( |\alpha..|
|000032d0| 5e 7b 34 7d 2b 5c 61 6c | 70 68 61 20 2b 31 5c 72 |^{4}+\al|pha +1\r|
|000032e0| 69 67 68 74 29 20 5e 7b | 32 7d 3d 24 20 24 5c 6c |ight) ^{|2}=$ $\l|
|000032f0| 65 66 74 28 20 5c 61 6c | 70 68 61 20 5e 7b 34 7d |eft( \al|pha ^{4}|
|00003300| 5c 72 69 67 68 74 29 20 | 5e 7b 32 7d 2b 5c 61 6c |\right) |^{2}+\al|
|00003310| 70 68 61 0d 0a 5e 7b 32 | 7d 2b 31 3d 5c 6c 65 66 |pha..^{2|}+1=\lef|
|00003320| 74 28 20 5c 61 6c 70 68 | 61 20 5e 7b 32 7d 5c 72 |t( \alph|a ^{2}\r|
|00003330| 69 67 68 74 29 20 5e 7b | 34 7d 2b 5c 61 6c 70 68 |ight) ^{|4}+\alph|
|00003340| 61 20 5e 7b 32 7d 2b 31 | 24 3b 20 68 65 6e 63 65 |a ^{2}+1|$; hence|
|00003350| 2c 20 24 25 0d 0a 6d 5f | 7b 31 7d 28 78 29 3d 6d |, $%..m_|{1}(x)=m|
|00003360| 5f 7b 32 7d 28 78 29 24 | 2e 20 42 79 20 74 68 65 |_{2}(x)$|. By the|
|00003370| 20 73 61 6d 65 20 72 65 | 61 73 6f 6e 69 6e 67 2c | same re|asoning,|
|00003380| 20 24 6d 5f 7b 32 7d 28 | 78 29 3d 6d 5f 7b 34 7d | $m_{2}(|x)=m_{4}|
|00003390| 28 78 29 3d 6d 5f 7b 38 | 7d 28 78 29 24 2e 0d 0a |(x)=m_{8|}(x)$...|
|000033a0| 4c 69 6b 65 77 69 73 65 | 2c 20 24 6d 5f 7b 33 7d |Likewise|, $m_{3}|
|000033b0| 28 78 29 3d 28 78 2d 5c | 61 6c 70 68 61 20 5e 7b |(x)=(x-\|alpha ^{|
|000033c0| 33 7d 29 28 78 2d 5c 61 | 6c 70 68 61 20 5e 7b 36 |3})(x-\a|lpha ^{6|
|000033d0| 7d 29 28 78 2d 5c 61 6c | 70 68 61 20 5e 7b 31 32 |})(x-\al|pha ^{12|
|000033e0| 7d 29 28 78 2d 5c 61 6c | 70 68 61 0d 0a 5e 7b 39 |})(x-\al|pha..^{9|
|000033f0| 7d 29 3d 78 5e 7b 34 7d | 2b 78 5e 7b 33 7d 2b 78 |})=x^{4}|+x^{3}+x|
|00003400| 5e 7b 32 7d 2b 78 2b 31 | 24 3b 20 68 65 6e 63 65 |^{2}+x+1|$; hence|
|00003410| 2c 20 61 20 64 6f 75 62 | 6c 65 20 65 72 72 6f 72 |, a doub|le error|
|00003420| 2d 63 6f 72 72 65 63 74 | 69 6e 67 20 63 6f 64 65 |-correct|ing code|
|00003430| 20 69 73 0d 0a 67 65 6e | 65 72 61 74 65 64 20 62 | is..gen|erated b|
|00003440| 79 20 0d 0a 5c 5b 0d 0a | 71 28 78 29 3d 25 0d 0a |y ..\[..|q(x)=%..|
|00003450| 5c 6c 69 6d 66 75 6e 63 | 7b 6c 63 6d 7d 5b 6d 5f |\limfunc|{lcm}[m_|
|00003460| 7b 31 7d 28 78 29 2c 6d | 5f 7b 32 7d 28 78 29 2c |{1}(x),m|_{2}(x),|
|00003470| 6d 5f 7b 33 7d 28 78 29 | 2c 6d 5f 7b 34 7d 28 78 |m_{3}(x)|,m_{4}(x|
|00003480| 29 5d 5c 6c 69 6d 66 75 | 6e 63 7b 6d 6f 64 7d 25 |)]\limfu|nc{mod}%|
|00003490| 0d 0a 32 3d 78 5e 7b 38 | 7d 2b 78 5e 7b 37 7d 2b |..2=x^{8|}+x^{7}+|
|000034a0| 78 5e 7b 36 7d 2b 78 5e | 7b 34 7d 2b 31 20 0d 0a |x^{6}+x^|{4}+1 ..|
|000034b0| 5c 5d 0d 0a 5c 62 69 67 | 73 6b 69 70 0d 0a 5c 65 |\]..\big|skip..\e|
|000034c0| 6e 64 7b 65 78 61 6d 70 | 6c 65 7d 0d 0a 0d 0a 5c |nd{examp|le}....\|
|000034d0| 73 75 62 73 65 63 74 69 | 6f 6e 7b 5c 20 52 65 6c |subsecti|on{\ Rel|
|000034e0| 61 74 65 64 20 74 6f 70 | 69 63 73 7d 0d 0a 0d 0a |ated top|ics}....|
|000034f0| 5c 68 79 70 65 72 72 65 | 66 7b 53 6f 6c 76 69 6e |\hyperre|f{Solvin|
|00003500| 67 20 45 71 75 61 74 69 | 6f 6e 73 7d 7b 7d 7b 7d |g Equati|ons}{}{}|
|00003510| 7b 44 4d 31 32 2d 31 2e | 74 65 78 23 49 6e 74 65 |{DM12-1.|tex#Inte|
|00003520| 67 65 72 20 73 6f 6c 75 | 74 69 6f 6e 73 7d 0d 0a |ger solu|tions}..|
|00003530| 0d 0a 5c 68 79 70 65 72 | 72 65 66 7b 49 6e 74 65 |..\hyper|ref{Inte|
|00003540| 67 65 72 73 20 4d 6f 64 | 75 6c 6f 20 6d 7d 7b 7d |gers Mod|ulo m}{}|
|00003550| 7b 7d 7b 44 4d 31 32 2d | 32 2e 74 65 78 23 49 6e |{}{DM12-|2.tex#In|
|00003560| 74 65 67 65 72 73 20 6d | 6f 64 75 6c 6f 20 6d 7d |tegers m|odulo m}|
|00003570| 0d 0a 0d 0a 5c 68 79 70 | 65 72 72 65 66 7b 4f 74 |....\hyp|erref{Ot|
|00003580| 68 65 72 20 53 79 73 74 | 65 6d 73 20 4d 6f 64 75 |her Syst|ems Modu|
|00003590| 6c 6f 20 6d 7d 7b 7d 7b | 7d 7b 44 4d 31 32 2d 33 |lo m}{}{|}{DM12-3|
|000035a0| 2e 74 65 78 23 4d 61 74 | 72 69 63 65 73 20 6d 6f |.tex#Mat|rices mo|
|000035b0| 64 75 6c 6f 20 6d 7d 0d | 0a 0d 0a 5c 68 79 70 65 |dulo m}.|...\hype|
|000035c0| 72 72 65 66 7b 4c 69 6e | 65 61 72 20 50 72 6f 67 |rref{Lin|ear Prog|
|000035d0| 72 61 6d 6d 69 6e 67 7d | 7b 7d 7b 7d 7b 44 4d 31 |ramming}|{}{}{DM1|
|000035e0| 32 2d 35 2e 74 65 78 23 | 4c 69 6e 65 61 72 20 70 |2-5.tex#|Linear p|
|000035f0| 72 6f 67 72 61 6d 6d 69 | 6e 67 7d 0d 0a 0d 0a 5c |rogrammi|ng}....\|
|00003600| 68 79 70 65 72 72 65 66 | 7b 45 78 65 72 63 69 73 |hyperref|{Exercis|
|00003610| 65 73 20 61 6e 64 20 53 | 6f 6c 75 74 69 6f 6e 73 |es and S|olutions|
|00003620| 7d 7b 7d 7b 7d 7b 44 4d | 31 32 2d 36 2e 74 65 78 |}{}{}{DM|12-6.tex|
|00003630| 23 45 78 65 72 63 69 73 | 65 73 7d 0d 0a 0d 0a 5c |#Exercis|es}....\|
|00003640| 72 75 6c 65 7b 30 2e 36 | 37 69 6e 7d 7b 30 2e 30 |rule{0.6|7in}{0.0|
|00003650| 31 69 6e 7d 0d 0a 0d 0a | 5c 68 79 70 65 72 72 65 |1in}....|\hyperre|
|00003660| 66 7b 5c 46 52 41 4d 45 | 7b 69 74 62 70 46 7d 7b |f{\FRAME|{itbpF}{|
|00003670| 30 2e 35 32 37 35 69 6e | 7d 7b 30 2e 33 33 39 39 |0.5275in|}{0.3399|
|00003680| 69 6e 7d 7b 30 2e 30 35 | 31 39 69 6e 7d 7b 7d 7b |in}{0.05|19in}{}{|
|00003690| 7d 7b 69 6e 64 65 78 2e | 77 6d 66 7d 7b 5c 73 70 |}{index.|wmf}{\sp|
|000036a0| 65 63 69 61 6c 25 0d 0a | 7b 6c 61 6e 67 75 61 67 |ecial%..|{languag|
|000036b0| 65 20 22 53 63 69 65 6e | 74 69 66 69 63 20 57 6f |e "Scien|tific Wo|
|000036c0| 72 64 22 3b 74 79 70 65 | 20 22 47 52 41 50 48 49 |rd";type| "GRAPHI|
|000036d0| 43 22 3b 64 69 73 70 6c | 61 79 20 22 50 49 43 54 |C";displ|ay "PICT|
|000036e0| 22 3b 76 61 6c 69 64 2d | 66 69 6c 65 0d 0a 22 46 |";valid-|file.."F|
|000036f0| 22 3b 77 69 64 74 68 20 | 30 2e 35 32 37 35 69 6e |";width |0.5275in|
|00003700| 3b 68 65 69 67 68 74 20 | 30 2e 33 33 39 39 69 6e |;height |0.3399in|
|00003710| 3b 64 65 70 74 68 20 30 | 2e 30 35 31 39 69 6e 3b |;depth 0|.0519in;|
|00003720| 6f 72 69 67 69 6e 61 6c | 2d 77 69 64 74 68 0d 0a |original|-width..|
|00003730| 33 36 2e 38 37 35 70 74 | 3b 6f 72 69 67 69 6e 61 |36.875pt|;origina|
|00003740| 6c 2d 68 65 69 67 68 74 | 20 32 32 2e 35 36 32 35 |l-height| 22.5625|
|00003750| 70 74 3b 63 72 6f 70 6c | 65 66 74 20 22 30 22 3b |pt;cropl|eft "0";|
|00003760| 63 72 6f 70 74 6f 70 20 | 22 31 22 3b 63 72 6f 70 |croptop |"1";crop|
|00003770| 72 69 67 68 74 0d 0a 22 | 31 22 3b 63 72 6f 70 62 |right.."|1";cropb|
|00003780| 6f 74 74 6f 6d 20 22 30 | 22 3b 66 69 6c 65 6e 61 |ottom "0|";filena|
|00003790| 6d 65 20 27 69 6e 64 65 | 78 2e 77 6d 66 27 3b 66 |me 'inde|x.wmf';f|
|000037a0| 69 6c 65 2d 70 72 6f 70 | 65 72 74 69 65 73 20 22 |ile-prop|erties "|
|000037b0| 58 4e 50 45 55 22 3b 7d | 7d 7d 7b 7d 7b 7d 7b 25 |XNPEU";}|}}{}{}{%|
|000037c0| 0d 0a 44 4d 49 6e 64 65 | 78 2e 74 65 78 23 4d 61 |..DMInde|x.tex#Ma|
|000037d0| 74 68 20 49 6e 64 65 78 | 7d 5c 71 75 61 64 20 7b |th Index|}\quad {|
|000037e0| 5c 73 6d 61 6c 6c 20 49 | 6e 64 65 78 20 65 6e 74 |\small I|ndex ent|
|000037f0| 72 69 65 73 3a 20 5c 68 | 79 70 65 72 72 65 66 7b |ries: \h|yperref{|
|00003800| 41 70 70 6c 69 65 64 20 | 6d 6f 64 65 72 6e 0d 0a |Applied |modern..|
|00003810| 61 6c 67 65 62 72 61 7d | 7b 7d 7b 7d 7b 44 4d 49 |algebra}|{}{}{DMI|
|00003820| 6e 64 65 78 2e 74 65 78 | 23 41 70 70 6c 69 65 64 |ndex.tex|#Applied|
|00003830| 20 6d 6f 64 65 72 6e 20 | 61 6c 67 65 62 72 61 7d | modern |algebra}|
|00003840| 2c 20 5c 68 79 70 65 72 | 72 65 66 7b 43 6f 6e 67 |, \hyper|ref{Cong|
|00003850| 72 75 65 6e 63 65 7d 7b | 7d 7b 7d 7b 25 0d 0a 44 |ruence}{|}{}{%..D|
|00003860| 4d 49 6e 64 65 78 2e 74 | 65 78 23 43 6f 6e 67 72 |MIndex.t|ex#Congr|
|00003870| 75 65 6e 63 65 7d 2c 20 | 5c 68 79 70 65 72 72 65 |uence}, |\hyperre|
|00003880| 66 7b 50 6f 6c 79 6e 6f | 6d 69 61 6c 73 7d 7b 7d |f{Polyno|mials}{}|
|00003890| 7b 7d 7b 44 4d 49 6e 64 | 65 78 2e 74 65 78 23 50 |{}{DMInd|ex.tex#P|
|000038a0| 6f 6c 79 6e 6f 6d 69 61 | 6c 73 7d 25 0d 0a 2c 20 |olynomia|ls}%.., |
|000038b0| 5c 68 79 70 65 72 72 65 | 66 7b 53 6f 6c 76 65 7d |\hyperre|f{Solve}|
|000038c0| 7b 7d 7b 7d 7b 44 4d 49 | 6e 64 65 78 2e 74 65 78 |{}{}{DMI|ndex.tex|
|000038d0| 23 53 6f 6c 76 65 7d 7d | 0d 0a 0d 0a 5c 65 6e 64 |#Solve}}|....\end|
|000038e0| 7b 64 6f 63 75 6d 65 6e | 74 7d 0d 0a             |{documen|t}..    |
+--------+-------------------------+-------------------------+--------+--------+