Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

-1
votes
0answers
31 views

How can I solve these linear diophantine equations?

Just starting to learn (in 11th grade) linear diophantine equations, and I'm faced with these problems. Everybody said to me that they are quite easy. Solve: $x! - 1 = y^2$ in natural ...
0
votes
1answer
23 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
4answers
29 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
32 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
21 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 ...
0
votes
0answers
36 views

number of answers in $a_1x_1 + a_2x_2 + … + a_nx_n = k$ equation

I was wondering to know how many possible answer does this equation have ? $a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n = k$ where ai are coefficients and constant while xi are variable and a non-...
2
votes
2answers
226 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$, ...
0
votes
0answers
20 views

Algorithm for solving a diophantine equation

Is there an algorithm to obtain integral solutions for equation of the form $\frac{N-x}{2x}=y$, with $N,x,y\in \mathbb{Z}^{+}$, $\mod(N,x) = 0$, $y\geq x$ and $x\leq\frac{\sqrt{8N+1}-1}{4}$. Or can ...
1
vote
1answer
44 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
vote
0answers
20 views

Estimate integer solutions to a set of linear or diophantine equations (underdetermined)

Find a possible solution for every team's individual match score. Given n teams and m matches, there are n*m variables, or columns to solve for. Each match has 3 teams. The total score for each match ...
3
votes
1answer
71 views

$\mathbb{Z}$-Module exercise

I am trying to solve the following exercise on basic module theory and I am stuck. Any help would be more than welcome! So let $M\subseteq \mathbb{Z}^3$ the solutions to the following problem: $-3x+...
6
votes
4answers
83 views

Minimize $152207x-81103y$ over the positive integers.

Minimize the expression $152207x-81103y$ over the positive integers, given $x,y\in\mathbb{Z}.$ So the book takes me through modular arithmetic and how to find $\text{gcd}(a,b)$ in order to solve ...
1
vote
1answer
74 views

Integer solutions of a two-variable linear equation.

The question is: Find all pairs of integers $(x, y)$ such that $61x+18y = 0$. By solving for $x$, we have $x = (-18/61) \cdot y$, therefore $x$ is an integer if-f $y$ is a multiple of $61$. ...
1
vote
0answers
22 views

Asymptotic Expression for the number of solutions to linear Diophantine equation.

Consider the the general linear diophantine equation $$\sum_{i=1}^{k}a_ix_i =n $$ with $a_i\geq 1, n\geq 1$ and $x_i\geq 0.$ Then the generating function that counts the number of solutions to this ...
2
votes
1answer
24 views

How to find a recurrence relation for counting the number of solutions?

Consider the diophantine equation $$x_1+3x_2+5x_3 = n$$ where $x_i\geq 0$ and $n\geq 1.$ Let $P_n(1,3,5)$ denote the number of solutions to this equation. I want to express $P_n(1,3,5)$ in terms of $...
0
votes
0answers
21 views

On largest box expected size not containing integer vector solutions

I am trying to understand the largest cube in $\Bbb Z^8$ around origin not containing integer vector $(a,b,c,d,a',b',c',d')$ solutions to $$aBDE+bBCE+cADE+dACE+a'BDF+b'BCF+c'ADF+d'ACF=0$$ where $A,B,C,...
1
vote
1answer
21 views

Intuitive explanation of solutions to a linear diophantine equation

"Given a linear diophantine equation $ax+by=c$ with a particular solution $(x_0,y_0)$ the general solution is given by $$\biggl(x_0-\frac{b}{gcd(a,b)}t,y_0+\frac{a}{gcd(a,b)}t\biggr)$$ for all $t\in \...
2
votes
1answer
62 views

The incongruent solutions of a linear congruence

My question is to do with the incongruent solutions of a linear congruence. This is the problem: Find all integer solutions to the linear congruence $15x \equiv 36 \mod 57$. I'm able to use Euclid'...
0
votes
0answers
23 views

finding the number of solutions of an equation over $\mathbb{Z}_{\ge 0}$

I want to count the number of solutions to the following equation in non-negative integers: Let $n \in \mathbb{N}$, Fix $1 \le p \le q \le n$ and $m_p, m_q \in \mathbb{N}$, $$\sum_{j = 1}^n j \cdot ...
0
votes
1answer
59 views

Euler's method for linear diophantine equations

This should be extremely easy, but I'm having trouble with something. I'm following C.D. Olds "Continued Fractions" book, pages 43/44. Consider the equation $8x+5y=81$. We're searching for integer ...
1
vote
2answers
43 views

Use of diophantine equation (money problems, 3 variables)

