Questions tagged [linear-diophantine-equations]

Diophantine equations where all of the terms are monomials of degree zero or one. For example, finding all integers $x$ satisfying $ax = b$, finding all integers $x,y$ such that $ax + by = c$, or finding all integers $x,y,z$ such that $ax + by + cz = d$. Probably appropriate with (elementary-number-theory).

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

What is the “right” name for this Diophantine equation? $ a_1 x_1 + a_2 x_2 + \dots + a_k x_k \equiv n\pmod h$

I am not able to find a clear answer to what is the right terminology to refer to this type of equation: $$ a_1 x_1 + a_2 x_2 + \dots + a_k x_k \equiv n\pmod h\,. $$ where $a_i,x_i,n,h(\neq0) \in \...
0
votes
2answers
47 views

How to solve a linear diophantine equation with six unknowns with constraints?

I would like to solve this linear diophantine equation: $$ 40x_1+296x_2+945x_3+2048x_4+4500x_5+8640x_6=616103 $$ All the answers have to be an integer number in the interval $\{[10] \cup [29,95]\}$. ...
1
vote
1answer
34 views

Minimal positive solution of linear congruence equations in multiple variables

I am definitely new when it comes to equations over integers so I am not even sure the nomenclature (modular linear congruence equation) is correct. I am interested to solve equations over the ...
0
votes
1answer
36 views

How to solve this using linear diophantine equations?

A trader has a beam balance and two weight weighing 25 grams and 60 grams using the theory diophantine equations, shows how he can sell exactly 40 grams of flour, using only these two weights and ...
2
votes
4answers
70 views

Integer solution of $a+b+c=15$ with restrictions on $a, b$ and $c$

I'm checking this problem: Find the integer solutions of $a+b+c=15$ if $a$ is multiple of 3, $b$ is less than 10 and $c$ is multiple of 2. With $a, b, c ≥ 0$ We can make a series of polynomials ...
1
vote
1answer
35 views

Non negative solution to diophantine equation

If I have an equation $$ a_1x_1+a_2x_2+...a_nx_n=c$$ where $a_i,c$ are non negative integers. Then under what conditions if any are $x_i$ also non negative integer solutions?
-2
votes
1answer
28 views

Efficiently find integer solution to ax + by = c [closed]

Consider an equation of the form $ax + by = c$, where $a$, $b$, and $c$ are nonnegative integers. I'd like to efficiently determine whether there exists a nonnegative integer solution for $x, y$ that ...
0
votes
0answers
32 views

How many positive integer solutions does the general equation $N=a_1 x_1+a_2x_2+a_3x_3+\dots$ have for some number of variables?

If I’m given this equation $$N=a_1x_1+a_2x_2+a_3x_3+\dots$$ is there a function or some way that doesn’t include brute force to tell how many positive integer solutions this equation has, it’s not ...
-1
votes
2answers
31 views

Solving integer equations [duplicate]

Find the number of positive integers $(x, y)$ that satisfy $3x + 5y = 501$ Usually when doing these I can get the result by factoring the expression. Here I ended up with something like this: $$3x+...
0
votes
2answers
34 views

Solution of Single Linear equation [duplicate]

How do I prove there is no solution/solution to the single equation $150a+5b=54c$ provided $a,b,c$ must be different integer numbers ranging from 0-9? I can verify it by running a computer program, ...
0
votes
5answers
56 views

Solving for positive integral values of an equation

The question I originally came across is this, Find positive, non-equal ,integrs such that the sum of their reciprocals is $\frac12$ I got an equation, $$\frac1{x}+\frac1{y}=\frac12$$ Where $x$ ...
1
vote
1answer
24 views

How to determine if a integer linear equation with contraints is solvable?

