skpro19's blog

By skpro19, history, 8 years ago, In English

The question is this.

I went through one of the submitted solutions:

I understood that for the solution to exist C must be divisible by g = gcd(A, B);

But, how are we getting the final values for x and y ?

Also, it would be very nice if someone can suggest some nice problems to practice on this topic.

Thanks!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Good day to you!

The solution uses Extended Euclidean Algorithm

To practice this problem more, you can try — for example — this problem.

You can also try any problem, which requires "Modular Inversion", which can be counted by Extended GCD too

Good Luck!