Skip to main content
added 174 characters in body
Source Link
JMP
  • 22.8k
  • 51
  • 37
  • 55

If $a\equiv b \mod n$, then we can write $a=b+kn$ for some $k\in\mathbb{Z}$.

So multiplying by $m$ say gives $am=bm+knm$, which rewriting incan be written as $\mod n$ form reads$am\equiv bm \mod mn$, but also as $am\equiv bm \mod n$, aswith $km$ isas the 'new' $k$.

$a^{-1}$ exists as $\gcd(a,n)=1$, and is an integer between $1$ and $n-1$, and doesn't appear in the modulus for the reason given above.

For part 2, $5^{-1}\cdot 5\equiv 1 \mod {13}$, and

$$5x\equiv 5\cdot15 \mod {13}$$ $$ 5^{-1}\cdot 5x\equiv 5^{-1}\cdot 5\cdot15 \mod {13} $$ $$ x\equiv 15 \mod {13}$$

If $a\equiv b \mod n$, then we can write $a=b+kn$ for some $k\in\mathbb{Z}$.

So multiplying by $m$ say gives $am=bm+knm$, which rewriting in $\mod n$ form reads as $am\equiv bm \mod n$, as $km$ is the 'new' $k$.

$a^{-1}$ exists as $\gcd(a,n)=1$, and is an integer between $1$ and $n-1$, and doesn't appear in the modulus for the reason given above.

If $a\equiv b \mod n$, then we can write $a=b+kn$ for some $k\in\mathbb{Z}$.

So multiplying by $m$ say gives $am=bm+knm$, which can be written as $am\equiv bm \mod mn$, but also as $am\equiv bm \mod n$, with $km$ as the 'new' $k$.

$a^{-1}$ exists as $\gcd(a,n)=1$, and is an integer between $1$ and $n-1$, and doesn't appear in the modulus for the reason given above.

For part 2, $5^{-1}\cdot 5\equiv 1 \mod {13}$, and

$$5x\equiv 5\cdot15 \mod {13}$$ $$ 5^{-1}\cdot 5x\equiv 5^{-1}\cdot 5\cdot15 \mod {13} $$ $$ x\equiv 15 \mod {13}$$

Source Link
JMP
  • 22.8k
  • 51
  • 37
  • 55

If $a\equiv b \mod n$, then we can write $a=b+kn$ for some $k\in\mathbb{Z}$.

So multiplying by $m$ say gives $am=bm+knm$, which rewriting in $\mod n$ form reads as $am\equiv bm \mod n$, as $km$ is the 'new' $k$.

$a^{-1}$ exists as $\gcd(a,n)=1$, and is an integer between $1$ and $n-1$, and doesn't appear in the modulus for the reason given above.