Solve the following congruence equations for X a) 8x = 1(mod 13) b) 8x = 4(mod 13) c) 99x = 5(mod 13)

Accepted Solution

Answer:a) 5+13k  where k is integerb) 20+13k where k is integerc)12+13k where k is integer Step-by-step explanation:(a)[tex]8x \equiv 1 (mod 13) \text{ means } 8x-1=13k[/tex].8x-1=13kSubtract 13k on both sides:8x-13k-1=0Add 1 on both sides:8x-13k=1I'm going to use Euclidean Algorithm.13=8(1)+58=5(1)+35=3(1)+23=2(1)+1Now backwards through the equations:3-2=13-(5-3)=13-5+3=1(8-5)-5+(8-5)=12(8)-3(5)=12(8)-3(13-8)=15(8)-3(13)=1So compare this to:8x-13k=1We see that x is 5 while k is 3.Anyways 5 is a solution or 5+13k is a solution where k is an integer.b)[tex]8x \equiv 4 (mod 13)[/tex]8x-4=13kSubtract 13k on both sides:8x-13k-4=0Add 4 on both sides:8x-13k=4We got this from above:5(8)-3(13)=1If we multiply both sides by 4 we get:8(20)-13(12)=4So x=20 and 20+13k is also a solution where k is an integer.c)[tex]99x \equiv 5 (mod 13)[/tex99x-5=13kSubtract 13k on both sides:99x-13k-5=0Add 5 on both sides:99x-13k=5Using Euclidean Algorithm:99=13(7)+813=8(1)+5Go back through the equations:13-8=513-(99-13(7))=58(13)-99=599(-1)+8(13)=5Compare this to 99x-13k=5 and see that x=-1 or -1+13=12 or 12+13k is a solution where k is an integer.