Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
67 views

System of linear diophantine equations with many small solutions?

Let $n$ be positive integer, $k$,$B$ fixed positive integers. Let $f_i(x_1,x_2...x_n)$ be a system of $n-k$ linearly independent linear equations over the integers. Let $S(f_i,k,B)$ be the set of ...
joro's user avatar
  • 25.4k
2 votes
1 answer
179 views

Only trivial solution to a pair of constrained linear diophantine equations

Given positive integer $n$, we are looking for a set of $n$ positive integers $a_i$. The following linear integer program must have only the trivial integer solution of all ones. $0 \le x_i \le \frac{...
joro's user avatar
  • 25.4k
0 votes
2 answers
426 views

Fastest way to solve non-negative linear diophantine equations

Let $A$ be a matrix in $M_{n \times m}(\mathbb{Z}_{\ge 0})$ without zero column. Let $V$ be a vector in $\mathbb{Z}_{> 0}^m$. Question: What is the fastest way to find all the solutions $X \in \...
Sebastien Palcoux's user avatar
5 votes
0 answers
240 views

Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

Crossposted at Theoretical Computer Science SE A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$....
Surpass2019's user avatar
6 votes
0 answers
410 views

Efficient solutions to general Bézout’s identity $a_1 b_1 + \dots + a_n b_n = 1$

Suppose I have integers $a_1, \dots, a_n$ which are coprime, meaning that $$a_1 b_1 + \dots + a_n b_n = 1$$ has a solution in integers $b_1, \dots, b_n$. I would like to get a bound saying ...
Kim's user avatar
  • 4,164
2 votes
1 answer
202 views

Feasibility of constrained multivariable diophantine equations

Let $d$ be day, $m$ be month and $y$ be year fields of a date. I want to find few dates of format $$(d^2\, mod\,\, 2 + (my + d^3) \,mod \,4) = 2$$ Is there a method to solve this type of equation or ...
user3219492's user avatar
6 votes
1 answer
405 views

Existence of nonnegative solution in diophantine linear equations system with non negative coefficents

Given a Diophantine system of linear equations $Ax = b$, where $A \in \mathbb{N}^{m\times n}$ and $b\in\mathbb{N}^{m}$, is there a method to determine whether there exists a nonnegative solution $x\...
Ladar's user avatar
  • 61
2 votes
0 answers
92 views

On design of a (preferrably unimodular) matrix

Assume each entry is in $\Bbb Z$. Say we want to solve $Ax=b$ where known $A$ is $n\times n$, unknown $x$ is $n\times1$ and $b$ is $n\times1$. The absolute value of minors of augmented matrix $[A|b]$...
Turbo's user avatar
  • 13.9k
1 vote
1 answer
116 views

Sign Enumeration

What is the number of solutions of $(a_i)_{i=1}^n$ such that $$\sum_{i=1}^nia_i\le b,\quad a_i\in\{-1,1\},\quad \sum_{i=1}^n{a_i}=c$$ given $b,c\in\mathbf Z$? Is there a generating function solution?
Hans's user avatar
  • 2,239
3 votes
2 answers
608 views

Minimal solution of simultaneous congruences

I would to determine the set of values $\lbrace a_1,a_2,a_3,\ldots,a_n \rbrace$ that minimizes the value of $x$ such that: $$x\equiv a_1\mod p_1$$ $$\vdots$$ $$x\equiv a_n\mod p_n$$ where every ...
user82974's user avatar
2 votes
1 answer
366 views

System of congruences

I have a system of $n$ congruences. the generic $m$_th congruence of the system ($m = 1,\dots,n$) is in the form: $(p_n\#)^2(\displaystyle\sum_{\substack{i=1\\i\neq m}}^n{\frac{x_iy_m}{p_ip_m}}+\...
Leonardo's user avatar
3 votes
1 answer
387 views

Sufficient condition for solvability of linear diophantine system

I would like to know under what conditions does an integer solution exist to the under-determined linear system: Ax = b. (without constraints) Where A is m x n matrix with positive integers entries (...
Leonardo's user avatar
1 vote
2 answers
752 views

basis of the lattice generated by the integer points inside a subspace of R^L

Consider $K$ linearly independent vectors $\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{a}_K \in \mathbb{Z}^L$, where $1 \leq K<L $. Hence, the span of $\lbrace\mathbf{a}_1, \mathbf{a}_2, ..., \mathbf{...
mohsenh01's user avatar
6 votes
2 answers
2k views

is there a solution to this linear Diophantine system?

I have a matrix $A \in \mathbb Z^{n \times m}$, where $m > n$, and a vector $b \in \mathbb Z^n$. Under what conditions does $$Ax = b$$ have an integer solution? Is there a way to bound the norm ...
SAK's user avatar
  • 61
3 votes
0 answers
3k views

0,1 solution to system of linear integer equations

I have the following problem: $A x = b$ where $A, b$ - $m \times n$-matrix and $m$-vector of nonnegative integers (respectively). $x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
Wisdom's Wind's user avatar