Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

Solving this congruence for all values of x

  • 10-11-2010 7:43pm
    #1
    Moderators, Education Moderators, Motoring & Transport Moderators Posts: 7,396 Mod ✭✭✭✭


    I have the following congruence:

    [latex] 9x \equiv 12 (mod 15)[/latex]

    OK, so that seems fine. The gcd(9,15) is 3, and 3 divides 12 so there should be three mutually incongruent solutions.

    I'm not going to post up everything I did, because it's quite long, but I used Euclid's Algorithm to express the gcd(12, 15) in the form

    gcd(12,15) = s(12) + w(15), and I evaluated s to be 2.

    The first solution is given by
    [latex]x_0 = \displaystyle s(\frac{12}{gcd(9,15)})[/latex], which gives me 8.

    To find the next solutions, I use the fact that every solution looks like

    [latex] x = x_0 - y(\frac{15}{gcd(9,15)})[/latex], y = 1, ..., gcd(9,15)-1 (in this case, y is 1 and 2).

    Putting in y=1 and y=2, I get two more solutions, 3 and -2.

    Is this correct? The -2 looks wrong, even though it technically works.
    But putting the congruence into this website, http://www.math.temple.edu/~renault/cryptology/congruences.html
    gives 13, 8 and 3 as the answers. How did they get 13? Did I go wrong somewhere?

    Sorry for the long post and the sloppy notation.


Comments

  • Registered Users, Registered Users 2 Posts: 1,595 ✭✭✭MathsManiac


    When you're operating mod 15, then -2 and 13 are the same thing.

    So your answers are consistent with the ones given on the website.

    Does that answer your question?


  • Moderators, Education Moderators, Motoring & Transport Moderators Posts: 7,396 Mod ✭✭✭✭**Timbuk2**


    When you're operating mod 15, then -2 and 13 are the same thing.

    So your answers are consistent with the ones given on the website.

    Does that answer your question?

    Thank you! I should have realised that!

    That answers my question perfectly, thanks! I'm relieved - I thought I had gone seriously wrong somewhere, because I expected 13 to be my first value.


  • Closed Accounts Posts: 6,081 ✭✭✭LeixlipRed


    Remember a congruence like this is a linear diophantine equation. So if the gcd divides into the remainder that means there's infinitely many solutions to the LDE and a finite number of these solutions that lie inside the "window" of our mod n.


Advertisement