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+2$$ $$5=2\times2+1$$ Then apply the extended Euclidean Algorithm, (do the initial algorithm in reverse with back-substitution) $$1=5-2\times2$$ $$1=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=37$$ $$a_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=35$$ $$b_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