|Jun11-07, 12:48 PM||#1|
Solving a System of Congruences with A Changing Modulus
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.
|Jun11-07, 04:58 PM||#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.
|Jun17-07, 07:56 AM||#3|
|Similar Threads for: Solving a System of Congruences with A Changing Modulus|
|Solving quadratic congruences||Calculus & Beyond Homework||1|
|Quadratic congruences with prime modulus||Linear & Abstract Algebra||9|
|Solving polynomial congruences modulo a prime power||Calculus & Beyond Homework||0|
|system of linear congruences||Linear & Abstract Algebra||7|
|Solving linear congruences||General Math||1|