1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Solving a System of Congruences with A Changing Modulus
  1. Solving Congruences (Replies: 2)

  2. Congruence Solving (Replies: 6)

Loading...