Intereting Posts

Solving $13\alpha \equiv 1 \pmod{210}$
What exactly is the Probability Integral Transform?
Expanding $\frac{\Gamma(n)}{\Gamma(n-k)}$ as a polynomial
Need help with an integral
Difference of $n$-th power of two consecutive integers
Showing there is a prime in a ring extension using Nakayama's lemma
Determine the coefficient of polynomial det(I + xA)
Group theory – prove that $\forall x((x^{-1})^{-1}=x)$
Can you prove why Popsicle Stick Multiplication works?
Solving Differential Functional Equation $f(2x)=2f(x)f'(x)$
First-order nonlinear ordinary differential equation
Matrix Theory book Recommendations
a question about behavior of functions whose graphs are rectifiable curves
Is it true that $p\mid $?
Arranging identical balls

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?

- Find remainder of $F_n$ when divided by $5$
- Show that $2^n$ is not a sum of consecutive positive integers
- Show that for any prime numbers $p,q,r$, one has $p^2+q^2 \ne r^2$.
- Can an integer of the form $4n+3$ written as a sum of two squares?
- conjectured new generating function of fibonacci numbers
- The system of genus characters determined by a binary quadratic form

- Is there a “nice” formula for $\sum_{d|n}\mu(d)\phi(d)$?
- How to use fundamental theorem of arithmetic to conclude that $\gcd(a^k,b^n)=1$ for all $k, n \in$ N whenever $a,b \in$ N with $\gcd(a,b)=1$?
- Prove that if the equation $x^{2} \equiv a\pmod{pq}$ has any solutions, then it has four solutions.
- For $n \geq 2$, show that $n \nmid 2^{n}-1$
- Prove that $\sqrt{p}$, $\sqrt{q}$ and $\sqrt{r}$ cannot be in the same arithmetic progression
- Is Pigeonhole Principle the negation of Dedekind-infinite?
- What five odd integers have a sum of $30$?
- Proving that the square root of 5 is irrational
- $13$ is the largest prime that can divide two successive integers of the form $n^2+3$
- Elementary Number Theory Congruence Proof

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.

- Asymptotic behavior of Harmonic-like series $\sum_{n=1}^{k} \psi(n) \psi'(n) – (\ln k)^2/2$ as $k \to \infty$
- $p$ prime, $1 \le k \le p-2$ there exists $x \in \mathbb{Z} \ : \ x^k \neq 0,1 $ (mod p)
- Field axioms: Why do we have $ 1 \neq 0$?
- $S := \{x \in \Bbb R^3: ||x||_2 = 1 \}$ and $T: S^2 \to \Bbb R$ is a continuous function. Is $T$ injective?
- Where can I learn about the lattice of partitions?
- What is the name of this shape?
- If $P(x)=2013x^{2012}-2012x^{2011}-16x+8$,then $P(x)=0$ for $x\in\left$ has
- Visualizing products of $CW$ complexes
- Is there a subfield $F$ of $\Bbb R$ such that there is an embedding $F(x) \hookrightarrow F$?
- A completely continuous operator carries weakly Cauchy sequences into norm-convergent ones
- What actually is a polynomial?
- A diophantine equation
- sum of arctangent
- $g'(x) = \frac{1}{x}$ for all $x > 0$ and $g(1) = 0$. Prove that $g(xy) = g(x) + g(y)$ for all $x, y > 0$.
- Proving a harmonic denominator is largest number NOT divisible by a number $y$