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

- Taken mod 5, the second term vanishes and
. Multiply by the inverse of 4 mod 5 (4), then by 2.

- Taken mod 7, the first term vanishes and
. Multiply by the inverse of 2 mod 7 (4), then by 6.


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 