# 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).

212 questions
Filter by
Sorted by
Tagged with
38 views

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-...
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$. ...
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 ...
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 ...
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 ...
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....
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 \}$. ...
103 views

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 ... 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 ... 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 ... 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+\... 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 ... 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' - ... 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? 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&... 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 ... 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 ... 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 ... 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 ... 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\... 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 ... 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 ... 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, ... 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: ... 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 ... 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, ... 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 ... 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 ... 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)$... 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 ... 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 ... 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 . 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 ...
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$, ...
### 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 ...