Extended Euclidean Algorithm Puns

So about the Extended Euclidean algorithm, the algorithm that finds, a, b, and d in the equation am+bn=d, where m and n are two positive integers, d is their GCD, and a and b are two integers (not necessarily positive)

So the book I am following has the following instructions for implementing this algorithm:

E1. [Initialize.] Set a′ ← b ← 1, a ← b′ ← 0, c ← m, d ← n.

E2. [Divide.] Let q and r be the quotient and remainder, respectively, of c divided by d. (We have c = qd + r and 0 ≤ r < d.)

E3. [Remainder zero?] If r = 0, the algorithm terminates; we have in this case am + bn = d as desired.

E4. [Recycle.] Set c ← d, d ← r, t ← a′, a′ ← a, a ← t − qa, t ← b′, b′ ← b, b ← t − qb, and go back to E2.

My problem is that I don't particularly understand all the math around this algorithm, I understand the normal Euclidean algorithm well enough, so I understand half of the extended one as well. What I don't understand is the need for a' and b' as well t (I get that t is a temporary variable but I don't get the a = t - qa and b = t - qb part). That as well as the initialization of the variables a, a', b, and b' as well as the swapping of the values between them on each iteration. Can anybody help me bridge these gaps in my understanding of this algorithm?

I know this is probably one of the simpler parts of the problem, but how (in this example) are they getting 5 * 675 - 16 *210 from 5 * (675 - 3 * 210) - 210? I understand all the mod calculations and plugging in steps, just that last jump is getting me.

https://preview.redd.it/89la6ngpx6u51.png?width=637&format=png&auto=webp&s=69ce6e371970ded844ec77488b9958d191fdec48

Found GCD(561, 442) to be 17

561 = 1*442 +119

412 = 3*119 +85

119 = 1*85 + 34

85 = 2*34 + 17

34 = 2*17 + 0

Rewritten

561 - 1*442 =119

412 - 3*119 =85

119 - 1*85 = 34

85 -2*34 = 17

34 -2*17 = 0

Then what do I do? I think I need to substitute somehow, but I cannot figure that out

from "https://crypto.stanford.edu/pbc/notes/numbertheory/euclid.html"

3=33m+27n

6=33-1*27

3=27-4*6

3=27-4*(33-1*27) = (-4)*33+5*27

m = -4, n=5

How did they get from 3=27-4(33-1*27)

to

3= -4*33+5*27... Where did the +5 come from? How does that term 3=27-4(33-1*27) become -4*33+5*27

Thanks!

Hi, I feel like this must be a really silly question compared to the other questions I have seen on this subreddit.

But pretty much I'm a little stuck on how to do the Euclidean's algorithm.

I think the part I don't understand is when you simplify the groups.

How did they get from this to the end result

31 = ( 527 - 341 x 1 ) x 2 - 341

31 = 527 x 2 - 341 x 2 - 341

31 = 527 x 2 - 341 x 3

I understand how they got to the first equation by expanding but I'm a little confused about the simplification process.

also please keep in mind this is not a homework question but I just want to learn the Euclidean's algorithm the question I'm talking about can be found here.

Animating the Euclidean Algorithm and its application to computer science encryption (extended Euclidean Algorithm - Bézout's identity) would be really cool. Computers stay secured by an algorithm derived 3000 years ago.

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

I have spent a few hours watching videos and running through this, and would appreciate any help. I have successfully used the extended euclidean algorithm to find the modular multiplicative inverse of other examples, but have failed with this example: 17x = 1 (mod 90). I have used brute force calculations to successfully define x as 53, but I can not get the result using the Euclidean algorithm.

Where am I going wrong?

This is the first portion to reduce to 1:

90 = 5(17) + 5

17 = 3(5) + 2

5 = 2(2) + 1

1 is reached, indicating a multiplicative inverse exists, so I begin working back up now for the extended portion of the algorithm, solving for the remainders first:

1 = 5 - 2(2)

2 = 17 - 3(5)

5 = 90 - 5(17)

Now, the issue begins when I start substituting:

1 = 5 - 2(2)

= 5 - 2(17-3(5))

=7(5) - 2(17)

=7(90-5(17))-2(17)

=7(90)-37(17) mod 90

1 =37(17) mod 90 <---- this is false, mod 90 returns 89, not 1.

Any help working out the second half of the algorithm with these numbers would be greatly appreciated. *Solved see comments.

I believe so that the Extended Euclidean Algorithm and other related algorithm of getting the inverse modulo would only yield to the smallest positive d

and the formula for getting d is either

d ≡ e-1 (mod ϕ(n) )

or

d * e mod ϕ(n) = 1

where e and (mod phi(n)) are constant numbers

my current implementation right now is through bruteforce

ull getD(ull e, ull totient)
{	
    ull d;
    smint flag;
    
    for(d=flag=0; d < ULLONG_MAX && flag < 2; d++) {
        if(d*e % totient == 1) {
            flag++;
        }
    }
    return d;
}

this code should get the third candidate of d that would satisfy the equation..

The problem I'm trying to solve is this:
d * 3 ≡ 1 mod 40

That is (d * 3) / 40 should have a remainder of 1

I use Extended Euclidean algorithm to try and solve this since gcd(3, 40) is 1.

Euclidean

40 = (3 * 13) + 1  
3 = (1 * 3) + 0 

Extended Euclidean

1 = 40 - (3 * 13)
0 = 3 - (1 * 3)
0 = 3 - 3[40 - (3 * 13)]  // replaced 1 with the equation above
0 = 3 - [40(3) - 3(39))]  // distribute 3
0 = 3 + [40(-3) + 3(39))]  //distribute -
0 = [40(-3) + 3(40))]

