Question: I have a modular arithmetic question. can you show me the process of solving 24^43 = 14 (mod 85) by using Fermat's Little Theorem and

I have a modular arithmetic question. can you show me the process of solving 24^43 = 14 (mod 85) by using Fermat's Little Theorem and Chinese Remainder Theorem? (like this link solves it: https://www.quora.com/How-do-I-solve-2-35-mod-561)

Obviously, using FLT, since 85 = 17 *5, 24^16 = 1 (mod 17) and 24^4 = 1 (mod 5).

Then I got 24^(16*2 + 11) = 8 (mod 17) and 24^(4*10 + 3) = 4 (mod 5). (perhaps my calculation was wrong here?... please check).

Now using Chinese Remainder,

x = 17k +8 for the first

for the second, x = 4 (mod 5)

17k + 8 = 4 (mod 5)

17k = -4 (mod 5)

17k = 51 (mod 5)

k = 3 (mod 5)

k = 5j + 3

so backwards,

x = 17(5j + 3) + 8

= 85j + 59

so i get 59, not 14..

Would you please show me the correct steps of solving this?

Thank you so much

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Mathematics Questions!