Stuck on Euclidean Algorithm Answer

Question

Hello smart mathematicians,

I am new to advanced maths so please do not judge.

I basically learnt some cool new math equation algorithm: Euclidean Algortihm.

Basically, I used it for the following example...

11a = 1 mod 60

Using Euclidean Algorithm:
60 = 5(11)+5
11 = 2(5)+1

But then what do I do after 11 = 2(5)+1? The answer to a is 11 but then I am stuck as to why or where I am going wrong

Any help, greatly appreciated!!!!!

Answer 1

Using your equations $$ 60 = 5(11)+5\implies 5= 60 - 5(11) $$ $$ 11 = 2(5)+1\implies 1 = 11 - 2(5) $$

we can unwind everything to write the gcd 1 in terms of 11 and 60, so we have

$$ 1 = 11 - 2(5) = 11 - 2(60 - 5(11)) = 11(11) - 2(60). $$

do you see what the answer is from here?

Answer 2

You have:

60 = 5(11)+5

11 = 2(5)+1

Use that to solve $11a + 60b = 1$.

Start with $1= 11 -2*5$.

Replace the $5$ from the line above $5 = 60-5*11$

So $1 = 11 - 2*5=$

$11 -2 (60-5*11) =$

$11 - 2*60 + 10*11 =$

$11*11 - 2*60$.

So $1 = 11*11 -2*60$.

And that's it!

To solve $11a + 60b =1$ we have $a=11$ and $b=-2$ are solutions.

So that means $11a = 1+2*60 \equiv 1 \pmod{60}$.

If have $11*a \equiv 1 \pmod {60}$ we have figured $11*11$ so if $a=11\pmod{60}$ that is a solution.

... Okay, I haven't explained how we knew that $11a\equiv 1\pmod{60}$ had any solutions at all in the first place, nor how we knew that it had only one solution[1].... but.... you didn't ask about that.

[1] Only one solution modulo $60$, that is. $11$ is a solution but so are $11 + 60k$. But all $11 + 60k\equiv 11\pmod {60}$ and are considered, for all intents and purposes, to be the same single thing.

Answer 3

Rem:This post has been modified in order to give an appropriate answer to the threads topic.

Ok here is my version of an answer after i initially missed a bit the topic you were asking for in the first version of this post(sorry)

Basicly the poster fleablood already answered everything important about the topic.

So question was about how to solve 11a=1 mod 60 using the Euclidean Algorithm.

The connection with the Euclidean Algorithm is due to the fact that $gcd(60,11)=1$ and in general for numbers $n,m\ n>m$ we can always find integers a,b such that $gcd(n,m)=na+mb$ (known as Bezout's lemma) in order to find a and b we execute the Euclidean Algorithm and write it down and then do the backward substitution as explained by fleablood and a is then a particular solution of $11a=1\ mod\ 60$ all the rest of solutions will be congruent then.

By the way this method can be generalized to solve any conguence of the type $mx=d\ mod\ n$ if $d=gcd(m,n)$