Calculating integer overflow in C

Question

I'm attempting to solve the following equation for x to make the if statement true. I have tried using a linear congruence equation however could not get the right answer.

I am using the assumptions that integer overflow occurs at 2^63-1, and x is of type long

Could someone give me a pointer with how to do this?

long arg1 = 1234123412341234;
long arg2 = -3456345634563456;
if(x * arg1 == arg2) {
    //true
}

Answer 1

First, note that signed integer overflow is undefined. Unsigned integer overflow is, however, defined. I’m not sure how much that changes the problem, but I’m going to assume unsigned integers rather than signed integers.

The problem, again, is x × arg1 = arg2. To make the wrapping explicit, we have x × arg1 ≡ arg2 (mod 2⁶⁴). If we want x, we just solve for it; in particular, we have x ≡ arg1⁻¹ × arg2 (mod 2⁶⁴).

The question then is how to find arg1⁻¹. It happens that this is called a modular multiplicative inverse, and when it exists (it exists iff arg1 is relatively prime to 2⁶⁴), it can be found using the extended Euclidean algorithm.