Find an integer x such that 0< =x< 527 and x^37===3 mod 527

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.

21

step-by-step explanation:

21-4

The second and fourth answer are correct