Intereting Posts

$A,B$ be Hermitian.Is this true that $tr\le tr(A^2B^2)$?
Is this function holomorphic at 0?
Baby Rudin Theorem 1.20 (b) Proof
Prove that the set of palindromes are not regular languages using the pumping lemma.
Is $e^x=\exp(x)$ and why?
Comparing Category Theory and Model Theory (with examples from Group Theory).
A union of two subspaces not equal to the vector space.
On Martingale betting system
Let $A$ and $B$ be $n \times n$ real matrices such that $AB=BA=0$ and $A+B$ is invertible
Relating $\operatorname{lcm}$ and $\gcd$
Why is $|x|$ not differentiable at $x=0$?
Is there an integral for $\pi^4-\frac{2143}{22}$?
Prove DeMorgan's Theorem for indexed family of sets.
Expected Value Function
Is First Order Logic (FOL) the only fundamental logic?

I’m having trouble solving the following diophantine equation:

$8x + 13y = 1571$

For all the other examples I’ve worked through I’ve been able to use the euclidean algorithm and the solution shows up somewhere. That doesn’t work in this case, and the $\text{gcd}(8, 13) = 1$, so I know a solution exists. So how would you solve a problem like this?

- Proving that there are at least $n$ primes between $n$ and $n^2$ for $n \ge 6$
- how to calculate double sum of GCD(i,j)?
- How many pairs of numbers are there so they are the inverse of each other and they have the same decimal part?
- Practical method of calculating primitive roots modulo a prime
- $ 0 < a < b\,\Rightarrow\, b\bmod p\, <\, a\bmod p\ $ for some prime $p$
- Basic question on primitive roots

- How to prove Lucas's Converse of Fermat's Little Theorem without using primitive root?
- $2^a +1$ is not divisible by $2^b-1$.
- Proof of irrationality of square roots without the fundamental theorem of arithmetic
- Existence of $\sqrt{-1}$ in $5$-adics, show resulting sum is convergent.
- How to prove that $z\gcd(a,b)=\gcd(za,zb)$
- Is there only one pair of unequal rational numbers with $n^m = m^n$?
- Prove that, $(2\cdot 4 \cdot 6 \cdot … \cdot 4000)-(1\cdot 3 \cdot 5 \cdot …\cdot 3999)$ is a multiple of $2001$
- Solving Equation through inequalities.
- Are there infinitely many primes and non primes of the form $10^n+1$?
- For which $n$'s $2^n\mid n!$?

Start by solving the equation $8s+13t=1$. You can do this by inspection, for $s=-8$, $t=5$ obviously works. Or else you can use the machinery of the Euclidean Algorithm.

So $x_0=(-8)(1571)$, $y_0=(5)(1571)$ is a solution of the equation we were given.

All solutions of that equation are given by $x=x_0+13t$, $y=y_0-8t$, where $t$ ranges over the integers.

**Remark:** We need not have started from a solution of $8s+13t=1$. The only reason we did it that way was to connect the solution with material that you have already covered.

If we find **any** particular solution $(x_1,y_1)$ of our equation, then all solutions are given by $x=x_1+13t$, $y=y_1-8t$.

If you have done Linear Algebra, or Differential Equations, you have seen this kind of thing before. We got the *general* solution of our equation by taking a *particular* solution, and adding the *general* solution of the homogeneous equation $8x+13y=0$.

Expanding as continued fraction we get $$\frac{13}8=1+\frac58=1+\frac1{\frac85}=1+\frac1{1+\frac35}$$

$$=1+\frac1{1+\frac1{\frac53}}=1+\frac1{1+\frac1{1+\frac23}}$$

$$=1+\frac1{1+\frac1{1+\frac1{\frac32}}}=1+\frac1{1+\frac1{1+\frac1{1+\frac12}}}$$

So, the last convergent is $$1+\frac1{1+\frac1{1+\frac1{1}}}=\frac53$$

Using the convergent property of continued fraction, $$ 8\cdot 5-13\cdot3=1$$

So, $$8x+13y=1571(8\cdot 5-13\cdot3)$$

$$8(x-5\cdot1571)=-13(3\cdot1571+y)$$

$$\frac{13(3\cdot1571+y)}8=5\cdot1571-x$$ which is an integer

So, $$8\mid 13(3\cdot1571+y)\implies 8\mid (3\cdot1571+y)\text{ as }(8,13)=1$$

$3\cdot1571+y\equiv0\pmod 8\iff 3\cdot3+y\equiv0\pmod 8$ as $1571\equiv3\pmod8$

$\implies y\equiv-9\pmod8\equiv7\implies y=8a+7$ for some integer $a$

Using Euclidean algorithm you will find $x’,y’\in\mathbb Z$ such that $8x’+13y’=1$. Multiplying through by 1571 we get $8(x’\cdot1571)+13(y’\cdot1571)=1571$.

Now set $x=x’\cdot1571$ and $y=y’\cdot1571$. How about all solutions?

$\rm 8x\!+\!13y = k = 3\!+\!8j\:\Rightarrow\:mod\ 8\!:\ 13y\equiv 3\:\Rightarrow\:y \equiv \dfrac{3}{13} \equiv \dfrac{3}{{-}3}\equiv -1\:\Rightarrow\: \color{#c00}{y = -1\!+\!8n}$

$$\rm\Rightarrow\ \ \ x\, =\, \dfrac{k\!-\!13\,\color{#c00}y}8\,=\, \dfrac{ 8j\!+\!3 \!-\!13\,(\color{#c00}{-1\!+\!8n})}8\,=\, j\!+\!2\!-\!13n$$

Your special case is $\rm\ k = 1571 = 3 + 8\cdot 196,\:$ so $\rm\ j = 196,\ $ so $\rm\ (x,y) = (198,-1) + n(-13,8)$

**Hint:** $~8x+(8+5)y=8\cdot196+3\iff8~(x+y-196)+5y=3=8-5.~$ Can you take it from here ? ðŸ˜‰

8x + 13y = 1571 is equivalent to 8x = 1571(mod 13) which reduces 8x = 11(mod13).

Solving x = 3(mod 13) or x = 3 + 13k. Substituting this x back into the original equation you get y = 119 – 8k. The complete solution is x = 3 + 13k and y = 119 – 8k. Recently, on this site I discovered the Euclid – Wallis Algorithm. This algorithm computes the gcd(m,n), solves the Diophantine equation mx + ny = gcd(m,n) and yields the continued fraction of m/n. This algorithm accomplishes all of this by a series of multiplications and subtractions. Using this algorithm I got x = 7855 – 13k and y = -4713 + 8k which is equivalent to the answer above and equivalent to the Extended Euclidean Algorithm.

- Free Schroedinger equation
- Newton's method vs. gradient descent with exact line search
- Cardinality of the set $D$
- Is there any simple trick to solve the congruence $a^{24}\equiv6a+2\pmod{13}$?
- showing Cohen-Macaulay property is preserved under a ring extension
- How do I get $\cos{\theta} \lt \frac{\sin{\theta}}{\theta} \lt 1$?
- Proving that $D_{12}\cong S_3 \times C_2$
- Show that the Beta Function $\beta (x,y)$ Converges When $x \gt 0, \space y \gt 0$
- Proof of a Ramanujan Integral
- Dirac $\delta\left( \left^2 -k^2-m^2 \right)$
- What does an outer automorphism look like?
- $e^{1/z}$ and Laurent expansion
- proof that $\int_{a}^{x} = \int_{x}^{b}$
- Which field is it?
- Equivalent of $ x(x+1)(x+2)\cdots(x+n)$?