Skip to main content

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
0 votes
0 answers
46 views

A man cashes a check for $d$ dollars and $c$ cents [duplicate]

I know this question has been asked before, but the answer to the previously posted question does not address my question about the problem. I will restate the problem: A man cashes a check for $d$ ...
k endres's user avatar
0 votes
1 answer
42 views

A man buys a dozen pieces of fruit...Questions about finding which solutions work [duplicate]

From Dudley's Elementary Number Theory, Section 3 on Linear Diophantine Equations, he poses the problem "A man bought a dozen pieces of fruit--apples and oranges--for 99 cents. If an apple costs ...
k endres's user avatar
1 vote
1 answer
48 views

When formulating the general solutions to a linear diophantine equation $ax + by = c$, does it matter which term is $x$ and which is $y$?

I saw the problem I am working on posted some years ago, and I cannot see how changing the order of the terms can matter, but when applying the general solution after finding one solution, my ...
k endres's user avatar
2 votes
0 answers
81 views
+50

Solving linear diophantine equations - methods and complexity

I'm curious what (if any) are the state-of-the-art methods to find solutions for linear diophantine* equations of N variables, like: $$ \sum _{i=1} ^{n} a_{i}x_i ~=~ b $$ Note that I mean a single ...
Adam's user avatar
  • 111
-2 votes
0 answers
31 views

Solving equation to get all possible solutions [duplicate]

This is a question on entrance exam. It says for positive integers $x,y,n,k$ and $n,k>1$ find all the possible solutions to $20x^k+24y^n =2024$ I found a wrong solution when $x^k =100$ so $x$ can ...
Ayush tripathi's user avatar
0 votes
1 answer
52 views

Diophantine equations - is my reasoning valid here?

I was thinking about the Diophantine equation $20x+24y=2024$ for a class today. There is an obvious solution: $x=100,y=1$ but there are other solutions as well where $x$ and $y$ are both positive ...
Red Five's user avatar
  • 2,772
3 votes
1 answer
77 views

Two pairs of coprime numbers

Given two pairs of integers $(m,n)$ and $(m',n')$ such that $m$ and $n$ (resp. $m'$ and $n'$) are coprime. Can we find a sequence of integer pairs $\{(m_1,n_1), (m_2,n_2),\cdots, (m_k,n_k)\}$ so that $...
Summer's user avatar
  • 6,923
0 votes
0 answers
32 views

Solving underdetermined linear equations over the nonnegative integers

