Skip to main content
19 votes

How to find solutions of linear Diophantine ax + by = c?

Here's another method. It doesn't require finding an initial solution, but it may require finding a modular multiplicative inverse. (Edit: I'll show this method with an example instead of a ...
user236182's user avatar
  • 13.3k
9 votes
Accepted

Number of positive unequal integer solutions of $x+y+z+w=20$

HINT: Each solution of the desired type is a permutation of a solution in which $x<y<z<w$, and every permutation of such an increasing solution is of the desired type. Each increasing ...
Brian M. Scott's user avatar
9 votes

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

Use the Euclidean Algorithm to find the gdc of $5$ and $12$. $$12=5\times2+2$$ $$5=2\times2+1$$ Then apply the extended Euclidean Algorithm, (do the initial algorithm in reverse with back-substitution)...
Harry Alli's user avatar
  • 2,101
8 votes

Determining the existence of solutions to the linear Diophantine equation $ax + by = c$

Here is an outline of an answer based on Section 5.1, "The Equation $ax + by = c$," of I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (...
user0's user avatar
  • 3,277
8 votes
Accepted

How many distinct values of $x_1+x_2+x_3+x_4+x_5+x_6+x_7$ when $x_1,x_2,x_3,..,x_7 \in \{0,3,4,5\}$

Clearly, we have $0\leq A\leq 35$, so there are at most $36$ possibilities. Also clearly $A\neq 1,2$. In fact any other $A$ is possible. (Maybe you can prove this yourself; if not there is a spoilered ...
Especially Lime's user avatar
8 votes
Accepted

How to solve a system of linear equations modulo n?

First you can multiply the system by any number that has an inverse, that is $\gcd(x,20)=1$. So in particular you cannot multiply or divide by $2,4,5,10$ as you would not multiply or divide by $0$ in ...
zwim's user avatar
  • 28.7k
7 votes

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

You can reduce each of your five equations to a linear equation so you get a system of five linear equations with nine unknowns $$a_{11}x_1+\cdots a_{19}x_9=c_1\\a_{21}x_1+\cdots a_{29}x_9=c_2\\.........
Piquito's user avatar
  • 29.9k
6 votes

Number of positive unequal integer solutions of $x+y+z+w=20$

By inclusion-exclusion over the distinctness conditions: There are $\binom{20-1}3=\binom{19}3$ solutions disregarding the conditions. There are $\binom42$ ways to choose one pair that fails to be ...
joriki's user avatar
  • 239k
6 votes
Accepted

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

I think Hardy is asking for conditions on $(a,b,c)$, to be given in terms of $(A,B,C)$ and $(\alpha,\beta,\gamma)$. The $(x,y,z)$ are dummy variables, note the "for all". For (1), which $(a,b,c)$ are ...
ancient mathematician's user avatar
6 votes

Using gcd Bezout identity to solve linear Diophantine equations and congruences, and compute modular inverses and fractions

Yes, it's well-known and occurs here many times, e.g. here where it is special case $\,b\! =\! 1\,$ below of the solvability criterion for a general linear congruence $\quad\ \, \exists\, x\in\Bbb Z\!...
Bill Dubuque's user avatar
5 votes
Accepted

Number of solutions of: $3x+y=5702$

I'll find all the integer solutions of $3x+y=5702$. First, mod $3$ gives $y\equiv 2\pmod{3}$. Let $y=3k+2$, $k\in\mathbb Z$. $$3x+3k+2=5702\iff 3(x+k)=5700$$ $$\iff x+k=1900\iff x=1900-k$$ All the ...
user236182's user avatar
  • 13.3k
5 votes
Accepted

Find the number of integer solutions of $|x|+|y| \le 10$

The number of integer solutions of $|x|+|y|\le n$ is $$1+4n+4\sum_{k=1}^{n-1} k=2n(n+1)+1.$$ $1$ is for the origin, $4n$ is for the points on the 4 semi-axis, and finally $4\sum_{k=1}^{n-1} k$ counts ...
Robert Z's user avatar
  • 146k
5 votes
Accepted

How can I solve the folowing Diophantine equation with two unknowns?

Hint $\ $ This type of diophantine equation is solvable by a generalization of completing the square. Namely, completing a square generalizes to completing a product, using the AC-method, viz. $$\...
Bill Dubuque's user avatar
5 votes

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

The Euclidean algorithm is best for large numbers, but for a small example like this, trial and error, combined with a little modular arithmetic works just fine, and is less work. Reducing $5a−12b=13$...
saulspatz's user avatar
  • 53.2k
5 votes
Accepted

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

If $(x,y)$ and $(x',y')$ are two of the eleven solutions, then $x'=x+13t$, $y'=y-12t$ for some integer $t$. Hence the $11$ solutions will be of the form $x=x_0+13t$, $y=y_0-12t$ with $t$ ranging over $...
Hagen von Eitzen's user avatar
5 votes
Accepted

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

You wish to solve the system $Ax=b$ over $\Bbb Z$ where \begin{align*} A &= \left[\begin{array}{rrrr} -5 & 2 & 4 & 1 \\ 27 & 10 & 2 & 7 \\ -20 & -6 & 0 & -4 \...
Brian Fitzpatrick's user avatar
5 votes

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$?

As has been suggested by @Robert Shore, transform the problem to $4x_1 + 3x_2 +2x_3 + x_4 = 41,\; x_i \in N$ Now when multinomials in $x$ are multiplied together, the exponents get added up, so if we ...
true blue anil's user avatar
4 votes

Check whether positive integral solution $(x,y)$ exists for $ax + by = n$

Note that $\mathbb Z^+ = \{1,2,3,\dots\}.$ The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers $a,b$, the ...
Steven Alexis Gregory's user avatar
4 votes
Accepted

How to show that $2x + 3y + 5z$ generate all integers greater than 2

In fact, $2x+3y$ generates all integers greater than $2$. If $n$ is even, we put $n = 2k + 3(0)$. If $n$ is odd, we put $n = 2k+1 = 2(k-1) + 3 \cdot 1$.
This account was hacked's user avatar
4 votes
Accepted

Number of solutions to $a + 10b + 20c = 100$ with $a,b,c$ non-negative integers

You can simplify fairly drastically, since $a = 100-10b-20c$ means $a$ must be a multiple of $10$. So setting $a' := a/10$, we have $a' + b + 2c = 10$. Again $a'$ is determined by $b$ and $c$, so ...
Joffan's user avatar
  • 39.8k
4 votes

How to solve a system of linear equations modulo n?

\begin{eqnarray} 4x - 10y \equiv 8\pmod {20} \\ 7x + 2y \equiv 5\pmod {20} \end{eqnarray} Method 1 - Take advantage of a unit coefficient (7) \begin{align} 7x + 2y &\equiv 5\pmod {20} \\...
Steven Alexis Gregory's user avatar
4 votes

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

Guide: Since we know that $5$ and $12$ are coprime, use Eucliean Algorithm to find $x, y \in \mathbb{Z}$ such that $$5x+12y = 1$$ After which, multiply the equation by $13$. In general to solve for ...
Siong Thye Goh's user avatar
4 votes

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

Write the equation in terms of another variable: $$5a-12b=13 \iff a=\frac{13}{5}+\frac{12}{5}b$$ Now you just need to see that $13+12b \equiv 0 \pmod{5} \iff 12(b+1)+1 \equiv 0 \pmod{5} \Rightarrow ...
Rakete1111's user avatar
4 votes
Accepted

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

Since $\gcd (152207,81103)=1111$ it is the same as minimum of $$1111(137x-73y)$$ Since $137x-73y=1$ is solvable (say $x=8$ and $y=15$) the answer is $1111$.
nonuser's user avatar
  • 90.3k
4 votes

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

Note $c=ax+by$ has integer solution if and only if $gcd(a,b)|c$ and if this exists then infinite no of integer solutions can be obtained from 1 solution by $x=x_{0}+\frac{b}{d}k$ and $y=y_{0}-\frac{...
NewBornMATH's user avatar
4 votes
Accepted

$\mathbb{Z}$-Module exercise

Well, $M$ is the kernel of the map $$ f:\mathbb{Z}^3\to\mathbb{Z}^3,\;\;\begin{pmatrix}x\\y\\z\end{pmatrix}\mapsto\begin{pmatrix}-3x+5y+3z\\-6x+20y+9z\\-3x+25y+9z\end{pmatrix} $$ Using the standard ...
David Hill's user avatar
  • 12.2k
4 votes
Accepted

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

Simpler: $\bmod 9\!:\ \underbrace{\overbrace{n^2\equiv \color{#0a0}{-n}-1}^{\textstyle \color{#0a0}{-n}\equiv 5a\!+\!4b}}_{\textstyle (n\!-\!4)^2\equiv\color{#c00}{-3}} \:$ has no roots by $\,\...
Bill Dubuque's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible