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,
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.