Thread: Solving modular congruence

Hi everyone!

Does anyone perhaps know how to solve this:

7¹¹⁷ = x (mod 29)

what would x be? Can I use Fermat's little theorem somehow?

Thank you all

Yes.

Hi there! Thanks for the answer, I managed to solve it with that info , would you mind if I asked another question?

How would I solve that problem if in the question, instead of mod 29, we had mod 28. 28 is not a prime number, so I can't use Fermat's little theorem. Do you perhaps know?

I can't say anything more general at the moment as I've forgotten most of the little number theory that I once knew.

basically, you look at powers of 7 until you notice a cycle (and there will be a cycle, since there are only 28 congruence classes the powers of 7 can land on).

7² = 49 = 21 (mod 28)
7³ = 7 (mod 28)

so:

7⁴ = 21 (mod 28)
7⁵ = 7 (mod 28)

etc.

that is: 7²ⁿ = 21
7²ⁿ⁺¹ = 7

hence 7¹¹⁷ = 7 (mod 28) since 117 is odd.

Thanks for the answer! That was a very cool way to solve it I worked through it and I understand, now I will use that for similar exercises.

Can I ask another question?

How would you solve 110x = 157 (mod 273)

The one method I know for solving these kind of things is: if a = b (mod m), than a - b must be divisible by m. So here a = 110 x and b = 157, so I could make a table with different x-value and check which ones when inserted into 110x - 157 are divisible by 273, but this would seem to take too long, since I would have to try 273 different x-values?

In the answer key to the question I see that they used the Euclidean algorithm to find gcd(273, 110) I understand how to do that. Than they work backwards from the Euclidean algorithm to get the number - 67. I understand that too. But than it stops making sense for me. Could you explain to me where to go from there?

Thank you so so so very much for all your help!!

I imagine you arrived at 27 x 273 - 67 x 110 = 1.

Multiply this through by 157.

the euclidean algorithm for finding gcd(a,b) is actually a way to find a^-1 (mod b) (if it exists).

for suppose gcd(a,b) = 1 <--this is important.

using the euclidean algortihm, we find integers r,s with:

ar + bs = 1

take both sides mod b:

(a mod b)(r mod b) + (b mod b)(s mod b) = 1 (mod b)

the b mod b term is, of course, 0, which "knocks out" the s term, as well, leaving:

(a mod b)(r mod b) = 1 (mod b).

so a^-1 (mod b) is r (mod b).

for example:

we want to solve:

3x = 14 (mod 22)

gcd(3,22) = 1.

we do our euclidean magic thing, and get:

(-7)(3) + (1)(22) = 1 <--so r = -7, and s = 1. but who cares about s? seriously? begone! we only care about r!

so, what is -7 (mod 22)? it's....uh....wait a minute....15!

so now we multiply through by 15:

45x = 210 (mod 22)

reduce everything mod 22:

1x = x = 12 (mod 22) (45 = 1 + 44, and 44 = 2*22, 210 = 12 + 198 and 198 = 22*9).

woah! magic!