Solve the following equations: (a) x^11=13 mod 35 (b) x^5=3 mod 64

a.

By Fermat's little theorem, we have

5 and 7 are both prime, so and . By Euler's theorem, we get

Now we can use the Chinese remainder theorem to solve for . Start with

b.

We have , so by Euler's theorem,

Now, raising both sides of the original congruence to the power of 6 gives

Then multiplying both sides by gives

so that is the inverse of 25 mod 64. To find this inverse, solve for in . Using the Euclidean algorithm, we have

64 = 2*25 + 14

25 = 1*14 + 11

14 = 1*11 + 3

11 = 3*3 + 2

3 = 1*2 + 1

=> 1 = 9*64 - 23*25

so that .

So we know

Squaring both sides of this gives

and multiplying both sides by tells us

Use the Euclidean algorithm to solve for .

64 = 3*17 + 13

17 = 1*13 + 4

13 = 3*4 + 1

=> 1 = 4*64 - 15*17

so that , and so

me

step-by-step explanation: