How to find X , at which (A + X * B) will be divided without remainder by C ?

For example: A = 17 , B = 199 , C = 11

(17 + X * 199) % 11 = 0

How to find X in the above example?

  • Start with A = A% C; B = B% C; and then stupid selection. - Akina
  • Is it possible to solve purely analytically? Formula. - Denis Leonov
  • 2
    neerc.ifmo.ru/wiki/… - Harry
  • Ta-a-ak, formula. Of course, you understand that the solutions here are infinite? - Igor
  • It's clear. It is necessary to find at least one solution. - Denis Leonov

2 answers 2

We consider everything on the module 11:

 17 + X * 200 = 0 6 + X * 2 = 0 X * 2 = -6 X * 2 = 5 X = 5 / 2

The inverse element for 2 is 6 (since 2 * 6 = 1)

 X = 5 * 6 X = 30 X = 8

http://e-maxx.ru/algo/reverse_element

Finding the inverse of a residue ring

  • Could you tell me how to calculate the inverse element in general? - Denis Leonov
  • @Denis, there is a description by reference and there is an Euler theorem . Well, binary exponentiation can be viewed. - Qwertiy ♦

The simplest option is brute force:

 function solve(a, b, c) { for (var x=0; x<c; ++x) { if ((a + b*x) % c === 0) { return x; } } } console.log(solve(17, 199, 11));

  • I am looking for a purely analytical solution. Bust does not fit. - Denis Leonov