2
$\begingroup$

I am confused with the below notations .

I know that

($a \equiv b \mod {n} )\iff ( n|(a-b)$ )

but what the below notation says ?

$a = b \mod {n}$

and in theorem 16 in this ,it's given as below

if $g \in\mathbb{Z_n^*} , r_1,r_2 \in \mathbb{Z_n}$ and $m_1,m_2 \in \mathbb{Z_n}$

($g^{m_1}r_1^n =g^{m_2}r_2^n \mod {n^2}) \implies (g^{m_1-m_2}r_1^n=r_2^n \mod{n^2}$)

In the above equation , both sides are divided with $g^{m_2}$

When we can divide both sides of a modular expression as in the above equation with a number ?

$\endgroup$
  • $\begingroup$ This is wrong, $a\equiv b\mod n\iff n|(a-b)$ not the other way around. $\endgroup$ – Adam Hughes Jul 2 '14 at 17:29
  • 2
    $\begingroup$ When the number we are dividing by is relatively prime to the modulus. $\endgroup$ – André Nicolas Jul 2 '14 at 17:31
  • $\begingroup$ @AdamHughes yeah , edited . $\endgroup$ – hanugm Jul 2 '14 at 17:31
  • 1
    $\begingroup$ You can use the Euclidean algorithm to see that "division" is legal when $gcd(g,n)=1$. $\endgroup$ – Adam Hughes Jul 2 '14 at 17:33
  • 1
    $\begingroup$ @hanu $\ a = b\ {\rm mod}\ n\ $ could mean either $\ a\equiv b\pmod n\ $ or $\ a = (b\ {\rm mod}\ n),\,$ i.e. the former combined with $\,0\le a < n.\ \ $ $\endgroup$ – Bill Dubuque Jul 2 '14 at 17:45
2
$\begingroup$

$$g^{m_1}r_1^{n} \equiv g^{m_2}r_2^{n} \pmod {n^2} \Rightarrow n^2 \mid g^{m_1}r_1^{n} - g^{m_2}r_2^{n} \\ \Rightarrow n^2 \mid g^{-m_2} \cdot (g^{m_1}r_1^{n} - g^{m_2}r_2^{n}) \Rightarrow n^2 \mid g^{m_1-m_2}r_1^n-r_2^n$$

EDIT: We can multiply with $g^{-m_2}$,because, we know that $g \in \mathbb{Z}^*$,so it is a unit,therefore $g^{-1}$ exists.

In general, if $m \mid a-b \Rightarrow m \mid x(a-b), \forall x \in \mathbb{Z}$

$\endgroup$
  • $\begingroup$ but is $g^{-m_2} \in \mathbb{Z}$ ? $\endgroup$ – hanugm Jul 2 '14 at 17:39
  • $\begingroup$ I edited my answer..Tell me if you understand it now!!! $\endgroup$ – evinda Jul 2 '14 at 17:41
  • $\begingroup$ @hanu: an inverse can be found using the Euclidean algorithm, as I indicated in my previous comment. $\endgroup$ – Adam Hughes Jul 2 '14 at 17:43
  • $\begingroup$ Yeah , understood . what about the notation $a=b \mod {n}$ , is it same as $a \equiv b \mod{n}$ $\endgroup$ – hanugm Jul 2 '14 at 17:45
  • 1
    $\begingroup$ Nice! it is the same,but it is better to write it like that : $$a \equiv b \pmod n$$ because it isn't exactly an equality!!!We are working $\mod n$.. $\endgroup$ – evinda Jul 2 '14 at 17:47

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.