Please show your work
2 answers:
You might be interested in
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.
By Fermat's little theorem, and the fact that
so we have
Consider the first case. By Fermat's little theorem, we know that
so if we were to raise
we would need to choose
which makes
Now,
Similarly, we can look for
so that
And similarly,
Decomposing the power of 3 in a similar fashion, we have
So we have two linear congruences,
and because
Suppose
but we want to obtain
Using the Euclidean algorithm:
we find that
To satisfy the second condition that
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
and so on - we've already done this. So
as required. This means the congruence
We want