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$,where$Z,Z'\in\mathbb Z$
But generally,$Z\not =Z'$

 

[Apteronotus]

This is a special case.
$ka=Z(kb)+c$ and $a=Z'(b)+d$,where$Z,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:
$$b = aq + r, 0 \leq r <\left|a\right|$$

Therefore:
$$b=aq + r \Rightarrow kb = \left(ka\right)q + kr$$

But, as $0 \leq r <\left|a\right|$ and $k \geq 0$ then $0 \leq kr <\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
$$a = q\cdot b + r,$$
where [itex]q[/tex] is the quotient and $r$ is the remainder ($0\leq r< |b|$). Then, just multiply everything by $k.$

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.