A Special System of Linear Congruences

In summary, the conversation discusses a system of m equations in k unknowns with restrictions on the values of the unknowns. It is concluded that Gaussian elimination will work if all operations are done mod d (or n). If a solution is obtained where one of the unknowns is outside its bounds, it can be reduced mod d (or n). However, if this results in a violation of the restrictions, it can be concluded that there is no solution.
  • #1
e(ho0n3
1,357
0
Suppose I have a system of m equations in k unknowns

[tex]
\begin{align*}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1k}x_k &= 0 \pmod d \\
&\vdots \\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mk}x_k &= 0 \pmod d
\end{align*}
[/tex]

with the restriction that [itex]0 \le x_n < n[/itex]. How do I solve such a thing? Will Gaussian elimination work? What if I get a solution where one of the x's is outside its bounds?
 
Physics news on Phys.org
  • #2
Gaussian elimination will work, if all operations are done mod d (I suspect this d should be n).

What if I get a solution where one of the x's is outside its bounds?

Reduce it mod d (or n).
 
  • #3
JSuarez said:
Gaussian elimination will work, if all operations are done mod d (I suspect this d should be n).
No, it should be mod d.

What if I get a solution where one of the x's is outside its bounds?
Reduce it mod d (or n).
I messed up with the restrictions. It should be [itex]0 \le x_n \le i_n[/itex] for some given [itex]i_n[/itex]. If I mod an x by d or by [itex]i_n[/itex], it will screw up the solution because when I plug a mod'ed x back into the system, the numbers won't come out right. I would have to mod all the x's by d, by this will automatically happen if I do Gaussian elimination by mod d. However, the problem remains: What if one of the x's is outside its bound?
 
  • #4
Then, if after reducing mod d, there is a violation of any of the restrictions, we must conclude that there is no solution.
 
  • #5
You have a good point there. Thanks for your help.
 

1. What is a special system of linear congruences?

A special system of linear congruences is a set of equations that involve congruences, which are essentially a type of mathematical equality. In this system, all equations are linear (meaning they involve only variables to the first power) and have the same modulus (the number that is used as the basis for the congruence).

2. What makes a system of linear congruences "special"?

A special system of linear congruences has the property that the number of equations is equal to the number of variables. This means that the system has a unique solution, unlike a regular system of linear equations which may have multiple solutions.

3. How is a special system of linear congruences solved?

To solve a special system of linear congruences, we use the Chinese Remainder Theorem. This theorem states that if the moduli of all equations in the system are pairwise relatively prime (meaning they have no common factors), then there exists a unique solution to the system. This solution can be found using a process called the Chinese Remainder Algorithm.

4. What are some real-world applications of a special system of linear congruences?

A special system of linear congruences can be used to solve problems related to finding the least common multiple (LCM) and greatest common divisor (GCD) of numbers. It also has applications in cryptography, specifically in the field of RSA encryption.

5. Can a special system of linear congruences have no solution?

No, a special system of linear congruences will always have a unique solution as long as the number of equations is equal to the number of variables and the moduli are pairwise relatively prime. However, a regular system of linear equations may have no solution if the equations are inconsistent or contradictory.

Similar threads

Replies
27
Views
1K
  • Linear and Abstract Algebra
2
Replies
52
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
921
  • Linear and Abstract Algebra
Replies
15
Views
1K
  • Math POTW for University Students
Replies
1
Views
1K
Replies
7
Views
2K
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
2K
  • Advanced Physics Homework Help
Replies
1
Views
1K
  • Topology and Analysis
Replies
9
Views
2K
Back
Top