Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a System of Congruences with A Changing Modulus

  1. Jun 11, 2007 #1
    I'm working on some basic number theory. I came across an idea and I'm having trouble finding a general solution.

    A == X mod (L-k)
    k^2 == Y mod (L-k)

    It is the equivalent of:
    ( k^2 - A ) / ( L - k ) = integer

    A and L are two different pre-chosen numbers. I know L-k is a prime number, I just don't know which prime number from L-1 to 2. Is there a way to find a value for k such that X=Y?

    An example is A=129 L=130.
    I used my calculator to find k=99.
    A=1613 L=1940 k=333

    I also used the quadratic formula to find a lower bound

    [ 4L - sqrt ( (4L)^2 - 4( 2(L^2) + A ) ) ] / 2

    I have found the greater:

    ( k^2 – A ) / ( L – k ) + 2k

    Becomes, the less accurate the lower bound is.

    I have tried to apply solving systems of congruences but the method was for linear equations. And the changing modulus made it even harder.

    Also, when you derive an equation from a previously proven equation, do you have to prove the new equation?

    I have a copy of Gareth Jones and Mary Jones “Elementary Number Theory” and George Andrews “Number Theory.” Maybe you can point me to something I missed.
  2. jcsd
  3. Jun 11, 2007 #2
    I realize there is an easy algebraic equation for the remainder of the linear congruence, but for the quadratic congruence I don't recognize any pattern other than the standard 2n-1 from the series for calculating the square of a number.
  4. Jun 17, 2007 #3
    I am not sure why L-k must be a prime but if that is what you need then OK. If A is not pre-selected the problem is trite. Simply subtract any prime from L to get k and then select A = = k^2 mod L-k. But the other way around, i.e. preselecting A is more of a problem. I suggest getting a table of quadratic residues of primes and simply checking first if A == a quadratic residue. The lower primes are more apt to make A == a residue. Once you find A == a residue, say for prime = 31 as in your first example, you have your value for L-k!
  5. Jun 28, 2007 #4
    Opps I forgot that k relates both k^2 and L-k
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook