Property of Modulo operator

Apr 2010
215
0
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
Nov 2006
16,046
936
UTC -5
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?
 

Hoempa

Math Team
Apr 2010
2,780
361
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
 
Apr 2010
215
0
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
Apr 2010
2,780
361
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
 
Apr 2010
215
0
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
Apr 2010
2,780
361
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
Nov 2006
16,046
936
UTC -5
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\).
 
Apr 2010
215
0
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}\)