Intereting Posts

Union of two self-intersecting planes is not a surface
Sum with binomial coefficients: $\sum_{k=1}^m \frac{1}{k}{m \choose k} $
An integral that might be related to the modified Bessel function of second kind
Representation of Algebraic Extensions by Matrices
Solution to Locomotive Problem (Mosteller, Fifty Challenging Problems in Probability)
Intuition Building: Visualizing Complex Roots
Computation of the probability density function for $(X,Y) = \sqrt{2 R} ( \cos(\theta), \sin(\theta))$
Show that the odd prime divisors of the integer $n^2+n+1$ which are different from $3$ are of the form $6k+1$.
Intersection of a closed set and compact set is compact
Sum : $\sum_{n=0}^\infty \frac{(-1)^n}{(2n+1)^3}$
What kind of rings have exactly three ideals?
On a “1-D line”, the point that minimizes the sum of the distances is the median, WHY?
Does weak convergence in Sobolev spaces imply pointwise convergence?
A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets
What are the quadratic extensions of $\mathbb{Q}_2$?

I have to find the greatest common divisor of $a=78$ and $b=132$.

I have worked out to

$$\begin{align}

132 & = 78 \times 1 + 54 \\

78 & = 54 \times 1 + 24 \\

54 & = 24 \times 2 + 6 \\

24 & = 6 \times 4 + 0

\end{align}$$

- Finding prime factors by taking the square root
- Finding an MST among all spanning trees with maximum of white edges
- Fastest way to calculate $e^x$ up to arbitrary number of decimals?
- How to construct magic squares of even order
- Minimum Sum that cannot be obtained from the 1…n with some missing numbers
- splitting polygon in 4 equal parts

and back substituted

$$\begin{align}

6 & = 54 – 24 \times 2 \\

& = 54 – (78 – 54) \times 2 \\

& = 3 \times 54 – 78 \times 2

\end{align}$$

However I don’t seem to be able to work back to $132$ ?

Can someone explain / help?

- Show that a Sophie Germain prime $p$ is of the form $6k - 1$ for $p > 3$
- Smallest positive integer that gives remainder 5 when divided by 6, remainder 2 when divided by 11, and remainder 31 when divided by 35?
- Finding all the numbers that fit $x! + y! = z!$
- Fermat: Prove $a^4-b^4=c^2$ impossible
- Why is sorting pancakes NP hard?
- Can decimal numbers be considered “even” or “odd”?
- Proving that $ 30 \mid ab(a^2+b^2)(a^2-b^2)$
- What is wrong with this proof that there are no odd perfect numbers?
- Simple algorithm for generating Poisson distribution
- If $s$ is a multiple of both $a$ and $b$, then $s$ is a multiple of $\operatorname{lcm}(a,b)$

As you’ve experienced first-hand, back-substitution is messy and can lead to errors. It’s better to append an identity-augmented matrix to accumulate the Bezout identity as you compute the Euclidean remainder sequence, e.g. below (from an old post – tailored to your example)

```
For example, to solve mx + ny = gcd(x,y) one begins with
two rows [m 1 0], [n 0 1], representing the two
equations m = 1m + 0n, n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,
Here is an example: d = x(132) + y(78) proceeds as:
in equation form | in row form
----------------------+------------
132 = 1(132) + 0(78) |132 1 0
78 = 0(132) + 1(78) | 78 0 1
row1 - row2 -> 54 = 1(132) - 1(78) | 54 1 -1
row2 - row3 -> 24 = -1(132) + 2(78) | 24 -1 2
row3 - 2 row4 -> 6 = 3(132) - 5(78) | 6 3 -5
row4 - 4 row5 -> 0 =-13(132) + 22(78) | 0 -13 22
Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,
row1 row2 row3 row4 row5
namely: 132, 78, 54, 24, 6 = Euclidean remainder sequence
| |
for example 54-2(24) = 6, the 3rd step in Euclidean algorithm
becomes: row3 - 2 row4 = row5 on the identity-augmented matrix.
In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:
[ 3 -5] [132 1 0] = [6 3 -5]
[-13 22] [ 78 0 1] [0 -13 22]
The 1st row is the particular solution: 6 = 3 (132) - 5 (78)
The 2nd row is the homogeneous solution: 0 = -13(132) + 22(78),
so the general solution is any linear combination of the two:
n row1 + m row2 -> 6n = (3n-13m) 132 + (22m-5n) 78
The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
```

From the first equation you have $54=132-78$.

By plugging this into the last one you get $6=3(132-78)-2\cdot78=3\cdot132-5\cdot78.$

- $D_6 \cong D_3\times \mathbb Z_2$
- Spectrum in an separable Hilbert space
- Calculating logs and fractional exponents by hand
- Prove $\left|\partial_t \frac{1}{(4\pi t)^{2N}}e^{-\frac{|x|^2}{4t}}\right| \le \frac{1}{(4\pi t)^{2N}} C \frac{e^{-\frac{|x|^2}{4t}}}{t}$
- In $\ell^p$, if an operator commutes with left shift, it is continuous?
- The double cover of Klein bottle
- Showing Uniform Convergence of $f_n(x) = \frac{nx}{1+nx}$ for $x \geq 0$.
- integer solutions to $x^2+y^2+z^2+t^2 = w^2$
- Estimating line paths in vector fields.
- Hessian matrix of a quadratic form
- References request: Ramanujan's tau function.
- What's the difference between convolution and crosscorrelation?
- How to prove that the normalizer of diagonal matrices in $GL_n$ is the subgroup of generalized permutation matrices?
- Expectation of random variables ratio
- For $n \in \mathbb{N}$, show that $4^n + 10 \times 9^{2n-2}$ is divisible by 7