# Property of Modulo operator

#### brangelito

How do I prove the following?
(the question mark is the modulo operator)

a,b,x: positive integers.
$$\displaystyle x ? a = \frac{a}{b}\cdot(\frac{bx}{a} ? b)$$

#### CRGreathouse

Forum Staff
I'm not even sure how to interpret the problem! Does $$\displaystyle \frac{bx}{a}?b$$ mean the modular inverse of a, modulo b, times b, times x? If so, how should $$\displaystyle \frac ab$$ be interpreted?

#### brangelito

In C, I would write:

x % a == a/b * ((x * b/a) % b)

#### Hoempa

Math Team
Maybe, use: x?a=d, x=d+ak, k is positive integer. so $$\displaystyle d=x-ak$$
$$\displaystyle \frac{a}{b}\cdot\left(\frac{bx}{a}?b\right)=g.$$

$$\displaystyle \frac{a}{b}\cdot\left(\frac{bx}{a}-bk\right)=\frac{a}{b}\cdot{b\frac{x-ak}{a}=g$$

$$\displaystyle g=x-ak$$

d=x-ak, g=x-ak, so d=g.

QED (?)

Hoempa

#### brangelito

I'm sorry, but how do you know that:
$$\displaystyle \frac{a}{b}\cdot\left(\frac{bx}{a}?b\right)=\frac{a}{b}\cdot\left(\frac{bx}{a}-bk\right)$$

Thanks!

#### Hoempa

Math Team
Maybe, I could make that more clear with an example.

23?7=2.
23=2*7*k. In this case, k=3. It is not neccesary to know k.

Is it more clear now?

Hoempa

#### brangelito

Hoempa said:
Maybe, I could make that more clear with an example.

23?7=2.
23=2*7*k. In this case, k=3. It is not neccesary to know k.

Is it more clear now?

Hoempa
Ah, now it is obvious. Thank you.

$$\displaystyle k_1= k_2$$

where
$$\displaystyle k_1 = \lfloor \frac{x}{a} \rfloor$$
$$\displaystyle k_2 = \lfloor \frac{bx}{ab} \rfloor$$

#### Hoempa

Math Team
You're welcome
Yeah, that's true.
Hoempa said:
Should be 2+7*k.

Well, it is obvious, that's what matters.

Hoempa

#### CRGreathouse

Forum Staff
brangelito said:
In C, I would write:

x % a == a/b * ((x * b/a) % b)
Hmm... in C * and / are of equal precedence, and that precedence block associates left-to-right. So the expression on the right is (a/b)*(((x*b)/a)%b).

Now x, a, and b are integer variables, so / is integer division. So it is
$$\displaystyle \left\lfloor\frac ab\right\rfloor\cdot\left(\left\lfloor\frac{xb}{a}\right\rfloor\bmod b\right)$$
or
Code:
a\b*(x*b\a%b)
in Pari.

But these don't work: with (a, b, x) = (2, 1, 1)
$$\displaystyle \left\lfloor\frac 21\right\rfloor\cdot\left(\left\lfloor\frac{1\cdot1}{2}\right\rfloor\bmod 1\right)=2\cdot\left(0\bmod 1\right)=0$$
but
$$\displaystyle 1\bmod2=1\neq0$$.

#### brangelito

I wasn't talking about integer division, sorry for not making that clear.

CRGreathouse said:
brangelito said:
In C, I would write:

x % a == a/b * ((x * b/a) % b)
Hmm... in C * and / are of equal precedence, and that precedence block associates left-to-right. So the expression on the right is (a/b)*(((x*b)/a)%b).
It doesn't matter, right?
$$\displaystyle x\cdot\frac{b}{a} = \frac{xb}{a}$$