Simplify X * C1 == C2 with undefined overflow

[Jakub Jelinek]

On Fri, Aug 07, 2020 at 10:57:54PM +0200, Marc Glisse wrote:
> On Fri, 7 Aug 2020, Joern Wolfgang Rennecke wrote:
> 
> > 
> > On 07/08/20 19:21, Marc Glisse wrote:
> > > 
> > > If we are going to handle the wrapping case, we shouldn't limit to
> > > the non-wrapping meaning of multiplicity. 3*X==5 should become
> > > X==1431655767 (for a 32 bit type), etc.
> > > 
> > > Do we have an extended gcd somewhere in gcc, to help compute 1431655767?
> > I don't quite see yet how this relates to gcd,
> 
> https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm is the most
> common way to compute the modular multiplicative inverse of a number. For 3
> and 2^32, it could tell us that 2863311531*3-2*2^32=1, so modulo 2^32
> 2863311531*3==1, and 3*X==5 is the same as 2863311531*3*X==2863311531*5,
> i.e. X==1431655767.

wi::gcd ?

	Jakub