My friend has in his wallet some notes of $\displaystyle{ 20 }$ , $\displaystyle{ 50 }$ and $\displaystyle{ 100 }$ euros. He has $\displaystyle{ 15 }$ notes and the total value of them is $\...
1
vote
1answer
102 views

Find the number of non-negative integer solutions to linear systems

For instance with two variables: $ax + by = c$, where x and y are variables. I found these two threads [1, 2], where the solution is equal to $\binom{n+p-1}{p-1}$, where n is the desired sum and p is ...
0
votes
2answers
65 views

Find the value of $x,y$ for the equation $12x+5y=7$ using number theory .

I tried the solution using other ways like: $12x+5y=7$ $12x=7-5y$ $x=7-5y/12$ putting the value of $x$ $12(7-5y/12)+5y=7$ both $12$ will cancel out $7-5y+5y=7$ here comes the problem please ...
0
votes
0answers
18 views

General solution to three variable Diophantine equations

I am trying to solve the following form of linear Diophantine equation: ax + by + cz = d Having previously looked at two variable Diophantine equations (ax + bx = c), I have learnt to apply the ...
0
votes
0answers
42 views

Find the necessary and sufficient conditions under which ax + by = c will have a solution in positive integers

We know that the linear Diophantine equation ax + by = c has an integer solution if g | c where g = gcd(a,b). Such solutions may be positive or negative. Find the necessary and sufficient conditions ...
0
votes
0answers
26 views

An exponent for a linear homogeneous diophantine approximation

Notations. Let's denote by $\vert \cdot\vert $ the standard euclidean norm on $\mathbb Z^2$. Let's denote by $\Vert\cdot\Vert_{\mathbb Z}$ the following norm on $\mathbb R^2$: $$\forall X\in\mathbb ...
1
vote
0answers
36 views

Find a specific solution to a linear Diophantine equation

Prove that for any given integers $b > a \geq 1$ there exists an integer solution $u$, $w$ to $au - bw = \text{gcd}(a,b)$ with $0\leq u\leq b-1$ and $0\leq w \leq a-1$. This is supposedly a simple ...
2
votes
2answers
41 views

Linear Diophantine equation which doesn't divide

Im trying to find the solution for the linear Diophantine equation $55x + 22y = 400. $ I found $gcd(55,22) = 11$ therefore $11 = 55-22.2$ but 400 isnt a multiple of 11. is there any other way which ...
1
vote
3answers
134 views

Find $n$ such that there are $11$ non-negative integral solutions to $12x+13y =n$

What should be the value of $n$, so that $12x+13y = n$ has 11 non-negative integer solutions? As it is a Diophantine equation, so we check whether the solution exists? it exists if $gcd(12,13)|n$ ...
1
vote
0answers
40 views

Solving OR bounding sums of solutions to certain linear diophantine equations

