Taken from here (last page).
Let $t\in\mathbb Z$ and let $0\le j\le g-1$ such that $j\equiv t \pmod g$.

Then,$$t\cdot \frac {m}{g}\equiv j\cdot \frac{m}{g}\pmod m$$

($g = \gcd (m,a)$ if it matters)

Why is that?

Also, if I'm trying to divide by $m$ I get:

$$\frac{t}{g} \equiv \frac{j}{g} \pmod {1} \implies \frac{t}{g} = \frac{j}{g} \implies j=t$$

but it doesn't have to be the case at all that $j=t$.

I'd be glad if you could help me arranging my thoughts around this.



By your assumption, $(t-j)/g$ is an integer $c$. Therefore $$t\frac{m}{g}-j\frac{m}{g}=cm.$$ Is this divisible by $m$?

  • $\begingroup$ okay, I get it. From here $t \frac{m}{g} = j\frac{m}{g} + cm \implies t \frac{m}{g} = j \frac{m}{g} \pmod m$ $\endgroup$ – Elimination Dec 10 '17 at 10:56
  • $\begingroup$ but why is dividing by $m$ leading to the might-be-false-conclusion that $j=t$? $\endgroup$ – Elimination Dec 10 '17 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.