3 Solve a x11 13 mod 35 b x7 11 mod 63 c x5 3 mod 64 Solutio

3) Solve a) x^11 13 (mod 35). b) x^7 11 (mod 63). c) x^5 3 (mod 64).

(a)

x¹¹=13 (mod 35)

35 = 5 * 7

Then, 13 = 6(mod 7) and 13 = 3(mod 5)

Thus, we solve x^11 = 6(mod 7) and x^11 = 3(mod 5)

As 5 and 7 are both prime,

for 5, x^4 = 1(mod 5) for x not equal to 0

Then, x^11 = x^(12-1) = x^12 x^-1 = (x^4)^3 x^-1 = 1 * x^-1 = x^-1

Then, if x^-1 = 3(mod 5), note that 2*3 = 1(mod 5), so 2^-1 = 3(mod 5)

For 7, x^6 = 1(mod 7)

Thus, x^11 = (x^6)^2 * x^-1 = 1 * x^-1 = x^-1

Then, if x^-1 = 6(mod 7), as 6 = 7-1, 6^-1 = 6(mod 7)

To prove, 6*6 = 36(mod 7) = 1(mod 7)

Thus, our solution is x = 6(mod 7) and x = 2(mod 5)

As our numbers are large, we can simply start with x=6(mod 7) and find which x = 2(mod 5)

We consider 6, 6+7, 6+7*2, 6+7*3, and 6+7*4

6 = 1(mod 5)

13 = 3(mod 5)

20 = 0(mod 5)

27 = 2(mod 5) (we can stop here if we want)

34 = 4(mod 5)

Thus, our answer is 27

I verified this result below by calculating 27^11(mod 35) - note the 11 entries.

(b)

Next, we solve x^7 = 11(mod 63)

63 = 3^2*7 = 9*7; 11 = 4(mod 7) and 11 = 2(mod 9)

Let\'s start with 7.

For x not equal to 0, x^6 = 1(mod 7)

Thus, x^7 = x^(6+1)=x^6*x^1=1*x = x

Thus, x = 4(mod 7)

For 2(mod 9), note that 2 and 9 are relatively prime.

For p^2, x^(p(p-1)) = 1(mod p^2) for all x relatively prime to p.

As p = 3, p(p-1) = 3(3-1) = 3*2 = 6

Thus, once again, we will have x^7 = x^6*x = 1x = x

Thus, x = 2(mod 9)

Obviously, x = 2(mod 9) and x = 4(mod 7) has our original number as the solution, 11

Once again, we will check the answer via multiplication.

(c)

similarlly

x⁵=3(mod 64)