(This question arose during group work on classifying modular tensor categories.) Let $p$ and $q$ be two distinct primes. We seek integral solutions $\lbrace x_{i,j} \rbrace$ to the equation \begin{...
0
votes
0answers
100 views

Can EX=A where $E\in\Bbb{Z}^{6\times6}$, $X\in\Bbb{Z}^{6\times34}$, $A\in\Bbb{Z}^{6\times34}$ be solved in E and X when A is given?

I am trying to solve a cryptography challenge (https://www.mysterytwisterc3.org/en/challenges/level-ii/hilly-part-2) where I must calculate: $E \in \Bbb{Z}^{6\times6}$ 34 (column) vectors $X_i \in \...
1
vote
2answers
75 views

Proof that $\gcd(a,b) = \gcd(\operatorname{mod}(a,b),b) $ [closed]

Empirically this equality holds: $\gcd(10,8) = 2 $ and $\gcd(\operatorname{mod}(10,8),8) = \gcd(2,8) = 2 $ $\gcd(18,9) = 9 $ and $\gcd( \operatorname{mod}(18,9),9) = \gcd(0,9) = 9 $ I am stuck on ...
1
vote
2answers
87 views

Can we always solve this as a Linear Diophantine Equation?

Given $d=gcd(a,m) \mid b$, is it always possible to solve a congruence equation in the form $$ax+(-m)y=b$$ Since I have expressed the problem as a linear diophantine equation, can't I just solve ...
0
votes
1answer
42 views

Find $x, y, z \in \mathbb{Z}$ such that :

$4x+6y+9z=7$ using Smith's algorithm and linear system. We can re-write the equation with : $[4 \ 6 \ 9]\times \left( \begin{array}{c} x\\ y\\ z \end{array}\right)=7$ I want to find a matrix $L \in \...
2
votes
0answers
24 views

An interesting combinatorical counting prolem related to non negative solutions of linear diophantine equations

Given two non-negative integers $m,n$. Define $F_{m,n}$ as the set of all non negative integer sequence $(i_0,i_1,\ldots,i_n)$ which satisfiy $$i_1+2i_2+\cdots+(n-1)i_{n-1} = m$$ and $$i_0+i_1+\...
1
vote
3answers
58 views

How can I do the Euclidian's algorithm and the Extended Euclidean algorithm at the same time?

This is what my lecture notes have but I cannot find anything like it online and there is no explanation in the notes. The example given is for 903 and 444. Thank you.
0
votes
1answer
30 views

How can I solve equations of the form $xy-k(x+y)=0$ where $k\geq 0$ where $x,y\in \mathbb{Z}$

Given $xy-k(x+y)=0$ where $k\geq 0\space where\space x,y\in \mathbb{Z} $ I know this is a diophantine equation which I have read about earlier. My attempt : $(x-k)\cdot(y-k)=k^2$ $\implies \space ...
3
votes
1answer
77 views

How can I find all primitive pythagorean multiples given one even number including that number?

I am trying to make an algorithm to find all pythagorean triples given a even number such as 4. Then the triple would be (3,4,5). Is there a way to do this? I am using maple to do this but can also ...
0
votes
1answer
27 views

A question on linear diophantine equations in two variables

The theorem says, "Let $a,b,c$ be integers with $a$ and $b$ be both $ \text {not} \ {zero} \ $. Then the equation $ax+by=c$ has an integral solution iff $d$ divides $c$, where $d=g.c.d(a,b)$. ...
6
votes
6answers
518 views

How would one solve a linear equation in two integer variables?

For example, how would I find integers $a$ and $b$ that satisfy the following equation? $$5a - 12b = 13$$ I always resorted to trial and error when doing something like this and more often than not ...
0
votes
0answers
111 views

Diophantine equations with irrational coefficients

I was going through the book "Rational Points on Elliptic Curves by Silverman and Tate" and the rational line was defined like this. "We call a line a rational line if the equation of the line can be ...
0
votes
2answers
45 views

Diophantine equation with “extra” conditions

My question is how can I solve Diophantine equations with additional restrictions. For example, what about $x+2y+5z=40$ coupled with $x+y+z=20$ where $x,y,z>0$?
0
votes
2answers
155 views

How to find the first lattice point in the first quadrant on the line $21x-101y=1$?

How to find the first lattice point in the first quadrant on the line $21x-101y=1$? I can find the lattice point with the help of modular arithmetic. But is there any simple way to do that?
0
votes
1answer
46 views

Number of non-negative integer constraint solutions to simple linear equations

Suppose we want to find the number of non-negative integral solutions to the equation: $$x_1 + x_2+ x_3 = m$$ where we have $x_i \le L_i, i\ge2$ I found the solution as: $$\sum_{x_2=0}^{L_2} \sum_{...
0
votes
4answers
63 views

Prove the required form [closed]

Let $a$ and $b$ be coprime integers and $(x_0, y_0)$ be a set of integer solutions of the Diophantine equation $ax+by=1$. Prove that any set of integer solution is of the form $x = x_0 + bt$, $y = ...
4
votes
3answers
95 views

Integer solutions of $2x+3y=n$

What is the smallest $m$ such that for all $n\geq m$, the equation $2x+3y=n$ has solutions with $x,y \in \mathbb{Z}$ and $x,y\geq2$? My approach. We can write the solutions in terms of the parameter $...
0
votes
2answers
3k views

How to solve a system of linear equations modulo n?

For example, $4x - 10y \equiv 8\pmod {20}$ $7x + 2y \equiv 5\pmod {20}$ It resembles linear diophantine equations and the Chinese Remainder Theorem, but I don't know how to actually solve it..
1
vote
2answers
39 views

Explanation of this solution involving Linear Diophantine Equations

For the question: For what values of $c$ does $8x+5y = c$ have exactly one strictly positive solution? The solution is this So I have 3 questions. I understand everything up until the part ...
0
votes
2answers
696 views

Smallest positive integer a such that $5n^{13}+13n^5+a(9n)\equiv 0\pmod{65}$

How would you find the smallest positive integer $a$ such that $$5n^{13}+13n^5+a(9n)\equiv 0\pmod{65}$$ I simplified the polynomial in terms of $\bmod 5$ and $\bmod 13$ to get $3n+4na \equiv 0 \pmod{...
1
vote
1answer
114 views

Finding Specific Solution to Linear Diophantine Equation

Other than by brute force, how can I solve $a=20k+91806$ to find the solution $a=96646$ (or $k=242$) if I know the following: A. The prime factorization of $91806$ is $2,3,11,13,107$. B. $GCD(a,...