Solving a System of Congruences with A Changing Modulus

In summary: You could try a different prime and see if the equation still holds. In summary, when trying to solve for X in an equation with a quadratic congruence, it may be helpful to try to find a prime that makes A >>> a quadratic residue.
  • #1
drosser
13
0
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.
 
Physics news on Phys.org
  • #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.
 
  • #3
drosser said:
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?
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!
 
  • #4
ramsey2879 said:
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!
Opps I forgot that k relates both k^2 and L-k
 

1. How do you solve a system of congruences with a changing modulus?

To solve a system of congruences with a changing modulus, you first need to find the least common multiple (LCM) of all the moduli involved. Then, you can create a new system of congruences with the same residues but with the LCM as the modulus. Finally, you can use the Chinese Remainder Theorem to find the solution to the new system of congruences.

2. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical theorem that states that if the moduli in a system of congruences are pairwise coprime (meaning they have no common factors), then there exists a unique solution to the system of congruences. This solution can be found using a formula involving the residues and moduli.

3. Can a system of congruences have multiple solutions?

Yes, a system of congruences can have multiple solutions. However, if the moduli are pairwise coprime, there will be a unique solution. If the moduli are not pairwise coprime, there may be multiple solutions or no solution at all.

4. What is the least common multiple (LCM) of two or more numbers?

The least common multiple (LCM) of two or more numbers is the smallest positive number that is divisible by all of the given numbers. It is often used in solving systems of congruences with changing moduli.

5. Can the Chinese Remainder Theorem be used to solve systems of congruences with any number of equations?

Yes, the Chinese Remainder Theorem can be used to solve systems of congruences with any number of equations. However, as the number of equations increases, the calculations involved in finding the solution can become more complex and time-consuming.

Similar threads

Replies
4
Views
694
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Introductory Physics Homework Help
Replies
10
Views
818
  • Linear and Abstract Algebra
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
862
  • Linear and Abstract Algebra
Replies
5
Views
1K
Replies
4
Views
1K
  • Advanced Physics Homework Help
Replies
3
Views
398
Back
Top