85 Use Fermats theorem to find a number a between 0 and 72 w

8.5 Use Fermat’s theorem to find a number a between 0 and 72 with a congruent to 9794 modulo 73.

It is given with modulo 73. 73 is a prime number. prime number means whole numer factors are one and itself.

According to Fermat\'s theorem:

a^p = a (mod p)

a) a = 9^794 (mod 73)

73 is prime, we we want to break up the exponent 794 into a form of 73*q + r.

794 = 73 * 10 + 64

So we have:

a = 9 ^ (73*10 + 64) = (9 ^ 73)^10 * 9^64 (mod 73)

By Fermat\'s theorem, 9^73 = 9 (mod 73). This gives us:

9^10 * 9^64 = 9^74 = 9^73 * 9 (mod 73)

Again, use Fermat\'s theorem and we get:

a = 9*9 = 81 = 8 (mod 73)

So a = 8 (mod 73)

b) x^86 = 6 (mod 29)

29 is prime, so we use the same process. Break up the exponent into the form of 29*q + r:

x ^ (29*2 + 28) = (x^29)^2 * x^28 = x^2 * x^28 = x^30 = x^29 * x = x^2 (mod 29)

x^2 = 6 (mod 29)

Notice: 6 + 29 = 35 = 35 + 29 = 64 (mod 29)

So, x^2 = 6 = 64 (mod 29).

So our two solutions are x = 8 (mod 29) and x = -8 = 21 (mod 29).

c) x^39 = 3 (mod 13)

By following the same procedure :

x^39 = (x^13)^3 = x^3 (mod 13)

x^3 = 3 (mod 13)

This is small enough for trial and error:

1^3 = 1

2^3 = 8

3^3 = 27 = 1 (mod 13)

4^3 = 64 = 12 (mod 13)

5^3 = 25 * 5 = 8 (mod 13)

6^3 = 36 * 6 = 10 * 6 = 8 (mod 13)

7^3 = 49 * 7 = 10 * 7 = 14 * 5 = 5 (mod 13)

8^3 = 64 * 8 = 12 * 8 = 6 * 16 = 6 * 3 = 18 = 5 (mod 13)

9^3 = (3^2)^3 = 1 (mod 13)

10^3 = (2*5)^3 = 2^3 * 5^3 = 8 * 8 = 64 = 12 (mod 13)

11^3 = 121 * 11 = 4 * 11 = 2 * 22 = 2 * 9 = 18 = 5 (mod 13)

12^3 = (3*4)^3 = 3^3 * 4^3 = 1 * 12 = 12 (mod 13)

So this has no solution.