Results 1 to 8 of 8
Like Tree3Thanks
  • 1 Post By a tutor
  • 1 Post By a tutor
  • 1 Post By Deveno

Math Help - Solving modular congruence

  1. #1
    Member
    Joined
    Nov 2011
    Posts
    87

    Smile Solving modular congruence

    Hi everyone!

    Does anyone perhaps know how to solve this:

    7117 = x (mod 29)

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

    Thank you all
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Solving modular congruence

    Yes.

    7^{28} \equiv 1  (\mod 29)

    7^{4\times 28+5} \equiv 7^5 (\mod 29)
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2011
    Posts
    87

    Re: Solving modular congruence

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Solving modular congruence

    7^x\equiv 7 \text{ or } 21 \mod(28)

    I can't say anything more general at the moment as I've forgotten most of the little number theory that I once knew.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Solving modular congruence

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

    72 = 49 = 21 (mod 28)
    73 = 7 (mod 28)

    so:

    74 = 21 (mod 28)
    75 = 7 (mod 28)

    etc.

    that is: 72n = 21
    72n+1 = 7

    hence 7117 = 7 (mod 28) since 117 is odd.
    Thanks from Nora314
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2011
    Posts
    87

    Re: Solving modular congruence

    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!!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    66

    Re: Solving modular congruence

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

    Multiply this through by 157.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Solving modular congruence

    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving modular inequality
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 11th 2010, 10:00 AM
  2. help with modular congruence
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 23rd 2009, 08:33 PM
  3. Replies: 0
    Last Post: May 28th 2009, 10:07 AM
  4. Solving a congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 15th 2008, 10:10 AM

Search Tags


/mathhelpforum @mathhelpforum