if $a b \bmod n = x$ then is it true that $x b \bmod n = a$?

Question

I am a student of computer science and I'm doing cryptography; I need to optimise the way I calculate modulus.

What I'am doing is like this:

$$14 \cdot 16 \equiv 3 \bmod 17$$

$$3 \cdot 16 \equiv 1 \bmod 17$$

My question is if that is true for all numbers.

My goal is to know if this is true so that once I calculate $14 \cdot 16 \equiv 3 \bmod 17$, I can derive the result of $3 \cdot 16 \bmod 17$ without doing all the work.

Also, Is this true for "power modulus"? I mean

if $a^d \equiv b \bmod{n}$, is $b^d \equiv a \bmod n $?

Answer 1

In more common notation, what you're saying is this:

"Is it true that $ab \equiv x \pmod n$ implies $xb \equiv a \pmod n$?"

This is not true in general. A counter-example is given by letting $n=4$, and $a=b=2$ and $x=0$. Then $ab \equiv 0 \pmod 4$, but $0 \cdot 2 \not \equiv 2 \pmod 4$.

Answer 2

If $x\equiv a\cdot b\pmod n$

and $x\cdot b\equiv a\pmod n\implies x\equiv b^{-1}\cdot a\pmod n$

$$\implies a\cdot(b-b^{-1})\equiv0\pmod n$$ which is not true in general.

If $(a,n)=1, $ we need $b-b^{-1}\equiv0\pmod n\iff b^2\equiv1\pmod n$ assuming $(b,m)=1$

---

If $a^d\equiv b\pmod n$ and $b^d\equiv a\pmod n$

$\implies (a^d)^d\equiv a\pmod n\implies a^{d^2}\equiv a\pmod n$

If $(a,n)=1, a^{d^2-1}\equiv\pmod n$

$\implies ord_na$ needs to divide $d^2-1$ which is not true for all $d$

Answer 3

No, this is just a coincidence. Have you tried with other values of $a$, $b$ and $x$ to check whether it holds?

First, this only makes sense if $a \lt n$, from the definition of modulo.

But even in that case, if you replace the value of $x = \left (a \cdot b \right ) \, \mathrm{mod} n$ into the second equality, you would get $\left (x \cdot b \right ) \, \mathrm{mod} n = \left (a \cdot b^{2} \right ) \, \mathrm{mod} n = a$ which only holds if $a$ and $b^2$ are multiplicative inverses modulus $n$, which does not generally happen.

Answer 4

You probably need to learn a little bit about finite fields to make much progress. What you have written works because $16\equiv-1 \mod{17}$.

What might help you is to find a primitive root. This enables you to do the equivalent of taking logarithms. So mod 17, 3 is a primitive root and we have:

$1\equiv 3^{16}$; $2\equiv 3^{14}$; $3\equiv 3^{1}$; $4\equiv 3^{12}$; $5\equiv 3^{5}$; $6\equiv 3^{15}$; $7\equiv 3^{11}$; $8\equiv 3^{10}$; $9\equiv 3^{2}$; $10\equiv 3^{3}$; $11\equiv 3^{7}$; $12\equiv 3^{13}$; $13\equiv 3^{4}$; $14\equiv 3^{9}$; $15\equiv 3^{6}$; $16\equiv 3^{8}$

It is then possible to use the powers like logarithms, adding them mod 16. The problem of finding a primitive root in the first place is not straightforward.