# Tag Info

## Hot answers tagged linear-diophantine-equations

46

Using the Euclid-Wallis algorithm (described below) $$\begin{array}{r} &&4&2&1&7\\\hline 1&0&1&-2&3&-23\\ 0&1&-4&9&-13&100\\ 100&23&8&7&1&0\\ &&&&{\uparrow}&{\star} \end{array}$$ lookng below the horizotal line, the top row times $100$ plus the middle row ...

28

$100x -23y = -19$ if and only if $23y = 100x+19$, if and only if $100x+19$ is divisible by $23$. Using modular arithmetic, you have \begin{align*} 100x + 19\equiv 0\pmod{23}&\Longleftrightarrow 100x\equiv -19\pmod{23}\\ &\Longleftrightarrow 8x \equiv 4\pmod{23}\\ &\Longleftrightarrow 2x\equiv 1\pmod{23}\\ &\Longleftrightarrow x\equiv 12\... 11 HINT \displaystyle\rm\ \ mod\ 23:\ x\: \equiv\: \frac{-19}{100}\: \equiv\: \frac{4}{100}\: \equiv\: \frac{1}{25}\: \equiv\: \frac{24}{2}\: \equiv\: 12\:,\  i.e. \rm\ x\: =\: 12 + 23\ n\:. 9 More direct path to a+b+c = 12: Write x=a+b+c. In particular the last equation implies 31 x \ge 365 so x>11. On the other hand, the first equation is 28x + 2b + 3c = 365. If either b or c is nonzero, this means 28x < 364 so x < 13. And b=c=0 is not possible because 365 is not divisible by 28. added: to be fair I should ... 8 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 solution has 4!=24 permutations, so you need only count the increasing solutions and multiply by 24. Added: This can be done fairly easily by brute force. For ... 8 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 explanation below.) So the answer is 34. 8 Use the Euclidean Algorithm to find the gdc of 5 and 12.12=5\times2+25=2\times2+1$$Then apply the extended Euclidean Algorithm, (do the initial algorithm in reverse with back-substitution)$$1=5-2\times21=5-2\times(12-5\times2)1=5\times5-2\times12$$Then multiply throughout by 13$$13=65\times5-26\times12$$This gives you a ... 7 In the world of combinatorics, you can use something commonly known as the "stars and bars" method. Generally put, the equation$$x_1+x_2+\ldots+ x_k = s$$where s,x_i are positive integers has \binom{s-1}{k-1} many solutions. The quantity \binom{s-1}{k-1} is called a binomial coefficient. A general binomial coefficient \binom{a}{b} where a,b are ... 7 If you take the equation mod 23, you find 8x \equiv 4 \pmod{23} and by inspection, this is satisfied by x \equiv 12 \pmod{23}. To find this, you use the Extended Euclidean algorithm 6 Since 2 and 3 are coprime, every integer solution (a,b) of 2a+3b=2015 is of the form a=1+3k,b=671-2k for some integer k. In order that both a and b are positive, k must lie between 0 and 335, hence there are \color{red}{336} positive integer solutions. 6 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 generalization. It may make it more clear.) Solve 2x+3y=5. 2x\equiv 5\pmod{3}. You could either find a multiplicative inverse: x\equiv 5\cdot 2^{-1}\pmod{3} Or ... 6 Hint: The right hand side is always divisible by _____ no matter what integers x and y you pick. 6 Let us assume there are a,b,c \in \mathbb{Z},ac \neq 0 such that a \sqrt 2 − b = c \sqrt5$$b=a\sqrt{2} -c\sqrt{5}b^2=2a^2+5c^2-2ac\sqrt{10}\sqrt{10}=\frac{2a^2+5c^2-b^2}{2ac}\implies \sqrt{10} \space \text{is rational (contradiction)}$$EDIT: As suggested by A.P., we will need to rule out the cases when a=0 and when c=0 for a ... 6 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 orthogonal to all vectors? Answer, clearly only the zero vector, so (a,b,c)=(0,0,0). For (2), which (a,b,c) are orthogonal to all vectors which are ... 5 \gcd(9,15) = 3 Since 3 does not divide 61, no such numbers can be found. 5 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 integer solutions are (x,y)=(1900-k,3k+2), k\in\mathbb Z.$$x+y=(1900-k)+(3k+2)=2k+1902\le 2003\iff k\le 50.5\iff k\le 50$$Natural numbers ... 5 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 the points in the 4 right triangles inside the 4 quadrants. See also the Sloane' sequence https://oeis.org/A001844 5 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.$$\begin{eqnarray} &&axy + bx + cy\, =\, d,\ \ a\ne 0\\ \overset{\times\,a}\iff\, &&\!\! (ax+c)(ay+b)\, =\, ad+bc\end{eqnarray}\qquad\qquad$$So the ... 5 We are asked to find integer solutions for x,y. We can get particular solutions simply by plugging in values. Our first solution is obtained as: y’ = 3 and x’ = 13. Thus, the general solution for x will be:$$x = x’ + bn = 13 + 17n$$Hence lower limit for n is n \geq 0. Now we’ll find upper limit using given restriction x \leq 500. Plugging ... 5 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 modulo 12, we have a\equiv 1 \pmod{12}, and a\equiv 5 \pmod{12}, by trial. Then it's clear that a=5, b=1 is a solution. Alternatively, we might ... 4 Hint \  For \rm A\: linear, \rm\ A\:X_1\! = B = A\:X_2 \ \iff\ 0 \:=\: A\:X_1\! - A\:X_2 = A\:(X_1\!-X_2) This implies that the general solution of \rm\,\ A\:X = B\,\  is the sum of any particular solution plus a solution of the associated homogeneous equation \rm\ A\:X = 0.\: This property holds true for every linear operator, e.g. for ... 4 I think there is no correct option. The system is equivalent to$$a_1+a_2=37a_3+a_4+a_5=10$$Let b_i=a_i-1. Then, b_i are non-negative integers. So, the system is equivalent to$$b_1+b_2=37-2=35b_3+b_4+b_5=10-3=7$$Then, here you can use the method you wrote, so we have$$\binom{36}{1}\times\binom{9}{2}=\color{red}{1296}.$$4 It has solution because 1=\text{gcd}(2,3)\mid 5. Let (x_0, y_0) any solution of 2x+3y=5 i.e. for example x_0=y_0=1. Let (x,y) any other solution i.e. 2x+3y=5. Subtracting we get: 2(x-1)=3(1-y). Hence 1-y=2t and x-1=3t. Then any general solution can be find by generating formula:$$(3t+1, 1-2t), \quad t\in \mathbb{Z}.$$4 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 we just need b+2c\le 10. For c=\{0,1,2,3,4,5\} we have \{11,9,7,5,3,1\} options for b, for a total of 36 possible combinations. 4 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$$Aa-Bb=C$$where A,B, C is given. Use euclidean algorithm to find \gcd(A,B)=D, if D doesn't divide C, then there is no integer solutions. Otherwise, ... 4 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 b + 1= 5x +2,\, \forall x\in \mathbb{Z}. So the solutions have the form (by substituting b=5x+1 in the original equation)$$a=12x+5, b = 5x+1, \, \forall x\...

4

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 $11$ consecutive integers, wlog over the integers $\{0,1,\ldots,10\}$. As $t=-1$ does not lead to a solution, we conclude $x_0-13<0$. As $t=11$ does not lead ...

4

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

4

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{a}{d}k$ where $d$ is the gcd. And $x_{0},y_{0}$ are one solution which can be obtained from euclid's algorithm. (As will jagy has mentioned) And also the ...

4

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 basis $\{e_1,e_2,e_3\}$ for $\mathbb{Z}^3$, we can represent $f$ above as a matrix  A=\begin{pmatrix}-3&5&3\\-6&20&9\\-3&25&9\end{...

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