Number theory notation

502 Views Asked by At

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 ?

1

There are 1 best solutions below

5
On BEST ANSWER

$$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}$