Thread: Modular math

  1. 09-30-2003 #1
    PJYelton
    PJYelton is offline
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Modular math

    I’m working on an algorithm where a section of it appears to boil down to a modular arithmetic problem, but unfortunately my modular math sucks. Does anyone here know how to solve modular equations?

    Basically this is what I want. As an example, say I’m trying to solve for x in the equation (4x-6)%7=0. Doing a little trial and error, you can find out that x=5+7n where n can be any integer>=zero, so 5, 12, 19 etc are all answers. But when dealing with big numbers, then trial and error obviously can’t be done in my algorithm. So does anyone know how to solve the generic equation (Ax-B)%C=0?
  2. 09-30-2003 #2
    Clyde
    Clyde is offline
    The Earth is not flat. Clyde's Avatar
    Join Date
    Mar 2002
    Posts
    1,403
    I don't know much modular maths but can't you just use (Ax-B)/C = n

    -> x = (Cn +B)/A
  3. 09-30-2003 #3
    PJYelton
    PJYelton is offline
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Oops, don't think I was completely clear, all variables (A,B,C,x,n) must be integers. The problem with solving something like (Ax-B)/C = n and then just plugging values for n and solving for x is that x can only be an integer. So like in my above example, (4x-6)/7=n, if n=0 then x=3/2, if n=1 then x=13/4, but if n=2 then we are good since x=5. But the only way to find out which values of n produce an integer that I know of is by doing brute force, which is out of the question if the numbers are say over a million.
    Last edited by PJYelton; 09-30-2003 at 01:30 PM.
  4. 09-30-2003 #4
    confuted
    confuted is offline
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Isn't solving for integer solutions known as "Diophantine equations"?
    Away.
  5. 09-30-2003 #5
    Zach L.
    Zach L. is offline
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    More specifically, linear Diophantine equations (in this particular case). Just a quick note, in "x=5+7n", n need not be positive; it only needs to be an integer.

    As for how to solve it, I'm not entirely sure. I am relatively sure, however, that it is non-trivial at best. I know that www.generation5.org has a GA solver for linear Diophantine equations, you might want to look at that.
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.
  6. 10-01-2003 #6
    PJYelton
    PJYelton is offline
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Bah, I had no idea this would turn out to be such a pain... thanks all, guess I 'll get studying on Diophantine equations
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Math
    By knightjp in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 04-01-2009, 05:36 PM
  2. Help with C++ Math
    By aonic in forum C++ Programming
    Replies: 4
    Last Post: 01-29-2005, 04:40 AM
  3. Math Header?
    By Rune Hunter in forum C++ Programming
    Replies: 26
    Last Post: 09-17-2004, 06:39 AM
  4. toughest math course
    By axon in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-28-2003, 10:06 PM
  5. Modular Division problem
    By Malek in forum C++ Programming
    Replies: 7
    Last Post: 05-24-2003, 06:08 PM