I want to prove the following: Let $j_1, \ldots, j_8 \in \mathbb{Z}_{\ge 0}$. If \begin{align*} j_1 + j_2 + 2 j_3 - j_4 - j_6 -2 j_8 &= 0 \\ -j_1 + j_2 + j_4 + 2j_5 - j_6 -2 j_7 &=0 \end{...
Bobby L's user avatar
1 vote
0 answers
78 views

"Factorization" of the solutions set of a system of linear diophantine equations over non-negative integers

Suppose we have a system of linear diophantine equations over non-negative integers: $$ \left\lbrace\begin{aligned} &Ax=b\\ &x\in \mathbb{Z}^n_{\geq0} \end{aligned}\right. $$ where $A$ is a ...
Alexander's user avatar
0 votes
0 answers
44 views

Find integral values of x , y and z : $6x +10y + 15z= -1$ [duplicate]

I have done similar type of questions before by using the Euclidean Division Lemma/Algorithm to rewrite the equation and then find the solution, but those were problems with only two variables. In the ...
1025's user avatar
  • 49
2 votes
0 answers
95 views

Situations where the number of solutions to a linear Diophantine equation is always even

I have a number theory situation that I hope someone will recognize as a known situation and can direct me to some relevant papers in the literature. Let $S_1$ be an infinite subset of $N_0 =\{0,1,2,3,...
James McLaughlin's user avatar
0 votes
0 answers
25 views

Can linear diophantine equation be extended with coefficients infinitely? [duplicate]

That's the linear diophantine equation: $Ax + By = c$ where $A,B,x,y,c \in Z$ We can represent A and B as below: $GCD(A,B) = g$ $...
Szyszka947's user avatar
0 votes
0 answers
56 views

Given a solution find the values for a diophantine equation

Let $a,b \in \mathbb{Z}$ and suppose that every solution in $\mathbb{Z}$ of the Diophantine equation $$ax+by=35$$ is written as $$x = 7-3t \quad \text{and} \quad y = 7-4t.$$ where $t \in \mathbb{Z}$. ...
Davshock's user avatar
  • 137
2 votes
0 answers
109 views

Minimizing Absolute Value

Let a, b, c be three nonzero integers satisfying 7a + 11b + 13c = 0. What is the least possible value of |a| + |b| + |c|? I tried graphing this on the x-y-z plane but that didn't help much as a, b, ...
John Doe 's user avatar
0 votes
0 answers
60 views

Solving linear equations over $\mathbb{Z}$ using Smith normal form

To solve linear equations over $\mathbb{Z}$ we have a system of linear equations represented by some integer matrix $A$ of $n \times m$ dimension and $b \in \mathbb{Z}^n$. Such that solving $Ax = b$ ...
Txim's user avatar
  • 35
0 votes
1 answer
86 views

Algorithm to find the least solution of linear Diophantine equation [duplicate]

Suppose we are trying to find the smallest positive integers, $x,y$ such that, $$a + bx = cy$$ $$a \gt 0, b \gt a, c \gt b$$ If $a=0$, then this is just finding the lcm of $b$ and $c$. Not sure how to ...
Jeff's user avatar
  • 873
0 votes
0 answers
23 views

Find approximate solution $\omega_1 k_1 + \omega_2 k _2 \approx \gamma$ of linear Diophantine equation with real coefficients

Given real numbers $ω_1, ω_2, γ ∈ ℝ$, I want to find integers $k_1,k_2∈ℤ$ such that $ω_1k_1 + ω_2k_2 ≈ γ$. For all intends and purposes we may assume $ω_1, ω_2, γ$ are linearly independent over $ℚ$. ...
Hyperplane's user avatar
  • 11.8k
1 vote
1 answer
90 views

General Solution of equations involving integers

I was solving the following trigonometric equation in $x$ (which asked to find the general solution for $x$): $$\sin x(\cos\frac{x}{4}-2\sin x)+(1+\sin\frac{x}{4}-2\cos x)\cos x=0$$ After simplifying, ...
Vedaansh Agarwal's user avatar
0 votes
1 answer
31 views

Is this transformation of linear Diophanthine Equations always possible [closed]

Given a set of $N$ linear Diophantine equations over $V$ variables such that: Each variable appears 2 or 3 times Each equation has at most 3 variables $\frac12<\frac NV<1$ Can we always ...
xyz's user avatar
  • 47
2 votes
0 answers
96 views

Given a homogeneous system of Linear Equations mod $n$, if there are more equations than variables, can we tell if there exists a nontrivial solution?

We know that a homogeneous system of linear equations always has a trivial solution. Also, if there are more variables than equations, we are guaranteed to have a non-trivial solution. However, if ...
ghc1997's user avatar
  • 1,561
4 votes
1 answer
127 views

I am having difficulty understanding how to solve the diophantine equation $18x + 28y = 10$

I think I might be misunderstanding how to solve diophantine equations. I seem to be making a mistake somewhere in my process, and I am having difficulty figuring out what it could be. Here is what I ...
notsimplelogic's user avatar
0 votes
1 answer
78 views

$7x+5y=12$, so why does its solution will be of the format $(1+5n,1-7n)$ [duplicate]

Question Consider all ordered pairs of integers $(x,y)$ such that $$\frac{5}{x}+\frac{7}{y} = \frac{12}{xy}.$$ The smallest positive integer value of $x$ in these ordered pairs is 1, since $x=y=1$ ...
Ayush Upadhyay's user avatar
9 votes
1 answer
143 views

Shortest palindromic Egyptian representation for reciprocal integers

Consider the problem of representing the reciprocal of an integer as an Egyptian fraction where all the denominators are palindromes. i.e. write $$ \frac{1}{n} = \sum_{i} \frac{1}{a_i} $$ where $a_i$...
Peder's user avatar
  • 2,192
0 votes
0 answers
45 views

Number of positive integer solutions of diophantine inequality.

Given a Diophantine inequality of the form $$a_{1}x_{1}+a_{2}x_{2}+\dots+a_{n}x_{n}\leq N $$ How many positive integer solutions does it have? Here all $a_{i}\geq0$ and $x_{i}\geq 0$. I was able to ...
Anish Damai's user avatar
3 votes
4 answers
243 views

How many different sets of positive integers $(a, b, c, d)$ are there such that $a \lt b \lt c \lt d$ and $a + b + c + d = 41$?

Is there a general formula which I can use to calculate this and if it's with proof or reasoning would be great as well. Even if you could please solve this $4$-variable ordered set of positive ...
Jonathan Ramachandran's user avatar
0 votes
0 answers
57 views

Are the solution sets equal for diophantine equation with opposite general solution signs at parameter?

To my knowledge, this formula can be used to solve the general Diophantine equation $x=x_0\color{blue}+\frac{b}{d}\cdot t\\y=y_0\color{red}-\frac{a}{d}\cdot t$ or this $x=x_0\color{red}-\frac{b}{d}\...
DScounterGO's user avatar
0 votes
0 answers
41 views

Given two positive integers a , b , $gcd(a, b) = 1$, prove for any integer n > ab-a-b there exist integers $x, y\ge0$ such that $ax+by = n$ [duplicate]

Given two positive integers $a$, $b$ with $\gcd(a, b) = 1$, prove that for any integer $n > ab-a-b$ there exist non-negative integers $x$, $y$ such that $ax+by = n$ We can prove that for $c = ab-...
Gang men's user avatar
  • 425
1 vote
0 answers
20 views

Bound on minimimal non-negative linear diophantine equation in two variables

I want to find an upper bound for the minimization problem $\min x+y$ subject to $x\geq 0, y \geq 0, -Ax+By=C, (x,y)\in \mathbb{Z}^2$ where $A, B$ are non-negative constants. I've seen that there are ...
samabu's user avatar
  • 723
0 votes
2 answers
258 views

How many solutions to this Diophantine equation group of Com Quantum Theory? Does it have a general solution method?

$\begin{gathered} \frac{{{x_1} + 2{x_2} + {2^2}{x_3} + {2^3}{x_4} + {2^4}{x_5}}}{{2\left( {{x_6} + 2{x_7} + {2^2}{x_8} + {2^3}{x_9} + {2^4}} \right)}} = \frac{{1034}}{{1625}} \hfill \\ \frac{{{x_1}...
X. D. Dongfang's user avatar
2 votes
3 answers
198 views

Is there a way to find the values of 3 variables with just one equation?

I was doing a personal project until I came upon this equation that i need to solve to continue, the thing is I don’t thing I have been thought this in math ever so i wonder if this even possible to ...
Vin's user avatar
  • 21
1 vote
0 answers
46 views

minimum solutions for linear Diophantine equation in n variables

As we know for the most simple Diophantine equation $ax+by=1$ for positive $a,b$ if $1\le x\le b-1$ then $-(a-1)\le y\le -1$ but what if we have n variables and not just two , if equation be equals to ...
ssd's user avatar
  • 11
0 votes
0 answers
82 views

What is the complexity of solving this specific System of Diophantine Equations?

Given a set of linear Diophantine equations such that: There are $3N$ equations. The equations consist of $4N$ unique variables. Each equation is of the form: ($a_0$+$a_1$)=($a_2$+$a_3$) or ($a_0$+$...
xyz's user avatar
  • 47
1 vote
1 answer
56 views

Finding the biggest $k\leq k_0$ such that the interval $k[A, B]$ contains an integer

Question Let $0<A<B$ be rational numbers (with possibly large denominators) and $k_0$ a natural number. What is the biggest $k \in \{0,1,\dots, k_0\}$ such that the interval $[kA, kB]$ contains ...
ploosu2's user avatar
  • 9,588
-2 votes
1 answer
57 views

Consecutive integers 8p, 9q, 10r: search for small solution sets (p,q,r) other than (1,1,1). [duplicate]

The context: I want to show how prime factorisation patterns repeat along the number line. I've taken three consecutive integers, the first containing 2^3, the second 3^2, the third 5^1. Taking ...
Paul Stephenson's user avatar
3 votes
1 answer
111 views

Given $n$ integers $a_1$ to $a_n$ and an integer $K$, does there exist a solution which satisfies the following equation?

Given $n$ integers $a_1$ to $a_n$ and an integer $K$, does there exist a solution which satisfies the following equation? $$\sum_{i=1}^n a_i\cdot x_i = K $$ Note that all $x_i$ must need to be NON-...
user avatar
0 votes
0 answers
27 views

Solving $c = ab$ in $(\mathbb{Z}_n,+)$ [duplicate]

I need some help solving b). My approach is the following: I solved a) as follows: a is a unit, find it's inverse using the extended eucledian algorithm. For b). If c is not a unit, no problem, jsut ...
Anton2107's user avatar
1 vote
1 answer
50 views

Can $c^2(a\cdot b)+c(a+b)=2^c-2$ be solved to find $\mathbb{N}$ solutions?

$c^2(a\cdot b)+c(a+b)=2^c-2$ is of the form $mx+ny=k$ and should open the door to Diophantine, but do the constraints $x=(a\cdot b), y=(a+b)$ make a difference when trying to solve for $\mathbb{N}$ ...
JohnDNoone's user avatar
1 vote
2 answers
340 views

Let p be a prime. Prove that $x^4 + 4 y^4 = p$ has integer solutions if and only if $p = 5$. In this case, find the solutions for x and y.

I have tried to factor $$x^4 + 4 y^4 = p$$ using the Sophie Germain's Identity, as someone suggested in the comments, which yields: $$((x+y)^2 + y^2)((x-y)^2 + y^2) = p$$ Since p is a prime, either $$(...
user3347814's user avatar
-1 votes
3 answers
97 views

Is there an algorithm to simplify solutions of linear Diophantine Equations?

I will use the following equation as an example: $$3x + 5y = 47$$ We know that $gcd(3,5) = 1 | 47$ so, this equation has a solution. In order to find it, we can use the euclidean algorithm and the ...
user3347814's user avatar
1 vote
1 answer
153 views

How to show the equation $ax+by+cz=n$ always have nonnegative solutions?

Consider integers $a,b,c\geq1,$ such that gcd$(a,b,c)=1.$ Show that there exists an integer $n_0$ such that for all $n\geq n_0,$ one can find nonnegative integers $x,y,z$ such that $ax+by+cz=n.$ My ...
Chang's user avatar
  • 187
1 vote
0 answers
73 views

Structure of linear Diophantine system

I am learning about the linear system of Diophantine equations. I have noticed that the solution structure of the Diophantine equation is quite similar to the general system of linear equations. It is ...
lovemath's user avatar
3 votes
1 answer
584 views

Given that the positive integers $x>1$ and $y$ satisfy $2007x-21y=1923$. Find sum of digits of minimum value of $2x+3y$.

Given that the positive integers $x>1$ and $y$ satisfy $2007x-21y=1923$. Find sum of digits of minimum value of $2x+3y$. Here we have to solve for two variables using only one equation. How is ...
user avatar
1 vote
0 answers
37 views

I want to find all possible solution for the equation $x+2y+3z = V$, where $0\le x+y+z\le 5$, and $0\le x,y,z$.

Using modular arithmetic, I have derived that for the equation $x + 2y + 3z= v$ has solutions for any pair of integers, $k$ and $m$, where $x = \frac{-v - 2v_3 + 3v_2}{6} + k - m$, $y = -2x -3m - v_3$,...
Nikolas Koutroulakis's user avatar
1 vote
0 answers
235 views

Computing Smith normal form of matrix of integers

I known that the Smith normal form of $A$ provides two unimodular matrices $U$ and $V$ of respective dimensions $m \times m$ and $n \times n$ such that the matrix $$B=[b_{i,j}]=UAV$$ and B has the ...
lovemath's user avatar
0 votes
0 answers
212 views

Minimal solution to a linear Diophantine equation

I solved many linear diophantine equation, but i found some exercises where, in addition to find the general solution of the equation, i have to find the minimal solutions of it. I've found a similar ...
emSingularity's user avatar
1 vote
0 answers
61 views

Solving a system of Diophantine equation

Suppose I have this binary recurrent sequence $\{B_{n}\}$ called balancing sequence, satisfying $B_{n} = 6B_{n-1}-B_{n-2}$ with initial terms $(B_{0},B_{1}) = (0,1).$ This sequence has following ...
Atratrana Suna's user avatar
1 vote
0 answers
499 views

100 fowls problem

If a cock is worth 5 qians, a hen 3 qians, and three chicks together 1 qian, how many cocks, hens, and chicks, totaling 100, can be bought for 100 coins? So if , $x$ is the number of cocks, $y$ is the ...
user avatar
0 votes
1 answer
144 views

Integer row reduction without scalar multiplication

For which matrices is it possible to find the (unreduced, and with arbitrary pivot) Echelon form of a matrix following Gaussian elimination, but only with the row operations: Adding/subtracting one ...
Cameron's user avatar
  • 429
0 votes
4 answers
433 views

The number of non-negative integer solutions of $ax+by=k$

A linear equation in one variable $x$, $$ax+b=k$$ has only one non-negative integer solution. For example, $2x+3=85$ has a solution 41. How to find the number of non-negative integer solutions of a ...
user avatar
1 vote
1 answer
515 views

The equation 5x+7y=k has 7 solutions in which both x and y are non negative integers. What is the minimum value of k? [duplicate]

My approach: Upon solving this Diophantine equation , I get my generalized solutions as: $5(3k+7t) + 7(-2k-5t) = k$ where $t$ is an integer Now its given that x and y are non-negative integers ...
Fin27's user avatar
  • 958

1
2 3 4 5 6