0

Let $p=4295098403$ (tested prime), let $z=65537$ (prime). The following equality:

$$(kp - kp\bmod z) \equiv k(p-p\bmod z)\bmod p$$

is true for values of $k<1928$, but false for $k \geq 1928$. This may be a silly question, but what in the world is going on here (besides my lack of math comprehension)?

UPDATE: this can be reduced to $\left\lfloor\frac{kp}{z}\right\rfloor \equiv k\left\lfloor\frac{p}{z}\right\rfloor\ \text{mod}\ p$ only for smaller values of $k$.
Try it in Python: [k for k in range(z) if (k*p)/z == k*(p/z)]

Generally speaking, what is the proper way to distribute the k value to the inner mod? Thanks!

Michael Hardy
  • 1
Russ
  • 451
  • 2
  • 9
  • Your title has $\bmod p$ on both sides of the equivalence, but the body does not. Which do you mean? – Ross Millikan Oct 30 '17 at 22:42
  • You seem to confuse two different notational conventions with each other. When you write $(a\equiv b) \mod n$ that means $a$ and $b$ both leave the same remainder on division by $n.$ For example, one has $(52\equiv 67) \mod 5.$ But there is also the notation $a\bmod n,$ which means the remainder when $67$ is divided by $5.\qquad$ – Michael Hardy Oct 30 '17 at 23:02

1 Answers1

1

Note that $p \bmod z=34$ and $k(p \bmod z)=34 \cdot 1928=65552$ which has just crossed above $z$. If you do $kp \bmod z$ you remove one more copy of $z$ than if you do $p \bmod z$ and then multiply by $k$.

Ross Millikan
  • 374,822
  • Thanks - I should have used the "modular rhyme:" the mod of the prods is the prod of the mods (with one final mod). – Russ Oct 31 '17 at 12:27