A Special System of Linear Congruences

  • Thread starter e(ho0n3
  • Start date
  • #1
1,357
0

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
402
1
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
1,357
0
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
402
1
Then, if after reducing mod d, there is a violation of any of the restrictions, we must conclude that there is no solution.
 
  • #5
1,357
0
You have a good point there. Thanks for your help.
 

Related Threads on A Special System of Linear Congruences

  • Last Post
Replies
7
Views
7K
Replies
1
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
9K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
23
Views
4K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
8
Views
3K
Top