Intereting Posts

Is a linear tranformation onto or one-to-one?
Is this a wrong solution to the smallest enclosing circle problem?
Inversion of Laplace transform $F(s)=\log(\frac{s+1}{s})$ (Bromwich integral)
Lie group, differential of multiplication map
How exactly are the beta and gamma distributions related?
Is there a division algorithm for any Euclidean Domain?
Do torsionfree abelian groups form a (possibly many-sorted) algebraic category?
Wallis Product for $n = \tfrac{1}{2}$ From $n! = \Pi_{k=1}^\infty (\frac{k+1}{k})^n\frac{k}{k+n} $
Evaluation of $\int\frac{5x^3+3x-1}{(x^3+3x+1)^3}\,dx$
Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?
Power of prime ideal
Find a basis for a solution set of a linear system
Meta Theory when studying Set Theory
How to sum this series for $\pi/2$ directly?
Integral of $1/z$ over the unit circle

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

- Characterizing a real symmetric matrix $A$ as $A = XX^T - YY^T$
- Finding the radical of an integer
- Merge Sort time complexity analysis
- How can I find the square root using pen and paper?
- Efficiently finding two squares which sum to a prime
- Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

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?

- Why multiplicative group $\mathbb{Z}_n^*$ is not cyclic for $n = 2^k$ and $k \ge 3$
- Determine the number of factors for extremely large numbers.
- Why are Hornsat, 3sat and 2sat not equivalent?
- Polynomial $p(a) = 1$, why does it have at most 2 integer roots?
- Elementary central binomial coefficient estimates
- Show that every prime $p>3$ is either of the form $6n+1$ or of the form $6n+5$
- Are there infinitely many primes and non primes of the form $10^n+1$?
- Show that $a - b \mid f(a) - f(b)$
- How prove that there are $a,b,c$ such that $a \in A, b \in B, c \in C$ and $a,b,c$ (with approriate order) is a arithmetic sequence?
- Is $a^b+b^a$ unique for all integers a and 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.$

- How many $n$-digit decimal sequences (using the digits $0 = 9$) are there in which the digits $1$, $2$ and $3$ all appear?
- The Multiplier Algebra of the Hardy Hilbert Space
- Subfields of finite fields
- Subgroups of $D_4$
- Integrating using Laplace Transforms
- Why doesn't induction extend to infinity? (re: Fourier series)
- If a derivative of a continuous function has a limit, must it agree with that limit?
- Prove or disprove that $\phi(a^n – 1)$ is divisible by n
- Simplify a combinatorial sum
- Is a coordinate system a requirement for a vector space?
- Show that there is sequence of homeomorphism polynomials on that converge uniformly to homeomorphism
- Proving a proposition which leads the irrationality of $\frac{\zeta(5)}{\zeta(2)\zeta(3)}$
- Projections onto ranges/subspaces
- Evaluating $\int_0^1 \frac{\log x \log \left(1-x^4 \right)}{1+x^2}dx$
- Proving the summation formula using induction: $\sum_{k=1}^n \frac{1}{k(k+1)} = 1-\frac{1}{n+1}$