I want to write an efficient program to the determine if the following equation is solvable. The equation and the constraints look like this: $$\begin{align} &\sum_{i=1}^{n}a_ix_i=0\quad(\forall ...
0
votes
2answers
53 views

Given the values of apples, oranges, and mangoes, how to buy 100 fruits for 100 dollars?

One of my friends gave me this question. 1 apple costs \$1 20 oranges costs \$1 1 mango costs \$5 How many items do you need to buy in order to have a total of 100 items and a value of $100? I ...
0
votes
0answers
17 views

Diophantine Approximation under certain absolute error

I'm in a discrete mathematics course right now, and we are learning about Diophantine Approximations. We covered a topic the other day that kind of went over my head. It was about finding a ...
0
votes
1answer
45 views

Variable reduction in a Linear Programming problem

I am currently working on a problem where I need to find a feasible solution to linear equality constraints. $\hspace{50mm}Ax=b,$ $\hspace{50mm}x\geq0,$ $\hspace{38mm}$where $A \in R^{m*n}, b\...
2
votes
1answer
62 views

Efficiently Computing a Non-negative Solution for an Underdetermined System of Linear Equations with 0-1 Coefficient Matrix

I have a system of linear diophantine equations having $m$ constraints and $n$ variables, where $n>>m$. The coefficient matrix has all entries either 0 or 1. I am interested in finding a non-...
1
vote
0answers
70 views

A generating function for a non-homogeneous linear Diophantine equation

Suppose we have an equation $a_1 x_1 + \ldots +a_k x_k = l$, where $a_i$ and $l$ are integers, but not necessarily non-negative. Moreover, assume not all $a_i$ are zero, and that $k$ is at least $2$. ...
-1
votes
1answer
29 views

Naive question on combinatorics and Diofantine

I was reading through some stuff about cellular automaton and faced the following problem. Basically, I have three squares, each can contain one number among 1,2 and 3, and I have to consider all ...
2
votes
0answers
52 views

Solving a certain type of linear equation with natural numbers

Today I was given the following problem. Imagine walking into a chocolate store where they only sell boxes of $6$, $9$ or $20$ chocolates. What is the largest amount of chocolates you can't buy ...
0
votes
0answers
22 views

Does $ax - by + 1=0$ have an integer solution when $\gcd (a,b)=1$ and $|a-b|>1$? [duplicate]

I was working on modular arithmetic but I'm stuck on the question of whether $6n+1$ is divided by $11$ for any positive integer $n$? So I generalized this problem to learn details of integer solutions ...
-1
votes
1answer
29 views

How to know when it's possible to solve a modular equation? [duplicate]

In my professor's notes there's the following example: $$21x \equiv 15 \pmod{39} \Leftrightarrow 21x - 39y = 15$$ It reads: Because $\gcd(21,-39) = 3$ and $3\mid15$, this equation has a solution....
0
votes
1answer
55 views

Number of solutions for this diophantine equation using character theory?

Let $G$ an abelian group with $\text# G<+\infty$ and $N_1, ..., N_k$ , $k$ subsets of $G$. Let $a \in G$. We want to find $\text# \{(n_1,...,n_k)\in N_1\times...\times N_k \ / \ n_1+...+n_k=a \}$. ...
0
votes
1answer
103 views

Solving a linear Diophantine equation .

In one month a store sold pads of paper, some for $\$\,11$, some for $\$\,3$, and some for $50$ cents. A total of $98$ pads were sold for a total of $\$\,98$ evaluate the total number of $50$ cent ...
1
vote
1answer
71 views

Solution for a 5 variables diophantine equation-system (2 unknown independent variables, one given parameter)?

In continuing/generalizing an earlier question(this and this) I arrived at the following problem on positive integers. Assume $Q>0$ as given constant and either $(S,T) \ge 1$ as primary solutions ...
0
votes
1answer
46 views

Matrix method to solve linear Diophantine equations?

I see in this document the following method to solve the Diophantine equation $1234x+2341y=1$: It looks pretty useful and interesting, but I don't know what the cited work MNZ p.218 is. Can anyone ...
-1
votes
3answers
75 views

Solution of a diophantine linear equation system

I want to find out for what triples $(a,b,c) \in \mathbb{Z}^3 $ the following system of linear diophantine equations has a solution: $$\begin{cases} 24x+\phantom{1}6z=a, \\ 24x+16y=b, \\ 32x+\...
0
votes
0answers
41 views

Faster ways to prove no solutions for a linear Diophantine equation

At the heart of an algorithm for calculating optimal addition chains I prune by either showing a linear Diophantine equation has no solutions or enumerate some small number of solutions and reject ...
3
votes
2answers
142 views

How can we find the minimal solutions to a linear Diophantine equation?

Suppose we have coprime integers $(a,b)$ and let $\ell \in \mathbb{Z}$ be arbitrary. The general solution to the linear Diophantine equation $ax+by=\ell$ is given by $x=\ell x' + bt$ and $y=\ell y' - ...
-1
votes
1answer
43 views

Finding rational points [closed]

How can I find a formula for all rational points on the curve $x^2 - y^2 = 3$?
0
votes
3answers
40 views

Diophantine problems, pythagorean equation

It can be shown that that for $x,y,z \in \mathbb{N}_{>0}$ the Pythagorean equation $x^2 + y^2 = z^2$ has the general solution $x = 2grs$,$y = g(r^2 - s^2)$ and $z = g(r^2+s^2)$ with $g>0, r>s&...
0
votes
2answers
44 views

If $\exists a,b \in \mathbb{N}$ then $\exists k,l \in \mathbb{Z}$ s.t. GCD(a,b)=ak+bl, $l,b\in \mathbb{Z}$ [duplicate]

I don't really understand the proof for this. It says "consider a set $A=\{ax+by\mid x,y\in \mathbb{Z}\}$. Then let the smallest element of of $A$ be $d$.Then $d=ak+bn, k,n\in Z$. Show $d|a$ and $d|b$ ...
1
vote
1answer
38 views

Solution to a linear combination of integers being zero [duplicate]

I'm not very familiar with number theory so forgive me if this is a basic question. Consider the equation: $$\alpha \ n + \beta \ m = 0,$$ with $n,m$ being integers. One can easily see that the above ...
1
vote
2answers
128 views

A man exchanges 9763 yen for USD and CAD. 99 yen = 1USD, 86yen = 1CAD how much of each currency did he exchange?

So I did Euclidean algorithm to find the GCD of 86 and 99 cause there's a theorem that if their GCD divides 9763 then there are infinitely many solutions of combination $99x+86y=9763$. Here is my ...
3
votes
4answers
307 views

How many integral solutions does $2x + 3y + 5z = 900$ have when $ x, y, z \ge 0$?

Solution: Let $2x + 3y = u.$ Then we must solve $\begin{align} u + 5z = 900 \tag 1 \\ 2x + 3y = u \tag 2 \end{align}$ For $(1),$ a particular solution is $(u_0, z_0) = (0, 180).$ Hence, all the ...
1
vote
1answer
90 views

$11c+2d=86$ has no solution.

Show that, in the year $1996$, no one could claim on his birthday, that his age was the sum of the digits of the year, in which, he was born. My attempt:- Suppose a person born in the year $19\...
1
vote
0answers
36 views

Existence of solution for a modular system of equations

I am trying to prove that there is at least one solution for the following system of equations: There are $2(q+1)$ unknowns $\{r_1, r_2, \dots, r_{q+1}\}$ and $\{r'_1, r'_2, \dots, r'_{q+1}\}$ where ...
1
vote
3answers
84 views

Determining the truth of $\forall \; n \in Z, \exists \; a,b \in Z$ : $n=4a+5b$ $\implies$ $n^2 = 5a+4b-1$

The question at proving $\forall n \in Z,$ : ($\exists a,b \in Z$ $n=4a+5b$) $\implies$ ($\exists a,b \in Z$ $n^2 = 5a+4b-1$) originally asked one thing but then it was corrected to ask something ...
2
votes
0answers
44 views

Solution to a very specific linear system of (Diophantine) equations

Let $A$ be an $n\times n$ matrix, with entries only from $\{1,\dots ,n\}$, with no repeated values in any row or any column. Consider the system $AX=B$ of $n$ linear (Diophantine) equations $AX=B$, ...
2
votes
3answers
124 views

How to solve 3 equations over $\mathbb{Z}$?

I have those 3 equations: $$-5x+2y+4z+w=8\\ 27x+10y+2z+7w=6\\ -20x-6y-4w=-10$$ I tried to solve them over $\mathbb{Z}$ via making a matrix at $SNF$ (Smith Normal Form), So I began with this matrix: $...
1
vote
0answers
54 views

Counting number non-reachable integer solutions of a Linear Diophantine Equation.

Suppose we have a Linear Diophantine Equation $$a_k x_1 + a_{k+1} x_2 + ...+a_{k+n-1}x_n $$ where, $a_k>0 , n>1$ and $x_i>0$ And it is given that $$gcd(a_k, a_{k+1}...a_{k+n-1}) = 1$$ the ...
1
vote
4answers
81 views

How many $c$ for which equation $ax+(a + 1)y=c$ will have no positive integer solution?

Suppose we are given an equation in $ax+(a + 1)y=c$ Now we have to find for how many values of $c$ where $c \in [1,\infty)$ will have no positive integral solution. I'm new to diophantine equation, ...
0
votes
1answer
64 views

Expressing difference of squares as diophantine equation

I have a function defined by $f=(2c-1)^2-2b^2$. I want to express this in the form of a linear diophantine equation. I tried $f_1=8m\pm 1$ for some $m$, but it unfortunately does not work since for ...
0
votes
1answer
36 views

Finding all integer solutions to a linear equation that lie in a particular region

I want to find all $(x,y,z)$ satisfying $z=x+ay,a>0$ where $0\le x\le X,0\le y \le Y, 0 \le z \le Z$. Additionally, $Z>X$. An expression for the number of all such $(x,y,z)$ tuples is also ...
0
votes
0answers
61 views

General Solution of Linear Diophantine Equation with 2 and more than 2 variable

We know the theorem of linear diophantine equation from Bezout's identity that the solution is in ordered pair form: $\left(x + m \dfrac{b}{\text{gcd}(a,b)}\,,\,y-m \dfrac{a}{\text{gcd}(a,b)}\right)$ ...
0
votes
1answer
35 views

Is there a way to find positive values for unknown of Diophantine Equations?

I have a equation as follow ax+by =c where the value of x and y are unknown. This is a 2 ...
1
vote
5answers
86 views

An equation in two variables?

Given 13x + 35y = 2000. How do I find positive integer solutions for this equation (without hit and trial). My work :- I know I can use Bezout's Theorem to find integer solutions to this equation if ...
-2
votes
2answers
133 views

Solve This Diophantine Equation : $11x+13y$=$1000$ where $(x,y)$ belongs to positive integers . [closed]

Please help me solve this Diophantine Equation : $11x+13y$=$1000$ where $(x,y)$ belongs to positive integers .
0
votes
0answers
44 views

Solution of Linear Diophantine Equation

How to find all solutions of Linear Diophantine Equation $a \cdot x + b \cdot y = c $ given $a,b,c$ where $c$ is divisible by $\gcd(a,b)$ and constraints are $x_0 \leq x \leq x_1$ and $y_0 \leq y \leq ...
2
votes
2answers
238 views

A problem from Hardy's_Pure Mathematics on Real variables about Linear equations in 3 variables

It may be my stupidity, yet I am unable to understand what the following problem asks (Q.1 Miscellaneous Examples, Chapter-1: Real Variables). It says: What are the conditions that $ax+by+cz=0$, ...
1
vote
1answer
45 views

When $p<q$ there is a solution to $qx+py = c$, but not when $p>q$. Why?

For linear diophantine equation: $qx+py = c$ , where $p$ is a prime and $q$ is a natural number, why is it that if $p<q$ then there is a solution to the equation, however when $p>q$ then there ...

1
2 3 4 5