Is (ka)mod kb Equal to k(a mod b)?

[Apteronotus]

Hi

Just a simple Mod question.

Is (ka)mod kb = k(a mod b)?

Thanks

 

[HallsofIvy]

(ka) mod kb is the remainder when ka is divided by kb. Obviously, ka/kb= a/b and so has the same remainder as a divided by b. Therefore, the answer to your question is "no". What is true is that (ka) mod kb= a mod b.

 

[Apteronotus]

perhaps a counter example to your reply...

15 mod 9 = 6
5 mod 3 = 2
but
3(5 mod 3) = 6

 

[Apteronotus]

Yes I do believe I am correct. Suppose
ka mod kb = c
and
a mod b = d
then this means that
ka = Z(kb)+c
and
a = Z(b)+d
where Z is an integer
Hence c/k=d, and if this is true then
ka mod kb = c = kd = k(a mod b)

Thank you for your reply anyway.

 

[kntsy]

Yes I do believe I am correct. Suppose
ka mod kb = c
and
a mod b = d
then this means that
ka = Z(kb)+c
and
a = Z(b)+d
where Z is an integer
Hence c/k=d, and if this is true then
ka mod kb = c = kd = k(a mod b)

Thank you for your reply anyway.

This is a special case.
ka=Z(kb)+c and a=Z'(b)+d,whereZ,Z'\in\mathbb Z
But generally,Z\not =Z'

 

[Apteronotus]

This is a special case.
ka=Z(kb)+c and a=Z'(b)+d,whereZ,Z'\in\mathbb Z
But generally,Z\not =Z'

No I don't think so.

We have
ka=(kb)Z+c where 0<c<kb
and
a = bZ'+d where 0<d<b
multiplying the second equation by k we arrive at
ka = kb Z' +kd
so
kb Z +c = kb Z'+kd
kb(Z-Z')=kd-c
(Z-Z')=(kd-c)/kb
Hence the right hand side must be an integer. But since both kd and c are in (0,kb), the distance between them kd-c cannot be larger than kb. so it must be zero.
Giving us Z=Z'

 

[JSuarez]

First, your equality can only be valid for k\geq 0. Second, everyone seems to be forgetting the remainder theorem: for b,a in Z, there are unique integers q and r, such that:
<br /> b = aq + r, 0 \leq r &lt;\left|a\right|<br />

Therefore:
<br /> b=aq + r \Rightarrow kb = \left(ka\right)q + kr<br />

But, as 0 \leq r &lt;\left|a\right| and k \geq 0 then 0 \leq kr &lt;\left|ka\right|, which means that (by uniqueness) kr is the remainder of kb divided by ka, hence:

(kb mod ka) = kr = k(a mod b), k\geq 0

 

[Apteronotus]

..., hence (kb mod ka) = a mod b, for k\geq 0.

2*7 mod 2*3 = 2
7 mod 3 = 1

?

 

[JSuarez]

Sorry. There was a typo in the last equality; it's corrected now.

2*7 mod 2*3 = 2(7 mod 3) = 2

 

[zgozvrm]

(ka) mod kb is the remainder when ka is divided by kb. Obviously, ka/kb= a/b and so has the same remainder as a divided by b. Therefore, the answer to your question is "no". What is true is that (ka) mod kb= a mod b.

Not true...
Suppose a=12, b=5, k=8
Then you have, ka=96, kb=40

Sure, a/b=2.4 and ka/kb=2.4

But, a mod b = 2 whereas (ka) mod (kb) = 16



And, by the way, the answer (if it was unclear by reading through this thread), is "yes"
k * (a mod b) = (ka) mod (kb) for ALL a, b, k such that k<>0 and b<>0 (otherwise, you will have a divide-by-zero error)

 

[zgozvrm]

And, by the way, the answer (if it was unclear by reading through this thread), is "yes"
k * (a mod b) = (ka) mod (kb) for ALL a, b, k such that k<>0 and b<>0 (otherwise, you will have a divide-by-zero error)

Here's the proof...

Let's first assume that the symbol, \odot is the operator for the function "mod"
and that the function "int" returns an integer which rounded down from it's argument; for example, int(8.9) = 8, but int(-8.9)= -9

a \odot b = a - int \left( \frac{a}{b} \right) * b (this is the definition of the mod function)

Therefore,
k * ( a \odot b) = k * \left( a - int \left( \frac{a}{b} \right) * b \right) = ka - int \left( \frac{a}{b} \right) * kb

Then,
(ka) \odot (kb) = (ka) - int \left( \frac{ka}{kb} \right) * kb

but since \frac{ka}{kb} = \frac{a}{b}

we have

(ka) \odot (kb) = (ka) - int \left( \frac{a}{b} \right) * kb

which has already been shown to be equal to k * (a \odot b)

 

[tmccullough]

I found the above terribly painful, but completely correct. To prove your deal, just use the euclidean algorithm. Write
<br /> a = q\cdot b + r,<br />
where q[/tex] is the quotient and r is the remainder (0\leq r&amp;lt; |b|). Then, just multiply everything by k.<br /> <br /> In fairness, this is just zgozvrm proof with less abusive notation. Note that Halls of Ivy just confused the quotient with the reminder.

 

[Apteronotus]

Thank you all for your replies.