I'm getting 40 instead of 27. What am I doing wrong?

Edit:
I solved: 7 * e = 1 mod 20 like so:
Euclidean

    20 = (7*2) + 6
    7 = (6*1) + 1
    6 = (1*6) + 0

Extended

    6 = 20 - (7*2)
    1 = 7 - (6*1)
    
    1 = 7 - [20 - (7*2)]
    1 = 7 + [(-1)20 + (2)7]
    1 = [(-1)20 + (3)7]

The correct answer is e = 3
I can't find what I'm doing wrong for the d * 3 ≡ 1 mod 40 problem. It seems like I'm doing the exact same steps...

Hi, I've looked at several youtube tutorials and googled thoroughly on how to use the Extended Euclidean Algorithm to find the multiplicative inverse. I'm still not sure how to do this problem though because the remainder equals 1 in the first step...

Problem: Use the EEA and your code to find the multiplicative inverse of 5474 mod 10949. Confirm that your answer is correct by showing that 5474 * x mod 10949 = 1.

Help!

I've been presented with the following question and I'm a bit lost as to how to solve or explain it:

Find integers x and y such that 8 = x * 1022 + y * 400, or explain why they don’t exist.

I've gone through the algorithm earlier and done the following working out:

1022 = 2 * 400 + 222

400 = 1 * 222 + 178

222 = 1 * 178 + 44

178 = 4 * 44 + 2

44 = 22 * 2 + 0

I must be a moron but anytime wikipedia gets into mathematics none of it ever makes any sense. I understand how to work the algorithm by hand using the back substitution method but I don't understand it well enough to turn it into a computer algorithm.

Basically, how do I solve something like 13^-1 mod 60 using an algorithm?

I was playing around with GATs today and decided to challenge myself to implement the Euclidean Algorithm using only the type system. Also, to make it even harder, I used GATs wherever possible, including for implementing comparisons, addition, squaring, and multiplication on the natural numbers.

GitHub gist

Playground link

Surprisingly the most difficult part was implementing the absolute difference operation (|x-y|). I had to create a "-1"-ish type which I'm not thrilled about :/

I tried to provide at least a little documentation of my thought process, but some of the implementation (mostly floor division) is a bit messy.

Let me know what you think, this is my first time posting here and my first finished Rust project that I'm really proud of!

As the title says, a program to run the Euclidean algorithm on the fx-991EX: https://imgur.com/a/L3MC2dD

It's a little technical, a little long ( ... ), but for a first ever ( because I can say with some confidence that no one sufficiently versed with calculator logic programs on a non-programmable calculator ) attempt I made in a physics lesson I don't think it's so bad ( there are a few bits here and there I'm able to condense, but for reasons of convenience I don't think I will ).

Now, as for actually running the 'program':

We start with the initialisation of the variables:

• Set A to be the larger of the two values, B to be the smaller, and everything else as 0.

• Make sure the calculator is operating with radians as the angle measure, degrees will not work with what I've done here. ( If you're unsure of how this is changed, just type in [ SHIFT, SETUP, 2, 2 ] ) ).

• Next, input: [ A . STO x ]

• If entered correctly, this should trigger a syntax error ( all intended, don't worry! ).

( note: it's important that the decimal point is not deleted until after the program is entered in full, so keep it there even as we're typing in the rest )

• Press on the D-PAD Left button three times to move to the end of the expression and continue to write the program till we're finished and it's all on screen.

• Remove the decimal point and start the program by pressing enter. From here on you'll need to manually push equals for every step forward.

Done! There's nothing more that requires any direct input, so just keep it going and if all goes well it’ll finish with the very last value of B as the HCF of our initial inputs A & B.

If anyone has any thoughts / queries, feel free to share, I’m quite interested to see if there’re actually any meaningful applications to this. Happy calculating!

n >= 3.
The greatest common divisor is:

(F_n, F_n+1).

so be it:

aF_n + bF_{n+1}.

What general assumption could you make about a and b? Prove it.

This is our task and we are completly lost about how to deal with that.

Hi folks. In short, the Euclidean method of calculating GCD says that;

suppose a>= b and rem = remainder, gcd(a, b) = gcd(rem(a,b), b)

Implementing this method is also easy. However, I do wonder what its algorithmic complexity is. Or does it exist in terms of known notations? I know some basic ideas behind categorizing algorithms such as recursivity, loops, binary searches, etc, but I couldn't categorize that. Thanks in advance.