Since

, we have that

By Fermat's little theorem, and the fact that

, we know that


so we have

Consider the first case. By Fermat's little theorem, we know that

so if we were to raise

to the

th power such that

we would need to choose

such that

(because

). We can find such an

by applying the Euclidean algorithm:



which makes

the inverse of 5 modulo 16, and so

.
Now,






Similarly, we can look for

such that

. Apply the Euclidean algorithm:




so that

is also the inverse of 7 modulo 30.
And similarly,
![x^7\equiv3\mod{31}[/ex] [tex]\implies (x^7)^{13}\equiv3^{13}\mod{31}](https://tex.z-dn.net/?f=x%5E7%5Cequiv3%5Cmod%7B31%7D%5B%2Fex%5D%20%5Btex%5D%5Cimplies%20%28x%5E7%29%5E%7B13%7D%5Cequiv3%5E%7B13%7D%5Cmod%7B31%7D)
Decomposing the power of 3 in a similar fashion, we have




So we have two linear congruences,

and because

, we can use the Chinese remainder theorem to solve for

.
Suppose

. Then modulo 17, we have

but we want to obtain

. So let's assume

, so that modulo 17 this reduces to

Using the Euclidean algorithm:





we find that

is the inverse of 14 modulo 17, and so multiplying by 12, we guarantee that we are left with 12 modulo 17:

To satisfy the second condition that

, taking

modulo 31 gives

To get this remainder to be 24, we first multiply by the inverse of 17 modulo 31, then multiply by 24. So let's find

such that

. Euclidean algorithm:


and so on - we've already done this. So

is the inverse of 17 modulo 31. Now, we take

as required. This means the congruence

is satisfied by

We want

, so just subtract as many multples of 527 from 8580 until this occurs.